2
$\begingroup$

I've read in various threads on stack exchange as well as other webpages that every CFL has a corresponding PDA with just one state. I've studied PDA from Peter Linz's Automata book. However there is no mention of a single state PDA. In the text, they have mentioned a method for 3 state PDA and in the exercises they have reduced it to 2 states.

For a single state, I've come up with the idea of using multiple initial symbols on the stack so that I can simulate two different states in a single state in the following way:

Initially stack contains $xy$.

$\delta (a,xy,ay)$ #with $x$ gone from stack, a langauge such as $a^nb^na^mb^m$ won't be accepted.

$\delta (a,a,aa)$

$\delta (b,a,\lambda)$

Accept if we get the $y$ on stack at the end of the input. I don't know if such assumptions and operations are allowed on a PDA. In any case, how do I represent the above language in a single state PDA?

Regarding accessing two elements from top prior to any operation: I would think of $\delta(a,xy,ay)$ as $\delta(a,x,M)$, $\delta(y,M,N)$, $\delta(a,N,ay)$.

$\endgroup$
2
  • $\begingroup$ If there is any confusion in the question, then please ask in comments. I've not been able to get a clear idea about this concept and need help with this one. I study on my own and do not have the luxury of an instructor. $\endgroup$
    – aste123
    Oct 9, 2016 at 19:15
  • $\begingroup$ @mvw a^nb^n is a context free language. So it has a grammar also. I just edited the question from CFG to CFL. That's what i meant actually because I've been creating the PDA directly from definition of the language instead of creating the grammar first. $\endgroup$
    – aste123
    Oct 9, 2016 at 19:21

1 Answer 1

Reset to default
1
$\begingroup$

In the definition of a PDA with one state, you can read only the top most element of the stack. Thus you cannot read $xy$ in your first transition. (it is actually equivalent but unless you state it the PDA read only 1 element).

Moreover I don't see how the xy allow you to disregard for example $a^2b^1a^3b^4$?

Forget your $y$. Say that the initial stack symbol is $x$. You want to remember the number of a you read before reading the same number of $b$. what you can do is: when your read a $a$ and $x$ is on the top of the stack push a $A$ and $x$ on top of it. You can do that with a transition $\delta(a,x,xA)$.

At some point you choose non deterministically that you read the last $a$, so you don't push $x$ again. You have the transition $\delta(a,x,A)$.

Now you have a stack containing only $A$'s and you just have to pop them each time you see a $b$. hence $\delta(b,A,\lambda)$.

Accept with the empty stack.

Notice that you cannot read $b$ when $x$ is on top, hence you always start be reading multiple $a$. Also you cannot read $a$ when $x$ is not on top, hence after the last $a$ you read only $b$.

$\endgroup$
3
  • $\begingroup$ The definition of a stack allows us to see any number of symbols from the top (without jumps). Then why can't we access two elements from top prior to any operation? I'd think of $\delta(a,xy,ay)$ as $\delta(a,x,M)$, $\delta(y,M,N)$, $\delta(a,N,ay)$. The PDA you suggested doesn't seem to accept the empty string. Can you tell me what changes are necessary in it? Please also tell are we assuming the stack already contains $x$ or do we get an empty stack and push $x$ as the first symbol. If we do so, then doesn't it mean that empty string would be accepted in every such PDA? $\endgroup$
    – aste123
    Oct 13, 2016 at 3:35
  • $\begingroup$ @aste123 Ok for the definition with multiple reading (the two definitions are equivalent). I'm not sure of what you mean by "I'd think of [...]", but there exist reduction from one definition to the other if that is what you attempted to do. In order to accept the empty string you can change the transition $\delta(a,x,A)$ by a transition $\delta(\lambda,x,\lambda)$, hence you can pop the x at any time. $\endgroup$
    – wece
    Oct 13, 2016 at 6:55
  • $\begingroup$ @aste123 We are assuming that the stack already contain $x$ ($x$ is called the initial stack symbol). We cannot allow to push $x$ from the empty stack otherwise for any word $w$ accepted the word $ww$ would also be accepted. $\endgroup$
    – wece
    Oct 13, 2016 at 6:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .