Pushdown Automata

Nondeterministic Pushdown Automata

1
Topics

• Nondeterministic Pushdown Automata

• Pushdown Automata and Context-Free Languages
• Deterministic Pushdown Automata and Deterministic Context-free Languages
• Grammars for Deterministic Context-Free Languages

2
Nondeterministic Pushdown
Automata

3
Automata for Context-free Languages?

• We know that for regular languages, we have DFAs and NFAs which are equivalent to
them.

• However, finite automata have limitations, mostly due to bounded memory.

n n
• L = {a b : n ≥ 0}
• We have to remember the number of a's, then match the number of b's to it.
R
• L = {ww : w ∈ {a, b}*}
R
• We have to match each symbol for w and w .
• These cannot be done with finite automata, whether deterministic or nondeterministic.
4
Pushdown Automata

• In Pushdown Automata (PDA), we

have a stack as storage, which can
have infinite length by definition.

• Control Unit (CU) reads a symbol

from the input file one by one.

• It also changes the contents of the

stack during the process.

• Each move of the CU is determined

by the current input symbol & the
symbol on top of the stack.

5
Pushdown Automata
Definition 7.1

• A Nondeterministic Pushdown Automata (NPDA) is defined by the septuple

• M = (Q, Σ, Γ, δ, q0, z, F),
• where
• Q, Σ, q0, F are similar to DFAs,
• Γ is a finite set of symbols called the stack alphabet,
• z ∈ Γ is the stack start symbol,
• δ : Q × (Σ ∪ {λ}) × Γ → set of finite subsets of Q × Γ* is the transition function.
6
Pushdown Automata
Example 7.1

• Suppose the set of transition rules of an NPDA contains

• δ(q1, a, b) = {(q2, cd), (q3, λ)}.
• In case the CU is in state q1, and the input symbol is a, and the top stack symbol is b,
• the CU goes to q2, and string cd replaces b in the stack, or
• the CU goes to q3, and b is removed from the stack.
• We assume that the insertion of a string into a stack is done symbol by symbol from
the right end.

7
Pushdown Automata
Example 7.2

• Consider an npda with

• Q = {q0, q1, q2, q3}, Σ = {a, b}, Γ = {0,1},
• z = 0, F = {q3}, with initial state q0 and
• δ(q0, a,0) = {(q1,10), (q3, λ)}, δ(q0, λ,0) = {(q3, λ)},
• δ(q1, a,1) = {(q1,11)}, δ(q1, b,1) = {(q2, λ)},
• δ(q2, b,1) = {(q2, λ)}, δ(q2, λ,0) = {(q3, λ)}.
8
Pushdown Automata
Example 7.2

• Unspecified transitions are to the null sets, and represent dead configuration.
• δ(q0, a,0) = {(q1,10), (q3, λ)}, δ(q0, λ,0) = {(q3, λ)},
• δ(q1, a,1) = {(q1,11)}, δ(q1, b,1) = {(q2, λ)},
• δ(q2, b,1) = {(q2, λ)}, δ(q2, λ,0) = {(q3, λ)}.
• This NPDA accepts the language
n n
• L = {a b : n ≥ 0} ∪ {a}.

9
Pushdown Automata
Example 7.3

• The NPDA in Example 7.2 is represented by the transition graph in Figure 7.2.
• δ(q0, a,0) = {(q1,10), (q3, λ)},
• δ(q0, λ,0) = {(q3, λ)},
• δ(q1, a,1) = {(q1,11)},
• δ(q1, b,1) = {(q2, λ)},
• δ(q2, b,1) = {(q2, λ)},
• δ(q2, λ,0) = {(q3, λ)}. Figure 7.2

10
Instantaneous Description

• The triplet
• (q, w, u), where
• q is the state of the CU,
• w is the unread part of the input string, and
• u is the stack content
• is called an instantaneous description of a pushdown automaton.

11
Instantaneous Description

• A move from one instantaneous description to another will be denoted by the symbol ⊢
(turnstile).

