Problem Detail: I am having issue with designing contex free grammar for the following language: $L = {0^n 1^m , | , 2n leq m leq 3n }$ I can design for the individual cases i.e. for $m geq 2n$ and $m leq 3n$ but don’t know how should i combine both. Or is it a different approach altogether?
Asked By : Inderdeep Singh
Answered By : Nejc
It has been a while, since I have done context-free grammars, but I think this should be the answer: $qquad displaystyle A to 0A11 mid 0A111 mid varepsilon$ I am assuming that empty string is in $L$. The idea behind is, that you are working your way from outside. Since you need at least 2 times more of $1$’s, than you need $0$’s, you need the first rule. The upper limit is handled with the second rule. All cases inbetween are also covered. $-$ is needed for termination.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6150 Ask a Question Download Related Notes/Documents
