0
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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 ....

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.