So I have this language: $$ A= \{ w \in \{a,b\}^* \mid 2*\#_a(w) \ne 3*\#b(w) + 2\} $$ I know it's context free, I know how to make a PDA for it, I just can't, for the life of me, figure out how to design a grammar for it.

I know that for this language: $$ A= \{ w \in \{a,b\}^* \mid 2*\#_a(w) = 3*\#b(w)\} $$ I can design a grammar that looks like this (and it's hopefully correct): \begin{align} S \rightarrow aSaSaSb | aSaSbSaSb | bSaSaSaSb | aSbSaSaSb | bSbSaSaSa|aSbSbSaSa|bSaSbSaSa|aSbaSbSa|bSaSaSbSa|aSaSbSbSa|SS|\lambda \end{align} And although I know that usually when the condition of the language has $x \ne y$ I should use the union of $x<y$ and $x>y$ I just can't figure out how to do this for this specific example. I would really appreciate your help on this!

  • $\begingroup$ Converting a PDA to a grammar is a standard topic covered in standard textbooks. I see little point in us repeating it here when it is already covered well in existing resources. See also cs.stackexchange.com/q/51658/755 $\endgroup$ – D.W. Sep 16 '20 at 22:56