Show that language is accepted by a pushdown automaton

evinda

Well-known member
MHB Site Helper
Hello again!!!

I have to show that the language $$\left \{ w\epsilon \left \{ a,b \right \}^{*}:w=a^{m}b^{n},m\neq n \right \}$$ is accepted by a pushdown automaton.
Can I use the sentence "A string is accepted by a pushdown automaton if,starting with an empty stack,there is a path through the automaton such that the automaton stops in an accepting state after the entire string has been read." to show it?

Klaas van Aarsen

MHB Seeker
Staff member
Hello again!!!

I have to show that the language $$\left \{ w\epsilon \left \{ a,b \right \}^{*}:w=a^{m}b^{n},m\neq n \right \}$$ is accepted by a pushdown automaton.
Can I use the sentence "A string is accepted by a pushdown automaton if,starting with an empty stack,there is a path through the automaton such that the automaton stops in an accepting state after the entire string has been read." to show it?
Hey again!!

I have just refreshed my knowledge about pushdown automatons.
Apparently it starts with an initial stack symbol.
So I think the proper sentence should be: "A string is accepted by a pushdown automaton if, starting with the initial stack symbol, there is a path through the automaton such that the automaton stops in an accepting state after the entire string has been read."

evinda

Well-known member
MHB Site Helper
Hey again!!

I have just refreshed my knowledge about pushdown automatons.
Apparently it starts with an initial stack symbol.
So I think the proper sentence should be: "A string is accepted by a pushdown automaton if, starting with the initial stack symbol, there is a path through the automaton such that the automaton stops in an accepting state after the entire string has been read."
And how can I show it?Do I have to draw the pushdown automaton?

Klaas van Aarsen

MHB Seeker
Staff member
And how can I show it?Do I have to draw the pushdown automaton?
That would be my preferred way.

evinda

Well-known member
MHB Site Helper
That would be my preferred way.
Ok,I will try it!!! Except from that,is there also an other way,how I could show that the language is accepted by a pushdown automaton?

Klaas van Aarsen

MHB Seeker
Staff member
Ok,I will try it!!! Except from that,is there also an other way,how I could show that the language is accepted by a pushdown automaton?
You could also formally specify a pushdown automaton (PDA).

Here's an example from wiki:

The following is the formal description of the PDA which recognizes the language $$\displaystyle \{0^n1^n \mid n \ge 0 \}$$ by final state:

$$\displaystyle M=(Q,\ \Sigma,\ \Gamma,\ \delta, \ p,\ Z, \ F)$$, where
$$\displaystyle Q = \{ p,q,r \}$$
$$\displaystyle \Sigma = \{0, 1\}$$
$$\displaystyle \Gamma = \{A, Z\}$$
$$\displaystyle q_{0} = p$$
$$\displaystyle F = \{r\}$$

$$\displaystyle \delta$$ consists of the following six instructions:

$$\displaystyle (p,0,Z,p,AZ)$$,
$$\displaystyle (p,0,A,p,AA)$$,
$$\displaystyle (p,\epsilon,Z,q,Z)$$,
$$\displaystyle (p,\epsilon,A,q,A)$$,
$$\displaystyle (q,1,A,q,\epsilon)$$, and
$$\displaystyle (q,\epsilon,Z,r,Z)$$.​

Such a specification is much harder to read or to verify.
Note that the example on wiki also contains a picture that contains everything that is needed.

Evgeny.Makarov

Well-known member
MHB Math Scholar
Can I use the sentence "A string is accepted by a pushdown automaton if,starting with an empty stack,there is a path through the automaton such that the automaton stops in an accepting state after the entire string has been read." to show it?
There are different definitions of when a word is accepted. For example. some of them require that the stack is empty in the end while others don't. You should check your sources.

A language is accepted by a pushdown automaton iff it is context-free, so you could also construct a grammar to show that your language is accepted by a pushdown automaton. The ultimate determination is made by the one who designed the problem, but I think that if a question refers to a pushdown automaton, then such automaton has to be constructed.

evinda

