0
$\begingroup$

$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]$?

$\endgroup$
3
  • 1
    $\begingroup$ Hint: try to create a context free grammar (CFG) for the language. Then create a non-deterministic PDA out of it. $\endgroup$
    – plshelp
    Jun 9 at 11:56
  • $\begingroup$ @plshelp thank you very much! $\endgroup$
    – john doe
    Jun 9 at 14:38
  • $\begingroup$ Does this answer your question? PDA for { a^nb^m | 0 < n <= m <= 3n } $\endgroup$ Jun 9 at 23:05

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you very much any help is appreciated! I am able to solve it now. $\endgroup$
    – john doe
    Jun 9 at 14:38

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.