[Solved]: Designing context free grammar for a language with range restriction on repetition of alphabets

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