Well-known member
MHB Site Helper
There are different definitions of when a word is accepted. For example. some of them require that the stack is empty in the end while others don't. You should check your sources.

A language is accepted by a pushdown automaton iff it is context-free, so you could also construct a grammar to show that your language is accepted by a pushdown automaton. The ultimate determination is made by the one who designed the problem, but I think that if a question refers to a pushdown automaton, then such automaton has to be constructed.

I have tried to construct a grammar,to show that the language is accepted by a pushdown automaton.That's what I got:
$$S\rightarrow axyb , x\rightarrow ax , y\rightarrow by , x\rightarrow \varnothing , y\rightarrow \varnothing$$
Is it right?Or am I wrong?

Klaas van Aarsen

MHB Seeker
Staff member
I have tried to construct a grammar,to show that the language is accepted by a pushdown automaton.That's what I got:
$$S\rightarrow axyb , x\rightarrow ax , y\rightarrow by , x\rightarrow \varnothing , y\rightarrow \varnothing$$
Is it right?Or am I wrong?
Let's see...

\begin{array}{}S&\to& axyb \\
x &\to& \varnothing \\
y &\to& \varnothing
\end{array}

So $ab$ is accepted. Is that allowed?

Btw, perhaps you should use different casing (like $a$ and $X$) to visually distinguish terminals from non-terminals?

evinda

Well-known member
MHB Site Helper
Let's see...

\begin{array}{}S&\to& axyb \\
x &\to& \varnothing \\
y &\to& \varnothing
\end{array}

So $ab$ is accepted. Is that allowed?
Oh,you are right It should't be accepted!!!

- - - Updated - - -

Let's see...

\begin{array}{}S&\to& axyb \\
x &\to& \varnothing \\
y &\to& \varnothing
\end{array}

So $ab$ is accepted. Is that allowed?

Btw, perhaps you should use different casing (like $a$ and $X$) to visually distinguish terminals from non-terminals?
So,should it be like that:
$$S\rightarrow aXYb , X\rightarrow aaX , Y\rightarrow bY , X\rightarrow \varnothing , Y\rightarrow \varnothing$$

or like that:
$$S\rightarrow aXYb , X\rightarrow aX , Y\rightarrow bbY , X\rightarrow \varnothing , Y\rightarrow \varnothing$$

or something else?

Klaas van Aarsen

MHB Seeker
Staff member
Oh,you are right It should't be accepted!!!

- - - Updated - - -

So,should it be like that:
$$S\rightarrow aXYb , X\rightarrow aaX , Y\rightarrow bY , X\rightarrow \varnothing , Y\rightarrow \varnothing$$

or like that:
$$S\rightarrow aXYb , X\rightarrow aX , Y\rightarrow bbY , X\rightarrow \varnothing , Y\rightarrow \varnothing$$

or something else?
With both grammars I can still construct $ab$.

evinda

Well-known member
MHB Site Helper
With both grammars I can still construct $ab$.
And what could I change so that it cannot happen that m=n?

Klaas van Aarsen

MHB Seeker
Staff member
And what could I change so that it cannot happen that m=n?
Start with something like $S \to a S b$ which will allow a symmetric build-up.
Only allow it to terminate when there is an asymmetry in either $a$ or $b$.
So add for instance $S \to aA\ |\ Bb$.

evinda

Well-known member
MHB Site Helper
Start with something like $S \to a S b$ which will allow a symmetric build-up.
Only allow it to terminate when there is an asymmetry in either $a$ or $b$.
So add for instance $S \to aA\ |\ Bb$.
I looked again the exercise and realized that the language is the union of the two languages: $\displaystyle \left \{ w\epsilon \left \{ a,b \right \}^{*}:w=a^{m}b^{n},m>n\right \}$ and $\displaystyle \left \{ w\epsilon \left \{ a,b \right \}^{*}:w=a^{m}b^{n},m<n\right \}$ .So is the grammar the following?
$$S \to S_{1}|S_{2}$$
$$S_{1} \to AB$$
$$A\to aAb| \varnothing$$
$$B\to bB|b$$
$$S_{2}\to XY$$
$$X\to aX|a$$
$$Y\to aYb|\varnothing$$

