If you want to make money online : Register now

Writing context free grammar

, , No Comments
Problem Detail: 

I have the following language:

{0m1n0n1m | m,n ≠ 0}

I was wanting to write Context-free grammar for it. I'm a little confused because the rule doesn't mention that m and n are not equal to each other, so could we treat them in a case as the same?

So could something like

S --> 0S1S0S1S


S --> 0101 | 0S10S1 | ε

Asked By : user3295674
Answered By : Shreesh

For simpler language $\{1^n0^n\ | \ n > 0\}$, we can write grammar as $S \rightarrow 1S0\ |\ 10$.

Now we can replace the non-terminal $S$ by $A$. And write context free grammar for the language in the question. $A$ is in the center of $0^m$ and $1^m$. Also remember $m,n > 0$.

$A \rightarrow 1A0 \ | \ 10$
$S \rightarrow 0S1 \ | \ 0A1$

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback