Non-Deterministic Push Down Automata

Question

Can we make a NPDA for the following language?

$$L=\big\{w\in\{a,b\}^*:|w|_a\ne 3|w|_b\big\}$$

I was asked this question in exam today and I was unable to do so. Can anyone guide me?

Answer 1

A language is context free iff there is a NPDA that accepts it.

\begin{eqnarray} M &\to& \epsilon\\ &\to& M a M aMaMbM \\ &\to& M a M aMbMaM \\ &\to& M a M bMaMaM \\ &\to& M b M aMaMaM \\ \\ A &\to& a | M A M\\ \\ B &\to& b | M B M \\ \\ S &\to& A | B \\ \end{eqnarray} Any string $w$ derived from $M$ satisfies $|w|_a = 3 |w|_b$, and similarly, any string satisfying $|w|_a = 3 |w|_b$ can be derived from $M$.

Any string derived from $A$ has an excess of $a$s, and similarly, any string with an excess of $a$s can be derived from $A$. Similarly for $B$.

Hence the strings derived from $S$ are the same as the language $L$.