Klaas van Aarsen

MHB Seeker
Staff member
I looked again the exercise and realized that the language is the union of the two languages: $\displaystyle \left \{ w\epsilon \left \{ a,b \right \}^{*}:w=a^{m}b^{n},m>n\right \}$ and $\displaystyle \left \{ w\epsilon \left \{ a,b \right \}^{*}:w=a^{m}b^{n},m<n\right \}$ .So is the grammar the following?
$$S \to S_{1}|S_{2}$$
$$S_{1} \to AB$$
$$A\to aAb| \varnothing$$
$$B\to bB|b$$
$$S_{2}\to XY$$
$$X\to aX|a$$
$$Y\to aYb|\varnothing$$
Looks good!

But... I thought you were going to draw a pushdown automaton. You said so...

Btw... how do you feel about an avatar picture?

evinda

Well-known member
MHB Site Helper
There are different definitions of when a word is accepted. For example. some of them require that the stack is empty in the end while others don't. You should check your sources.

A language is accepted by a pushdown automaton iff it is context-free, so you could also construct a grammar to show that your language is accepted by a pushdown automaton. The ultimate determination is made by the one who designed the problem, but I think that if a question refers to a pushdown automaton, then such automaton has to be constructed.
The exercise is:"Show that the following language(the one that I wrote at the first post) is accepted by a pushdown automaton".So,could I just say that the language is accepted by a pushdown automaton,because of the fact that there is a contextfree grammar that generates it?

- - - Updated - - -

Looks good!

But... I thought you were going to draw a pushdown automaton. You said so...
I will try to draw the pushdown automaton and I'll tell you later what I have done!!!

- - - Updated - - -

Start with something like $S \to a S b$ which will allow a symmetric build-up.
Only allow it to terminate when there is an asymmetry in either $a$ or $b$.
So add for instance $S \to aA\ |\ Bb$.
Is there also an other grammar that generates the language,than the grammar that I wrote at my previous post?

Klaas van Aarsen

MHB Seeker
Staff member
The exercise is:"Show that the following language(the one that I wrote at the first post) is accepted by a pushdown automaton".So,could I just say that the language is accepted by a pushdown automaton,because of the fact that there is a contextfree grammar that generates it?
Yes.

- - - Updated - - -
I will try to draw the pushdown automaton and I'll tell you later what I have done!!!
Can I see the drawing?
I like pictures!

- - - Updated - - -
Is there also an other grammar that generates the language,than the grammar that I wrote at my previous post?
Of course.
For instance:
$$S \to aSb\ |\ aA\ |\ bB$$
$$A \to aA\ |\ \varnothing$$
$$B \to bB\ |\ \varnothing$$

Evgeny.Makarov

Well-known member
MHB Math Scholar
Is there also an other grammar that generates the language,than the grammar that I wrote at my previous post?
Yes.

N. had the habit of simply writing answers to homework assignments on the board (the method of solution being, of course, obvious) when he was asked how to solve problems. One time one of his students tried to get more helpful information by asking if there was another way to solve the problem. N. looked blank for a moment, thought, and then answered, "Yes".

evinda

Well-known member
MHB Site Helper

- - - Updated - - -

Can I see the drawing?
I like pictures!
I wanted to draw a pushdown automaton,but I haven't found a lot of examples and I haven't really understood,how such automata can be drawn.
Could you explain me?
[/QUOTE]

Of course.
For instance:
$$S \to aSb\ |\ aA\ |\ bB$$
$$A \to aA\ |\ \varnothing$$
$$B \to bB\ |\ \varnothing$$
Great!!Thank you!!!

Klaas van Aarsen

MHB Seeker
Staff member
I wanted to draw a pushdown automaton,but I haven't found a lot of examples and I haven't really understood,how such automata can be drawn.
Could you explain me?
Here's one for a pushdown automaton that accepts $0^n1^n$.

We start in state $\color{brown}p$ where symbol $\color{green}0$ is accepted.
On the stack we track the number of $\color{green}0$s that we accepted as the number of $\color{blue}A$s.

