17. An alternative to Definition 7.2 for language acceptance is to require the
stack to be empty when the end of the input string is reached. Formally, an
npda M is said to accept the language N (M) by empty stack if
where p is any element in Q. Show that this notion is effectively equivalent
to Definition 7.2, in the sense that for any npda M there exists an npda
such that L (M) = N ( ), and vice versa.
7.2 Pushdown Automata and Context-Free
Languages
In the examples of the previous section, we saw that pushdown automata exist
for some of the familiar context-free languages. This is no accident. There is a
general relation between context-free languages and nondeterministic pushdown
accepters that is established in the next two major results. We will show that for
every context-free language there is an npda that accepts it, and conversely, that
the language accepted by any npda is context-free.
Pushdown Automata for Context-Free Languages
We first show that for every context-free language there is an npda that accepts
it. The underlying idea is to construct an npda that can, in some way, carry out a
leftmost derivation of any string in the language. To simplify the argument a
little, we assume that the language is generated by a grammar in Greibach
normal form.
The pda we are about to construct will represent the derivation by keeping
the variables in the right part of the sentential form on its stack, while the left
part, consisting entirely of terminals, is identical with the input read. We begin
by putting the start symbol on the stack. After that, to simulate the application of
a production A → ax, we must have the variable A on top of the stack and the
terminal a as the input symbol. The variable on the stack is removed and
replaced by the variable string x. What δ should be to achieve this is easy to see.
Before we present the general argument, let us look at a simple example.
stack to be empty when the end of the input string is reached. Formally, an
npda M is said to accept the language N (M) by empty stack if
where p is any element in Q. Show that this notion is effectively equivalent
to Definition 7.2, in the sense that for any npda M there exists an npda
such that L (M) = N ( ), and vice versa.
7.2 Pushdown Automata and Context-Free
Languages
In the examples of the previous section, we saw that pushdown automata exist
for some of the familiar context-free languages. This is no accident. There is a
general relation between context-free languages and nondeterministic pushdown
accepters that is established in the next two major results. We will show that for
every context-free language there is an npda that accepts it, and conversely, that
the language accepted by any npda is context-free.
Pushdown Automata for Context-Free Languages
We first show that for every context-free language there is an npda that accepts
it. The underlying idea is to construct an npda that can, in some way, carry out a
leftmost derivation of any string in the language. To simplify the argument a
little, we assume that the language is generated by a grammar in Greibach
normal form.
The pda we are about to construct will represent the derivation by keeping
the variables in the right part of the sentential form on its stack, while the left
part, consisting entirely of terminals, is identical with the input read. We begin
by putting the start symbol on the stack. After that, to simulate the application of
a production A → ax, we must have the variable A on top of the stack and the
terminal a as the input symbol. The variable on the stack is removed and
replaced by the variable string x. What δ should be to achieve this is easy to see.
Before we present the general argument, let us look at a simple example.