MHB Show that language is accepted by a pushdown automaton

[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!

 

[Evgeny.Makarov]

Because I am not really familiar with the construction of pushdown automata!

Deterministic pushdown automata! That's not quite the same thing as regular (nondeterministic) pushdown automata.

Let's say that I am 80% sure the idea of this exercise is to construct an automaton, and I wouldn't be able to help you do this any other way because this would require me to do some reviewing.

 

[evinda]

Deterministic pushdown automata! That's not quite the same thing as regular (nondeterministic) pushdown automata.

Let's say that I am 80% sure the idea of this exercise is to construct an automaton, and I wouldn't be able to help you do this any other way because this would require me to do some reviewing.

Could you give me an example of a Deterministic pushdown automaton?

- - - Updated - - -

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

Is the the pushdown automaton we talked about deterministic?

 

[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 think it is deterministic,or am I wrong?I will try to change that what you said me and I will tell you what I have tried.. :)

 

[I like Serena]

Could you give me an example of a Deterministic pushdown automaton?

The example from wiki I gave earlier in this thread is actually a deterministic pushdown automaton.
That is because whenever the automaton reads a symbol from the input, the state changes are uniquely determined. There is never a choice between 2 different paths.

- - - Updated - - -
Is the the pushdown automaton we talked about deterministic?

I think it is deterministic,or am I wrong?I will try to change that what you said me and I will tell you what I have tried.. :)

Your last pushdown automaton is not deterministic.
Right at the beginning there already is a choice between 2 paths that both accept an $a$.

I would suggest to first try to make a deterministic pushdown automaton for $a^{n+m}b^n$ with $m>0$.

 

[Evgeny.Makarov]

Could you give me an example of a Deterministic pushdown automaton?

Besides the responses given above, I would if you convince me that this (that is, posting information that is readily available online, let alone in textbooks and lecture notes) is the optimal way to proceed. Why should we type and post information that has been already composed and verified by people who are more competent, like book authors? And why do you keep asking questions as if you have no access to educational materials? If indeed you have no textbook and no access to lecture notes, then it's not a way to learn something. If you have access but are unwilling to dig in and prefer to rely on common sense, then how can you discover subtler issues, like the fact that at least one book has slightly different definitions of accepted languages for regular pushdown and deterministic pushdown automata?

 

[evinda]

The example from wiki I gave earlier in this thread is actually a deterministic pushdown automaton.
That is because whenever the automaton reads a symbol from the input, the state changes are uniquely determined. There is never a choice between 2 different paths.Your last pushdown automaton is not deterministic.
Right at the beginning there already is a choice between 2 paths that both accept an $a$.

I would suggest to first try to make a deterministic pushdown automaton for $a^{n+m}b^n$ with $m>0$.

I tried to make a deterministic pushdown automaton for $a^{n+m}b^n$ with $m>0$ .Could you tell me if it is right?

View attachment 1841

 

[I like Serena]

I tried to make a deterministic pushdown automaton for $a^{n+m}b^n$ with $m>0$ .Could you tell me if it is right?

I'm afraid it's not.
- It is not deterministic, since reading an $a$ can both lead to a state shift from $p$ to $p$, as well as a shift from $p$ to $q$.
- It allows to read exactly as many $b$ as it has read $a$, meaning it does not fit the language.

 

[evinda]

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 $$\{0^n1^n \mid n \ge 0 \}$$ by final state:

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

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