When a symbol $\color{green}0$ comes in while the stack still contains the initial stack symbol $\color{blue}Z$, $\color{blue}A$ is pushed onto the stack ($\color{blue}Z$ is replaced by $\color{blue}{AZ}$).
When another symbol $\color{green}0$ comes in while the top of the stack contains $\color{blue}A$, another $\color{blue}A$ is pushed onto the stack ($\color{blue}A$ is replaced by $\color{blue}{AA}$).

And so on...

Aha! You have a mathy avatar now. Good!

evinda

Well-known member
MHB Site Helper
Here's one for a pushdown automaton that accepts $0^n1^n$.

We start in state $\color{brown}p$ where symbol $\color{green}0$ is accepted.
On the stack we track the number of $\color{green}0$s that we accepted as the number of $\color{blue}A$s.

When a symbol $\color{green}0$ comes in while the stack still contains the initial stack symbol $\color{blue}Z$, $\color{blue}A$ is pushed onto the stack ($\color{blue}Z$ is replaced by $\color{blue}{AZ}$).
When another symbol $\color{green}0$ comes in while the top of the stack contains $\color{blue}A$, another $\color{blue}A$ is pushed onto the stack ($\color{blue}A$ is replaced by $\color{blue}{AA}$).
And so on...
I have tried this,but I don't think that it is right..I haven't really understood the stacks

Klaas van Aarsen

MHB Seeker
Staff member
I have tried this,but I don't think that it is right..I haven't really understood the stacks
The problem here is that for instance $ab$ is accepted.
If we take the upper branch in your automaton and accept $a$ once, we can then make a shift to the next state while accepting $b$, and then let the automaton finish.

We need a stack to keep track how many $a$'s were accepted.
So in each transition, we do not only accept an input symbol, we also manipulate the stack.

Going back to the example I just gave (from wiki).
Here is how the stack would develop while reading the string $0011$.

Leftmost you see that the stack begins as
$$\begin{bmatrix}Z\end{bmatrix}$$

After reading the symbol $0$, an $A$ is pushed on top of it.
So we get the stack
$$\begin{bmatrix}A \\ Z \end{bmatrix}$$

After reading another symbol $0$, another $A$ is pushed on top, yielding
$$\begin{bmatrix}A \\ A \\ Z \end{bmatrix}$$
Note that there are as many $A$'s on the stack as we have read $0$'s.

And so on.

evinda

Well-known member
MHB Site Helper
The problem here is that for instance $ab$ is accepted.
If we take the upper branch in your automaton and accept $a$ once, we can then make a shift to the next state while accepting $b$, and then let the automaton finish.

We need a stack to keep track how many $a$'s were accepted.
So in each transition, we do not only accept an input symbol, we also manipulate the stack.

Going back to the example I just gave (from wiki).
Here is how the stack would develop while reading the string $0011$.

Leftmost you see that the stack begins as
$$\begin{bmatrix}Z\end{bmatrix}$$

After reading the symbol $0$, an $A$ is pushed on top of it.
So we get the stack
$$\begin{bmatrix}A \\ Z \end{bmatrix}$$

After reading another symbol $0$, another $A$ is pushed on top, yielding
$$\begin{bmatrix}A \\ A \\ Z \end{bmatrix}$$
Note that there are as many $A$'s on the stack as we have read $0$'s.

And so on.
I wish you a happy new year!!!!!

I have tried again to draw the pushdown automaton.That's what I did:

Klaas van Aarsen

MHB Seeker
Staff member
I have tried again to draw the pushdown automaton.That's what I did:
Looking good!

One problem (or rather 2): the strings $aa{}^*$ and $bb{}^*$ are not accepted while they should.

I wish you a happy new year!!!!!
HAPPY NEW YEAR!!

evinda

Well-known member
MHB Site Helper
Looking good!

One problem (or rather 2): the strings $aa{}^*$ and $bb{}^*$ are not accepted while they should.
And what could I change,so that the strings $aa{}^*$ and $bb{}^*$ get accepted?