• (q1, aw, bx) ⊢ (q2, w, yx) is possible iff.

• (q2, y) ∈ δ(q1, a, b).
• Moves involving an arbitrary number of steps will be denoted by ⊢*.
• The expression (q1, w1, x1) ⊢* (q2, w2, x2)
• indicates a possible configuration change over a number of steps.
• We can distinguish different automata using ⊢M1, ⊢M2, etc.
12
The Language Accepted by Pushdown Automata
Definition 7.2

• Let M = (Q, Σ, Γ, δ, q0, z, F) be an NPDA.

• The language accepted by M is the set
• L(M) = {w ∈ Σ* : (q0, w, z) ⊢*M (p, λ, u), p ∈ F, u ∈ Γ*}.
• This is the set of all strings that can put M into a final state at the end of the
string.

• Note that the final stack content u is irrelevant.

13
The Language Accepted by Pushdown Automata
Example 7.4
aabbab
• Construct an NPDA for the language
• L = {w ∈ {a, b}* : na(w) = nb(w)}. z

• For this language, we only need to count the number of a's and b's.
• In order to do that, we can insert a counter symbol into the stack.
• Whenever we encounter a, we put 0, and for b, we pop up 0 from the stack.

14
The Language Accepted by Pushdown Automata
Example 7.4

• How about there exists more b's than a's from the beginning?
• We don't have 0s to pop from the stack.
• We can leverage another symbol 1 to express such cases.
• These 1s will be matched against a's later.
bbaaab

15
The Language Accepted by Pushdown Automata
Example 7.4

• Figure 7.3 is the transition graph for the NPDA.

• For the string baab, the NPDA moves as the following.
• (q0, baab, z) ⊢ (q0, aab,1z) ⊢ (q0, ab, z)
• ⊢ (q0, b,0z) ⊢ (q0, λ, z) ⊢ (qf , λ, z).

Figure 7.3
16
The Language Accepted by Pushdown Automata
Example 7.5

• To construct an NPDA for accepting the language

R +
• L = {ww : w ∈ {a, b} },
• we can use LIFO (Last In, First Out) characteristic of the stack.
• First we put the first half of a string to the stack,
• then we compare the symbols for the latter half with the contents in the stack.
• The key difficulty is that we do not know the middle of the string.
• Note that NPDAs do not have features to compute the length of an input string.
17
The Language Accepted by Pushdown Automata
Example 7.5

• We can use nondeterministic feature of NPDAs to solve this issue.

• M = (Q, Σ, Γ, δ, q0, z, F), where
• Q = {q0, q1, q2}, Σ = {a, b}, Γ = {a, b, z}, F = {q2}.
• Here are the transitions to push w on the stack:
• δ(q0, a, a) = {(q0, aa)}, δ(q0, b, a) = {(q0, ba)},
• δ(q0, a, b) = {(q0, ab)}, δ(q0, b, b) = {(q0, bb)},
• δ(q0, a, z) = {(q0, az)}, δ(q0, b, z) = {(q0, bz)}.
18
The Language Accepted by Pushdown Automata
Example 7.5

• a set of transitions to guess the middle of the string:

• δ(q0, λ, a) = {(q1, a)}, δ(q0, λ, b) = {(q1, b)}.
R
• a set of transitions to match w against the stack:
• δ(q1, a, a) = {(q1, λ)}, δ(q1, b, b) = {(q1, λ)}.
• Final transition δ(q1, λ, z) = {(q2, z)} indicates the successful match.
• e.g.) abba
Two choices
• (q0, abba, z) ⊢ (q0, bba, az) ⊢ (q0, ba, baz) δ(q0, b, b) = {(q0, bb)}
• ⊢ (q1, ba, baz) ⊢ (q1, a, az) ⊢ (q1, λ, z) ⊢ (q2, z). δ(q0, λ, b) = {(q1, b)}
19
Pushdown Automata and
Context-Free Languages

20
Pushdown Automata for Context-Free Languages

• What we want to show here is that,