$$(p,0,Z,p,AZ)$$,
$$(p,0,A,p,AA)$$,
$$(p,\epsilon,Z,q,Z)$$,
$$(p,\epsilon,A,q,A)$$,
$$(q,1,A,q,\epsilon)$$, and
$$(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.

I have tried to describe the deterministic pushdown automaton,using the grammar of the Post 14:
(p, \varepsilon , \varepsilon ), (q, S)
(q, \varepsilon , S), (q, AB)
(q, \varepsilon , S), (q, XY)
(q, \varepsilon , A), (q, aAb)
(q, \varepsilon , A), (q, \varepsilon )
(q, \varepsilon , B), (q, bB)
(q, \varepsilon , B), (q, b)
(q, \varepsilon , X), (q, aX)
(q, \varepsilon , X), (q, a)
(q, \varepsilon , Y), (q, aYb)
(q, \varepsilon , Y), (q, \varepsilon )
(q, a, a), (q, \varepsilon )
(q, b, b), (q, \varepsilon )

Could you tell me if it's right?

 

[I like Serena]

I have tried to describe the deterministic pushdown automaton,using the grammar of the Post 14:
(p, \varepsilon , \varepsilon ), (q, S)
(q, \varepsilon , S), (q, AB)
(q, \varepsilon , S), (q, XY)
(q, \varepsilon , A), (q, aAb)
(q, \varepsilon , A), (q, \varepsilon )
(q, \varepsilon , B), (q, bB)
(q, \varepsilon , B), (q, b)
(q, \varepsilon , X), (q, aX)
(q, \varepsilon , X), (q, a)
(q, \varepsilon , Y), (q, aYb)
(q, \varepsilon , Y), (q, \varepsilon )
(q, a, a), (q, \varepsilon )
(q, b, b), (q, \varepsilon )

Could you tell me if it's right?

You have multiple transitions in state q on the same input and the same symbol on the top of the stack.
That means it is not deterministic.

Or did you want to know if it matches a non-deterministic pushdown automaton?

In that case, in the initial state (presumably p), there should already be a symbol on the stack, which would be S (making the state p redundant).

Your automaton seems fine otherwise, although you should also specify at the very least the initial state, the initial stack symbol, and the set of final states.

 

[evinda]

You have multiple transitions in state q on the same input and the same symbol on the top of the stack.
That means it is not deterministic.

Or did you want to know if it matches a non-deterministic pushdown automaton?

In that case, in the initial state (presumably p), there should already be a symbol on the stack, which would be S (making the state p redundant).

Your automaton seems fine otherwise, although you should also specify at the very least the initial state, the initial stack symbol, and the set of final states.

I wanted to write the description of the deterministic PDA,but I haven't really understood what I have to change.Could you explain it further to me?

 

[evinda]

$$S \to aSb\ |\ aA\ |\ bB$$
$$A \to aA\ |\ \varnothing$$
$$B \to bB\ |\ \varnothing$$

I could also show that the language is accepted by a deterministic PDA,showing that a deterministic grammar generates it..Right??Is the grammar above deterministic?

 

[evinda]

How can I check if the grammar is deterministic or not?

 

[Evgeny.Makarov]

Do your sources cover deterministic context-free grammars?

 

[evinda]

Do your sources cover deterministic context-free grammars?

In my textbook,there is nothing about deterministic context-free grammars..I have also searched at some sites,but I haven't found something,that could help me to understand it..

 

[Evgeny.Makarov]

The textbook by Lewis and Papadimitriou also does not have anything on deterministic context-free grammars, though it has a section on deterministic PDAs. Even Wikipedia, which has a detailed article on regular context-free grammars, does not give the definition of deterministic CFGs, though it has a small article about them. So, do you plan to undertake a little research project to study deterministic CFGs as a part of solving one problem?

 

[evinda]

The textbook by Lewis and Papadimitriou also does not have anything on deterministic context-free grammars, though it has a section on deterministic PDAs. Even Wikipedia, which has a detailed article on regular context-free grammars, does not give the definition of deterministic CFGs, though it has a small article about them. So, do you plan to undertake a little research project to study deterministic CFGs as a part of solving one problem?

I try to describe the function of the PDA:
For each $a$ that is read,we put an $a$ in the stack.
When,the first $b$ is read,we begin to pop an $a$ for each $b$.
But..how can the stack get empty,if we know that the number of $a$ that is read shouldn't be equal to the number of $b$ ??

 

[evinda]

I try to describe the function of the PDA:
For each $a$ that is read,we put an $a$ in the stack.
When,the first $b$ is read,we begin to pop an $a$ for each $b$.
But..how can the stack get empty,if we know that the number of $a$ that is read shouldn't be equal to the number of $b$ ??

Is it maybe like that:when the stack gets empty,we will have an accepting state and then it will be allowed that the automaton reads more $b$s??But,if it is like that,isn't it possible that the number of $a$ is equal to the number of $b$ ??

 

[I like Serena]

I try to describe the function of the PDA:
For each $a$ that is read,we put an $a$ in the stack.
When,the first $b$ is read,we begin to pop an $a$ for each $b$.
But..how can the stack get empty,if we know that the number of $a$ that is read shouldn't be equal to the number of $b$ ??

Is it maybe like that:when the stack gets empty,we will have an accepting state and then it will be allowed that the automaton reads more $b$s??But,if it is like that,isn't it possible that the number of $a$ is equal to the number of $b$ ??

Indeed.
So if the stack gets empty (except for the initial stack symbol), we should make sure we're not in an accepting state.
Either we have to accept the string before that happens, or we have to make sure we read more $b$'s after it happens.

 

[evinda]

Indeed.
So if the stack gets empty (except for the initial stack symbol), we should make sure we're not in an accepting state.
Either we have to accept the string before that happens, or we have to make sure we read more $b$'s after it happens.

Nice...Thank you very much for your help! :D