2
$\begingroup$

I know that CFG for $$ \{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is $$ S\rightarrow ab/abb/aSb/aSbb $$ but I am not able to tweak it in such a way that it is strictly in between m and 2m and not equal to any of m or 2m. I want to draw PDA for the same.

For drawing the PDA what I did was to push non-deterministically 1 a and 2a's and popping them out for b one by one. How should I handle the edge case that it always doesn't push 1 a or not always 2 a's?

$\endgroup$
1
$\begingroup$

As you knew intuitively, you just missed the solution by a millimeter, which, however, may look like a mile away.

$S\rightarrow aabbb/aSb/aSbb$

The idea is simple. Since $ab$ and $abb$ should not be generated, what is the shortest or simplest word that can be generated?

Here is a sketch of a NPDA. When it reads the first $a$, it goes to state $q_1$. When it reads the second $a$, it goes to state $q_2$. Then every time if it reads one $a$, it will push one or two $a$'s nondeterministically onto the stack. Then when it reads the first $b$ it goes to state $q_4$. When it reads the second $b$ it goes to state $q_5$. When it reads the third $b$ it goes to state $q_6$. Then every time if it reads one $b$, it pops out one $a$ from the stack, staying at state $q_6$.

I will let you flesh out the details.

$\endgroup$
  • 1
    $\begingroup$ For each $a$ that is read push either one or two $b$s on the stack and pop them again one by one while reading the $b$s. Reading at least two $a$s and not always pushing two $b$s (i.e. the edge cases) can be controlled by the states. $\endgroup$ – ttnick Dec 19 '18 at 23:01
  • $\begingroup$ I misled myself into construction of a DPDA, which cannot be done. For NPDA, the construction is easy. $\endgroup$ – Apass.Jack Dec 20 '18 at 5:29
  • $\begingroup$ What I did was to push non-deterministically 1 a, 2a's and popping them out for b one by one. How should I handle the edge case that it always doesn't push 1 a or not always 2 a's? $\endgroup$ – Amisha Bansal Dec 20 '18 at 6:36
  • $\begingroup$ Use states to deal with them. For the first $a$, just go to state $q_1$ without changing the stack. For the second $a$ go to $q_2$ without changing the stack. Now we are prepared to push to the stack (but not if we see $b$ immediately). $\endgroup$ – Apass.Jack Dec 20 '18 at 6:55

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.