• for every context-free language, there is an NPDA that accepts it.
• The idea is that we can construct an NPDA that can carry out a leftmost
derivation of any string in the language.

• For simplicity, we will assume that the language is generated by a grammar

in GNF.

21
Pushdown Automata for Context-Free Languages
Example 7.6

• Construct a PDA that accepts the language generated by a grammar with

productions

• S → aSbb | a.
• Converting the grammar into GNF, we obtain
• S → aSA | a, A → bB, B → b.
• The corresponding automaton will have three states {q0, q1, q2} correspond
to S, A, and B, having q0 as the initial state and q2 be a final state.

22
Pushdown Automata for Context-Free Languages
Example 7.6

• S → aSA | a, A → bB, B → b.
• Here is the first step, which put S to the stack.
• Every derivation should start from the start symbol.
• δ(q0, λ, z) = {(q0, Sz)}.
• S → aSA will be simulated by removing S from the stack and replacing it with SA, while
reading a to the input.

• Also, S → a can be simulated by reading a and removing S.

• These two productions combined to δ(q1, a, S) = {(q1, SA), (q1, λ)}.
23
Pushdown Automata for Context-Free Languages
Example 7.6

• A → bB and B → b give
• δ(q1, b, A) = {(q1, B)},
• δ(q1, b, B) = {(q1, λ)} respectively.
• When we find the stack start symbol on top of the stack indicates the
completion of derivation.

• Then the PDA is put into the final state by

• δ(q1, λ, z) = {(q2, λ)}.
24
Pushdown Automata for Context-Free Languages
Theorem 7.1

• For any context-free language L, there exists an NPDA M s.t.

• L = L(M).
• Proof: If L is a λ-free context-free language, there exists a context-free
grammar in GNF.

• Let G = (V, T, S, P) be such a grammar.

• Then we can construct an NPDA that simulates leftmost derivations in this
grammar.

25
Pushdown Automata for Context-Free Languages
Theorem 7.1

• Here is the construction of M.

• M = ({q0, q1, qf}, T, V ∪ {z}, δ, q0, z, {qf}), where z ∉ V.
• The input alphabet of M = the terminals of G.
• The stack alphabet of M contains the variables of G.
• At start, δ includes δ(q0, λ, z) = {(q1, Sz)} (7.1) to put S into the stack.
• (q1, u) ∈ δ(q1, a, A) (7.2), whenever A → au, u ∈ V* is in P.
• Finally, δ(q1, λ, z) = {(qf , z)} (7.3), to get M into a final state.
26
Pushdown Automata for Context-Free Languages
Theorem 7.1

• To show that M accepts any w ∈ L(G), consider the partial leftmost derivation
• S ⇒* a1a2⋯an A1A2⋯Am ⇒ a1a2⋯anbB1⋯Bk A2⋯Am.
• After reading a1a2⋯an, the stack must contain A1A2⋯Am.
• For the next step, G must have a production A1 → bB1⋯Bk.
• Then by construction, M has a transition rule (q1, B1⋯Bk) ∈ δ(q1, b, A1),
• so that the stack contains B1⋯Bk A2⋯Am, after reading a1a2⋯anb.
27
Pushdown Automata for Context-Free Languages
Theorem 7.1

• Now, a simple induction argument on the number of steps in the derivation

shows that if

• S ⇒* w, then (q1, w, Sz) ⊢* (q1, λ, z).

• Using (7.1) and (7.3) we have
• (q0, w, z) ⊢ (q1, w, Sz) ⊢* (q1, λ, z) ⊢ (qf , λ, z),
• so that L(G) ⊆ L(M).

28
Pushdown Automata for Context-Free Languages
Theorem 7.1

• To prove L(M) ⊆ L(G), let w ∈ L(M).

• By definition, (q0, w, z) ⊢* (qf , λ, u) (7.4).
• There is only one way for transition from q0 to q1 (7.1),
• and similar from q1 to qf (7.3).
• Hence we must have
• (q1, w, Sz) ⊢* (q1, λ, z).
• Now let us write w = a1a2a3⋯an.
29
Pushdown Automata for Context-Free Languages
Theorem 7.1

