A CFG Grammar for One Language

69 Views Asked by At

Suppose :

$w_1,w_2 \in \{a,b\}^∗$

and

$ L=\{w_1w_2 \mid w_1,w_2 \in \{a,b\}^* \land n_a(w_1)=n_b(w_2)\}$

$n_a$ is number of $a$'s and $n_b$ is number of $b$'s.

This is a Entrance Exam question. I think there is a typo in this question, or I'm wrong and there is a L with {a,b} and {0,1} alphabet? Any clarification by some expert?

I know this is a CFG. but I couldn't write any CFG grammar. Anyone could help me?

thanks

1

There are 1 best solutions below

4
On BEST ANSWER

How about $S \rightarrow aSA \mid bS \mid \varepsilon$ and $A \rightarrow b \mid aA \mid \varepsilon$?

Disclaimer: I didn't think about this for more than ten seconds, so please check!