We have alphabet $\Sigma = \{ { a, b} \} $.
How to construct CFG for language $\Sigma^{\ast} - \{a^{n}b^{n} | n \ge 0 \}$.
I suggest that is very easy, but I can't invent. I know PDA for this language if it can help.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Split into parts that you can handle. All strings not of the form $a^*b^*$. All strings of the form $a^ib^j$ with $i< j$. Then all strings ....
answered Nov 2, 2016 at 15:40
$\begingroup$
$\endgroup$
Yes, PDA for the language can certainly help. The transitions of the PDA can be transformed to production rules. This is an excellent video on PDA to CFG conversion.
Let me know if you need any clarification in conversion.