• Then the first step in (q1, a1a2a3⋯an, Sz) ⊢* (q1, λ, z) must be a rule of the form (7.2) to get
• (q1, a1a2a3⋯an, Sz) ⊢ (q1, a2a3⋯an, u1z).
• But then the grammar has a rule of the form S → a1u1, so that S ⇒ a1u1.
• Repeating this, writing u1 = Au2, we have
• (q1, a2a3⋯an, Au2z) ⊢ (q1, a3⋯an, u3u2z), implying that A → a2u3 is in the grammar,
• and that S ⇒* a1a2u3u2. With this, (7.4) implies S ⇒* a1a2⋯an.
• Hence L(M) ⊆ L(G), completing the proof.
• If λ ∈ L, we add δ(q0, λ, z) = {(qf , z)}.
30
Pushdown Automata for Context-Free Languages
Example 7.7

• Consider the grammar

• S → aA, A → aABC | bB | a, B → b, C → c.
• In addition to δ(q0, λ, z) = {(q1, Sz)} and δ(q1, λ, z) = {(qf , z)},
• the PDA will also have transition rules
• δ(q1, a, S) = {(q1, A)},
• δ(q1, a, A) = {(q1, ABC), (q1, λ)}, δ(q1, b, A) = {(q1, B)},
• δ(q1, b, B) = {(q1, λ)}, δ(q1, c, C) = {(q1, λ)}.
31
Pushdown Automata for Context-Free Languages
Example 7.7

• The string aaabc can be derived as

• S ⇒ aA ⇒ aaABC ⇒ aaaBC ⇒ aaabC ⇒ aaabc.
• The sequence of moves made by M in processing aaabc is
• (q0, aaabc, z) ⊢ (q1, aaabc, Sz)
• ⊢ (q1, aabc, Az) ⊢ (q1, abc, ABCz)
• ⊢ (q1, bc, BCz) ⊢ (q1, c, Cz)
• ⊢ (q1, λ, z) ⊢ (qf , λ, z).
32
Pushdown Automata for Context-Free Languages

• We assumed GNF for simplicity.

• How about general context-free grammars?
• For productions of the form A → Bx,
• we remove A from the stack and replace it with Bx, consume no input symbol.
• For productions of the form A → abCx,
• we can consider terminals as variables, having
• (q1, bCx) ∈ δ(q1, a, A) and (q1, Cx) ∈ δ(q1, b, b).
33
Context-Free Grammars for Pushdown Automata

• The converse of Theorem 7.1 is also true.

• For simplicity of the discussion, we assume that the NPDA in question satisfies the
following requirements.

1. It has a single final state qf that is entered iff. the stack is empty;

2. With a ∈ Σ ∪ {λ}, all transitions must have the form δ(qi, a, A) = {c1, c2, ⋯, cn},
where

• ci = (qj, λ) (7.5), or ci = (qj, BC) (7.6).

• Hence each move either increases or decreases the stack by a single symbol.
34
Context-Free Grammars for Pushdown Automata

• Suppose a grammar whose variables are of the form (qi Aqj) and whose productions are s.t.
• (qi Aqj) ⇒* v, iff. the NPDA erases A from the stack while reading v and going from state qi to qj.
• Then we can have productions
• (qi Aqj) → a for (7.5) and
• (qi Aqk) → a(qj Bql)(qlCqk) for (7.6),
• where qk and ql take on all possible values in Q.
• Finally, as a start variable, we take (q0zqf ), where qf is the single final state of the NPDA.
• Then (q0zqf ) ⇒* w iff. the NPDA removes z while reading w and going from q0 to qf.
35
Context-Free Grammars for Pushdown Automata
Example 7.8

• Consider the NPDA with transitions

