MHB 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 $$\{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.

 

[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 ,<br /> x\rightarrow ax ,<br /> y\rightarrow by ,<br /> x\rightarrow \varnothing ,<br /> y\rightarrow \varnothing<br />
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 ,<br /> x\rightarrow ax ,<br /> y\rightarrow by ,<br /> x\rightarrow \varnothing ,<br /> y\rightarrow \varnothing<br />
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 ,<br /> X\rightarrow aaX ,<br /> Y\rightarrow bY ,<br /> X\rightarrow \varnothing ,<br /> Y\rightarrow \varnothing<br />

or like that:
S\rightarrow aXYb ,<br /> X\rightarrow aX ,<br /> Y\rightarrow bbY ,<br /> X\rightarrow \varnothing ,<br /> Y\rightarrow \varnothing<br />

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 ,<br /> X\rightarrow aaX ,<br /> Y\rightarrow bY ,<br /> X\rightarrow \varnothing ,<br /> Y\rightarrow \varnothing<br />

or like that:
S\rightarrow aXYb ,<br /> X\rightarrow aX ,<br /> Y\rightarrow bbY ,<br /> X\rightarrow \varnothing ,<br /> Y\rightarrow \varnothing<br />

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![/color] (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!

 

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