Design a Pushdown automaton for $L = \{a^nb^m | n \le m \le 3n \} $

Question

$L = \{a^nb^m | n \le m \le 3n \} $

This is by far the hardest pushdown automaton I had to design. I literally have no idea where to start. Here's my thought process. Firstly, I thought that for each valid pair $(n,m)$ the differences between the number of $b$s abd $a$s will be the same. That wasn't true, as the number of possible strings rose for each new value of $n$.

Next, I tried adding $a$ on top of the stack when I read $a$, and then removing them when I read $b$s. That would only cover the case when $m=n$. I can produce an automaton where $m=n$, $m=2n$ or $m=3n$, but how do I cover all the cases where $m \in [n, n+1, n+2, ..., 3n]$?

Answer 1

First of all your language is CFL means NCFL not DCFL because machine has push confusion. Therefore DPDA design is not possible. Only NPDA has power to accept your language.

You have to understand what is grammar for your language. Suppose $n=0,$ then $m=0$ and string becomes $\epsilon.$ So your language contain $\epsilon.$ Now for $n=1,$ then $m=1,2,3$ and strings are $ab, abb, abbb.$ For $n=2,$ then $m=2,3,4,5,6 $ and the strings are $aabb, aabbb$ etc. ... . .... . ... . ..

So your grammar will be $S\to aSb|aSbb|aSbbb|\epsilon.$

This time I haven't design NPDA as last time I did,I am writing only transition functions. Start state is $q_0$ , stack bottom is $Z_0$ and final state is $q_f.$

$\delta(q_0,a,Z_0)=(q_0,aZ_0),(q_0,aaZ_0,(q_0,aaaZ_0).$

$\delta(q_0,a,a)=(q_0,aa),(q_0,aaa),(q_0,aaaa).$

$\delta(q_0,\epsilon,Z_0)=(q_f,Z_0). $

$\delta(q_0,b,a)=(q_1,\epsilon).$

$\delta(q_1,b,a)=(q_1,\epsilon).$

$\delta(q_1,\epsilon,Z_0)=(q_f,Z_0).$