• δ(q0, a, z) = {(q0, Az)},
• δ(q0, a, A) = {(q0, A)}, δ(q0, b, A) = {(q1, λ)},
• δ(q1, λ, z) = {(q2, λ)}.
• Using q0 as the initial state and q2 as the final state, the NPDA satisfies the
condition 1, but not 2.

• To satisfy the condition 2, we introduce a new state q3.

36
Context-Free Grammars for Pushdown Automata
Example 7.8

• New transitions including intermediate step:

• δ(q0, a, z) = {(q0, Az)}, δ(q3, λ, z) = {(q0, Az)},
• δ(q0, a, A) = {(q3, λ)}, δ(q0, b, A) = {(q1, λ)},
• δ(q1, λ, z) = {(q2, λ)}.
• The last three transitions are of the form (7.5), so corresponding productions
• (q0 Aq3) → a, (q0 Aq1) → b, (q1zq2) → λ.

37
Context-Free Grammars for Pushdown Automata
Example 7.8

• From the first two transitions δ(q0, a, z) = {(q0, Az)}, δ(q3, λ, z) = {(q0, Az)},
• we get a set of productions using (qi Aqk) → a(qjBql)(qlCqk).
• With δ(q0, a, z) = {(q0, Az)}, k = 0,1,2,3, l = 0,1,2,3,
• (q0zq0) → a(q0 Aq0)(q0zq0) | a(q0 Aq1)(q1zq0) | a(q0 Aq2)(q2zq0) | a(q0 Aq3)(q3zq0),
• (q0zq1) → a(q0 Aq0)(q0zq1) | a(q0 Aq1)(q1zq1) | a(q0 Aq2)(q2zq1) | a(q0 Aq3)(q3zq1), ...
• With δ(q3, λ, z) = {(q0, Az)},
• (q3zq0) → (q0 Aq0)(q0zq0) | (q0 Aq1)(q1zq0) ....
38
Context-Free Grammars for Pushdown Automata
Example 7.8

• After write down all the productions, we can consider to simplify this.
• A variable that does not occur on the left side of productions must be useless, so
we can eliminate (q0 Aq0) and (q0 Aq2).

• Also, with modified transitions from the following, there is no path from q1 to q0,
from q1 to q1, from q1 to q3, and from q2 to q2.

• δ(q0, a, z) = {(q0, Az)}, δ(q3, λ, z) = {(q0, Az)}, δ(q0, a, A) = {(q3, λ)},

δ(q0, b, A) = {(q1, λ)}, δ(q1, λ, z) = {(q2, λ)}.

• Hence associated variables are useless, such as (q1zq3) or (q2zq2), etc.

39
Context-Free Grammars for Pushdown Automata
Example 7.8

• When we eliminate (q0 Aq0) / (q0 Aq2), and q1 to q0 | q1 to q1 | q1 to q3 | q2 to q2,

• we have the following shorter grammar with start variable (q0zq2) and productions
• (q0 Aq3) → a, (q0 Aq1) → b, (q1zq2) → λ,
• (q0zq0) → a(q0 Aq3)(q3zq0), (q0zq1) → a(q0 Aq3)(q3zq1),
• (q0zq2) → a(q0 Aq1)(q1zq2) | a(q0 Aq3)(q3zq2), (q0zq3) → a(q0 Aq3)(q3zq3),
• (q3zq0) → (q0 Aq3)(q3zq0), (q3zq1) → (q0 Aq3)(q3zq1),
• (q3zq2) → (q0 Aq1)(q1zq2) | (q0 Aq3)(q3zq2), (q3zq3) → (q0 Aq3)(q3zq3).
40
Context-Free Grammars for Pushdown Automata
Example 7.9

• Consider the string w = aab, which is accepted by the PDA in Example 7.8.
• δ(q0, a, z) = {(q0, Az)}, δ(q3, λ, z) = {(q0, Az)},
• δ(q0, a, A) = {(q3, λ)}, δ(q0, b, A) = {(q1, λ)},
• δ(q1, λ, z) = {(q2, λ)}.
• Check successive configurations and corresponding derivation with G by yourself.
• (q0, aab, z) ⊢ (q0, ab, Az) ⊢ (q3, b, z) ⊢ ...
• (q0zq2) ⇒ a(q0 Aq3)(q3zq2) ⇒ aa(q3zq2) ⇒ ...
41
Context-Free Grammars for Pushdown Automata
Theorem 7.2

