1
$\begingroup$

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

As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to construct it is to define a CFG for the language, and then transform it to non-deterministic PDA which accepts strings by empty stack.

However, for this exercise, we have been forbidden to do that. We have to construct an automaton which accepts strings with a final state. Here's my proposed solution:

enter image description here

Here's my reasoning. If I was to construct a context-free grammar, the rules of production would be $S \to aSb | aSbb|\epsilon$. I tried to do something similar here by putting $a$ and $aa$ on the stack for the same input symbol and the same popped symbol from the stack, creating a non-deterministic PDA.

My question is: Am I correct to assume this is a correct interpretation of non-determinism?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ A possible approach to writing this PDA was suggested by Yuval in cs.stackexchange.com/a/147932/4287 , for a bound of $3n$ rather than $2n$, but that is similar. $\endgroup$
    – Hendrik Jan
    Jun 9, 2022 at 23:21

1 Answer 1

Reset to default
3
$\begingroup$

Your language is NCFL. Your design of NPDA is perfectly right. And in state $q_0,q_1$ and $q_2$ transitions makes your diagram NPDA. You accepts your strings by final state that is $q_3.$ If you want to accept by empty stack(without final state) then no need to move and create the new state $q_3.$ You just give the transition $(\epsilon,A/\epsilon)$ in state $q_2$ that is $\delta(q_2,\epsilon,A)=(q_2,\epsilon)$ , then the stack will be empty.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much! This is very important to me because yesterday I thought that the only method to solve the $n \le m \le x \cdot n, x \in \mathbb{N}$ is by doing CFG -> PDA. $\endgroup$
    – john doe
    Jun 10, 2022 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.