[Solved]: writing a Context free grammar for a language

Problem Detail: 

Hi I have two question about this language: L = {a^i b^j c^k | i = 2*j OR j=2*k }

1)Finding a CFG

2)If in condition part we put AND instead of OR , is this language remains CONTEXT FREE or not ??

thanks.

Asked By : alireza sanaee

Answered By : Karolis Juodelė

1. $L_{i=2j ~\text{OR} ~ j=2k} = L_{i=2j} \cup L_{j=2k}$. I'll assume you can do the languages with only one condition.

2. If OR turns into AND, then $L = \{a^ib^{2i}c^{4i}\}$. Use pumping lemma to show that $L$ is not context free.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26087

3.2K people like this

 Download Related Notes/Documents