• If L = L(M) for some NPDA M, then L is a context-free language.

• Proof: Assume that M = (Q, Σ, Γ, δ, q0, z, {qf}) satisfies conditions 1 and 2.
• We use the previous construction to get the grammar G = (V, T, S, P), with
T = Σ and V consisting of elements of the form (qicqj).

• We will skip the details of proof to show that L(M) = L(G).

42
Deterministic Pushdown Automata and
Deterministic Context-free Languages

43
Deterministic Pushdown Accepter
Definition 7.3

• A pushdown automaton M = (q, Σ, Γ, δ, q0, z, F) is said to be deterministic

if it is an automaton as defined in Definition 7.1, subject to the restrictions
that,

• for every q ∈ Q, a ∈ Σ ∪ {λ} and b ∈ Γ,

1. δ(q, a, b) contains at most one element,
2. if δ(q, λ, b) is not empty, then δ(q, c, b) must be empty for every c ∈ Σ.

44
Deterministic Context-Free Languages
Definition 7.4

• Condition 1 is for any given input symbol and stack top, at most one move
can be made.

• Condition 2 is that when a λ-move is possible, no input-consuming alternative

is available.

• A language L is said to be a deterministic context-free language if and only

if there exists a DPDA (deterministic pushdown automaton) such that
L = L(M).

45
Deterministic Pushdown Automata and Context-Free Languages
Example 7.10

n n
• The language L = {a b : n ≥ 0} is a deterministic context-free language.
• The PDA M = ({q0, q1, q2}, {a, b}, {0,1}, δ, q0,0,{q0}) with
• δ(q0, a,0) = {(q1,10)},
• δ(q1, a,1) = {(q1,11)}, δ(q1, b,1) = {(q2, λ)},
• δ(q2, b,1) = {(q2, λ)}, δ(q2, λ,0) = {(q0, λ)}
• accepts the given language, and it satisfies the conditions.
46
Deterministic vs. Nondeterministic PDAs
Example 7.11

• Unlike finite automata, DPDAs and NPDAs are not equivalent.

n n n 2n
• Let L1 = {a b : n ≥ 0} and L2 = {a b : n ≥ 0}.

• Both L1 and L2 are context-free languages, as well as L = L1 ∪ L2.

• For G1 and G2 s.t. L1 = L(G1) and L2 = L(G2), we can consider the
combined grammar G w/ productions P = P1 ∪ P2 ∪ {S → S1 | S2}.

• From the looks of it, L is not a deterministic context-free language.

• We cannot decide whether a's are matched to one b or two b's.
47
Deterministic vs. Nondeterministic PDAs
Example 7.11

• However, it assumes a specific algorithm to generate strings,

• hence there exists a possibility that a completely new method can be used.
• It turns out that there is not, so L is indeed nondeterministic.
• If L were a deterministic context-free language, then
̂ n n n
• L = L ∪ {a b c : n ≥ 0} would be a context-free language.
• We can show it by constructing an NPDA M ̂ for L ,̂ given a DPDA M for L.

48
Deterministic vs. Nondeterministic PDAs
Example 7.11

• The idea is adding a new part to the control unit of M,

n n
• which can be entered after M has read a b .
• This new part converts accepting of b into c , so M ̂
n n
n n n n n n
accepts a b c instead of a b b .
n n
• In M, (q0, a b , z) ⊢*M (qi, λ, u), with qi ∈ F.
• Since M is deterministic, the following must also be true,
n 2n n n
• (q0, a b , z) ⊢*M (qi, b , u), and (qi, b , u) ⊢*M (qj, λ, u1) Figure 7.4
n 2n
for some qj ∈ F, since it accepts a b .

49
Deterministic vs. Nondeterministic PDAs
Example 7.11

