Show that language is accepted by a pushdown automaton

[evinda]

Hello again! (Wasntme)

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?

 

[I like Serena]

Hello again! (Wasntme)

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! (Smirk)

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]

Hey again! (Smirk)

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?

 

[I like Serena]

And how can I show it?Do I have to draw the pushdown automaton?

That would be my preferred way.

 

[evinda]

That would be my preferred way.

Ok,I will try it! :D Except from that,is there also an other way,how I could show that the language is accepted by a pushdown automaton?

 

[I like Serena]

Ok,I will try it! :D 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]

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]

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?

 

[I like Serena]

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]

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?

 

[I like Serena]

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]

With both grammars I can still construct $ab$.

And what could I change so that it cannot happen that m=n?

 

[I like Serena]

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]

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

 

[I like Serena]

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]

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! :D

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

 

[I like Serena]

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! :D

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]

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]

Yes.

:D ;)

- - - 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! :)

 

[I like Serena]

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! :D

 

[evinda]

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
View attachment 1816

 

[I like Serena]

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]

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:
View attachment 1818

 

[I like Serena]

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! (Angel)

 

[evinda]

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?

 

[I like Serena]

And what could I change,so that the strings $aa{}^*$ and $bb{}^*$ get accepted?

Well, you could for instance replace the first transition $a;Z/AZ$ by $\varepsilon;Z/Z$ and also the first transition $b;Z/BZ$ by $\varepsilon;Z/Z$.

 

[evinda]

Well, you could for instance replace the first transition $a;Z/AZ$ by $\varepsilon;Z/Z$ and also the first transition $b;Z/BZ$ by $\varepsilon;Z/Z$.

So,should it be like that?
View attachment 1820

 

[I like Serena]

So,should it be like that?

Yep. All good now. (Priidu)

 

[evinda]

Yep. All good now. (Priidu)

Nice...Thank you very much! (Happy)

 

[I like Serena]

Nice...Thank you very much! (Happy)

Oh wait!
The PDA correctly accepts $a^nb^nb^+$ in the upper branch.
However, in the lower branch it accepts $b^na^na^+$... that is not right.
It should accept $a^+a^nb^n$.

 

[evinda]

Oh wait!
The PDA correctly accepts $a^nb^nb^+$ in the upper branch.
However, in the lower branch it accepts $b^na^na^+$... that is not right.
It should accept $a^+a^nb^n$.

I have changed it :) Is it right now?
View attachment 1822

 

[I like Serena]

I have changed it :) Is it right now?

Let me take a more careful look this time.

In the upper branch we can read $\varepsilon$ and leave the stack as $z$.
Then, in the next state, we can read $a$, but only if there is an $a$ on the top of the stack... but the first time there is a $z$ on top, so we're stuck!

In the lower branch we can now read $a^+$, leaving a $z$ on top of the stack, which is good.
Then we're stuck again, because we can't move on as long as the $z$ is still on top of the stack.

When we're able to pass that blockage, there is one more hurdle.
We will have a stack full of $a$'s... and we can only move on if there is a $b$ on top of the stack, but they were never pushed onto the stack!

 

[evinda]

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.

I looked again at the exercise and saw that I have to show that the language is accepted by a deterministic pushdown automaton.So,can I just show that the language is context-free,or do I have to do something else??

 

[Evgeny.Makarov]

Not all context-free languages are accepted by deterministic pushdown automata. The easiest is probably to construct such automaton.

 

[evinda]

Not all context-free languages are accepted by deterministic pushdown automata. The easiest is probably to construct such automaton.

And is this the only way?Because I am not really familiar with the construction of pushdown automata!