• Assume that no strings other than those in L ̂ are accepted by M ,̂

• then L ̂ = L( M )̂ , so that L ̂ is context-free.
• We will show that L ̂ is not context-free in the next chapter, so our assumption
that L is deterministic must be false.

50
Grammars for Deterministic
Context-Free Languages

51
Grammars for Deterministic Context-Free Languages

• It is important that deterministic context-free languages can be parsed

efficiently.

• We can consider the pushdown automaton as a parsing device.

• No backtracking involved, so we can easily write down a program for it.
• We may also expect the program to be efficient.

52
Grammars for Deterministic Context-Free Languages

• Suppose we are doing top-down parsing, to find the

leftmost derivation of a particular sentence.

• We can scan the input w from left to right,

• while developing a sentential form whose prefix
matches to the prefix of w.

• To proceed, we would like to know exactly which

production rule is to be applied at each step.

• The question is, which kind of grammars allow us

to do that?
53
Grammars for Deterministic Context-Free Languages

• For general context-free grammars, this is not the case, but if we restrict the form
of a grammar, we can achieve the goal.

• Consider s-grammar first.

• Suppose w = w1w2, and we have w1Ax so far.
• Say a is the leftmost symbol of w2, then we simply try to find a rule of the form
A → ay.
• If there is no such rule, then the string w cannot belong to the language.
• However, s-grammar is too restrictive to capture all aspects of the syntax of PLs.
54
Grammars for Deterministic Context-Free Languages

• One type of grammar called an LL grammar resolves such problems.

• The first L indicates the input is scanned from left to right.
• The second L indicates that leftmost derivations are constructed.
• Every s-grammar is an LL grammar.

55
LL(k) Grammar
Definition 7.5

• Let G = (V, T, S, P) be a context-free grammar.

• If for every pair of leftmost derivations
• S ⇒* w1Ax1 ⇒ w1y1x1 ⇒* w1w2,
• S ⇒* w1Ax2 ⇒ w1y2x2 ⇒* w1w3,
• with w1, w2, w3 ∈ T*, the equality of the k leftmost symbols of w2 and w3 implies
y1 = y2,
• then G is said to be an LL(k) grammar. (If | w2 | or | w3 | is less than k, then k is
replaced by the smaller of these.)
56
LL(k) Grammar
Definition 7.5

• If at any stage in the leftmost derivation (w1Ax),

• we know the next k symbols of the input,
• the next step in the derivation is uniquely determined.
• which is expressed by y1 = y2.

57
LL Grammar
Example 7.12

• The grammar
• S → aSb | ab
• is not an s-grammar, but it is an LL(2) grammar.
• In order to determine which production to be applied,
• we look at two consecutive symbols of the input string.
• For ab, we must apply the second, otherwise apply the first.

58
LL Grammar
Example 7.13

• The grammar
• S → SS | aSb | ab
• generates the language of properly nested parenthesis structures (Example 5.4).
• The grammar is not an LL(k) grammar for any k.
• If we look-ahead k symbols, still there exists a possibility that these symbols are
a prefix of more than one strings.

• e.g.) aa can be a prefix of aabb or aabbab.

59
LL Grammar
Example 7.13

• However, this does not mean that the language itself is not deterministic or no LL
grammar for it exists.

• The grammar S → aSbS | λ is an LL grammar close to the original grammar.

• For w = abab,
• S ⇒ aSbS ⇒ abS ⇒ abaSbS ⇒ ababS ⇒ abab.
• The difference is that this grammar generates an empty string.
• S0 → aSbS, S → aSbS | λ is an LL grammar equivalent to the original grammar.

60
Summary

• You should understand

• the connection between NPDAs and context-free languages.
• DPDAs and LL grammars.
• Please practice with examples,
• how to construct an NPDA for a context-free language.
• how to obtain a context-free grammar from an NPDA.
• You must remember that
• Deterministic Pushdown Automata are not equivalent to Nondeterministic Pushdown
Automata.

61