Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Theory of Computation
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
http://www-alg.ist.hokudai.ac.jp/∼thomas/ToC/

Lecture 10: CF, PDAs and Beyond

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Greibach Normal Form I

We want to show that all context-free languages are acceptedby pushdown automata. For doing this, it is very convenient touse another normal form for context-free languages, i.e., theso-called Greibach normal form.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Greibach Normal Form I

We want to show that all context-free languages are acceptedby pushdown automata. For doing this, it is very convenient touse another normal form for context-free languages, i.e., theso-called Greibach normal form.
Definition 1
A context-free grammar G = [T , N, σ, P] with λ < L(G) is said tobe in Greibach normal form if every production of G has theform h → aα, where a ∈ T and α ∈ N∗ .

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Greibach Normal Form II

Clearly, we aim to show that every context-free language does
possess a grammar in Greibach normal form. This is, however,
not as easy as it might seem. Therefore, we skip the proof here
and refer the audience to the book which also contains an
example.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Greibach Normal Form II

Clearly, we aim to show that every context-free language does
possess a grammar in Greibach normal form. This is, however,
not as easy as it might seem. Therefore, we skip the proof here
and refer the audience to the book which also contains an
example.
Theorem 1
For every language L ∈ CF with λ < L there exists a grammar G̃ suchthat L = L(G̃) and G̃ is in Greibach normal form.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata I
Now, we are ready to show the remaining fundamental
theorem concerning the power of pushdown automata.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata I
Now, we are ready to show the remaining fundamental
theorem concerning the power of pushdown automata.
Theorem 2
For every language L ∈ CF there exists a pushdown automaton Ksuch that L = N(K).
Proof. We assume that λ < L. It is left as an exercise to modify
the construction for the case that λ ∈ L. Let G = [T , N, σ, P] be acontext-free grammar in Greibach normal form such that
L = L(G).

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata II
We need the following notation:
A string α of terminals and nonterminals is called a sentential∗

form if σ =⇒ α.
Now, letK = [{q}, T , N, δ, q, σ, ∅] ,where (q, γ) ∈ δ(q, a, A) whenever (A → aγ) ∈ P.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata II
We need the following notation:
A string α of terminals and nonterminals is called a sentential∗

form if σ =⇒ α.
Now, letK = [{q}, T , N, δ, q, σ, ∅] ,where (q, γ) ∈ δ(q, a, A) whenever (A → aγ) ∈ P.
The pushdown automaton K simulates leftmost derivationsof G. Since G is in Greibach normal form, each sentential form ina leftmost derivation consists of a string x of terminals followed
by a string of nonterminals α.
Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata III
K stores the suffix α of the left sentential form on its stack after
processing the prefix x. Formally, we show the following claim.
∗

Claim 1. σ =⇒ xα
G

by a leftmost derivation if and only if∗(q, x, σ) −→ (q, λ, α) .
K

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata IV
We start with the sufficiency. The prove is done by induction.
i

∗

K

G

That is, we assume (q, x, σ) −→ (q, λ, α) and show σ =⇒ xα.
For the induction basis, let i = 0. That is, we assume0(q, x, σ) −→ (q, λ, α). By the definition of the reflexive transitiveK∗

closure −→ , this means nothing else than (q, x, σ) = (q, λ, α).
K

Consequently, x = λ and α = σ. Obviously, by the definition of
∗

∗

G

G

the reflexive transitive closure =⇒ we can conclude σ =⇒ σ,again in zero steps. This proves the induction basis.
Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata V
For the induction step, assume i > 1 and let x = ya, wherey ∈ T ∗ . Now, we consider the next-to-last-step, i.e.,
i−11(q, ya, σ) −→ (q, a, β) −→ (q, λ, α) .

(1)

K

K

If we remove a from the end of the input string in the first i
instantaneous descriptions of the sequence (1), we discover thati−1(q, y, σ) −→ (q, λ, β), since a cannot influence K’s behavior
K

until it is actually consumed from the input. Thus, we canapply the induction hypothesis and obtain∗σ =⇒ yβ .
GTheory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata VI
Taking into account that the pushdown automaton K, while1

consuming a, is making the move (q, a, β) −→ (q, λ, α), weK

directly get by construction that β = Aγ for some A ∈ N,
(A → aη) ∈ P and α = ηγ.
Hence, we arrive at
∗

1

G

G

σ =⇒ yβ =⇒ yaηγ = xα .

This completes the sufficiency proof.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata VIIi

For showing the necessity suppose that σ =⇒ xα by a leftmostG

derivation. We prove by induction on i that∗(q, x, σ) −→ (q, λ, α). The induction basis is again done forK

i = 0, and can be shown by using similar arguments as above.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata VIII
For the induction step let i > 1 and supposei−11

σ =⇒ yAγ =⇒ yaηγ , where x = ya, α = ηγ .
GG

By the induction hypothesis we directly get∗(q, y, σ) −→ (q, λ, Aγ)
K∗

and thus (q, ya, σ) −→ (q, a, Aγ). Since (A → aη) ∈ P, we canKconclude that (q, η) ∈ δ(q, a, A). Thus,
∗

1

K

K

(q, x, σ) −→ (q, a, Aγ) −→ (q, λ, α) ,and the necessity follows. This proves Claim 1.
Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

From CFto Pushdown Automata IX

To conclude the proof of the theorem, we have only to note that
Claim 1 with α = λ says
∗

∗

G

K

σ =⇒ x if and only if (q, x, σ) −→ (q, λ, λ) .

That is, x ∈ L(G) if and only if x ∈ N(K).

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Main Theorem

Now, putting it all together, we directly obtain the following.
Theorem 3
Let L be any language. Then the following three assertions areequivalent:(1) L ∈ CF .
(2) There exists a pushdown automaton K1 such that L = L(K1 ).
(3) There exists a pushdown automaton K2 such that L = N(K2 ).

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Remarks I

After so much progress we may want to ask questions likewhether or not L(G1 ) ∩ L(G2 ) = ∅ for any given context-freegrammars G1 , G2 .

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Remarks I

After so much progress we may want to ask questions likewhether or not L(G1 ) ∩ L(G2 ) = ∅ for any given context-freegrammars G1 , G2 .
You may be tempted to think this is not a too difficult task. But
as a matter of fact, nobody succeeded to design an algorithm
solving this problem for all context-free grammars. Maybe,
there is a deeper reason behind this situation. Before we can
explore such problems, we have to deal with computability.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Remarks II

On the other hand, so far we have studied regular andcontext-free languages. But we have already seen a language
which is not context-free, i.e.,
L = {an bn cn | n ∈ N} .
Thus, it is only natural to ask what other language families arearound. Due to the lack of time, we can only sketch these partsof formal language theory.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages I

First, we provide a formal definition.
Definition 2
A Grammar G = [T , N, σ, P] is said to be context-sensitive if allits productions satisfy the following conditions.
(1) (α → β) ∈ P iff there are s1 , s2 , r, and h such that h ∈ N,
s1 , s2 ∈ (T ∪ N)∗ and r ∈ (T ∪ N)+ andα = s1 hs2 and β = s1 rs2 , or(2) α = h and β = λ and h does not occur at any right-handside of a production from P.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages II
Definition 3
A language is said to be context-sensitive if there exists acontext-sensitive grammar G such that L = L(G).

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages II
Definition 3
A language is said to be context-sensitive if there exists acontext-sensitive grammar G such that L = L(G).
By CS we denote the family of all context-sensitive languages.
The name context-sensitive is quite intuitive, since thereplacement or rewriting of a nonterminal is only possible in acertain context expressed by a prefix s1 and suffix s2 . The
definition provided above directly allows for the observationthat CF ⊆ CS.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages II
Definition 3
A language is said to be context-sensitive if there exists acontext-sensitive grammar G such that L = L(G).
By CS we denote the family of all context-sensitive languages.
The name context-sensitive is quite intuitive, since thereplacement or rewriting of a nonterminal is only possible in acertain context expressed by a prefix s1 and suffix s2 . The
definition provided above directly allows for the observationthat CF ⊆ CS.
Exercise: Prove that CF ⊂ CS.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages III
Using similar ideas as we did for REG and CF, one can show
the following.
Theorem 4
The context-sensitive languages are closed under union, product andKleene closure.
Proof. The proof is left as an exercise.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages III
Using similar ideas as we did for REG and CF, one can show
the following.
Theorem 4
The context-sensitive languages are closed under union, product andKleene closure.
Proof. The proof is left as an exercise.
Also, in the same way as Theorem 6.4 has been shown, one canprove the context-sensitive languages to be closed undertransposition. That is, we directly get the next theorem.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages III
Using similar ideas as we did for REG and CF, one can show
the following.
Theorem 4
The context-sensitive languages are closed under union, product andKleene closure.
Proof. The proof is left as an exercise.
Also, in the same way as Theorem 6.4 has been shown, one canprove the context-sensitive languages to be closed undertransposition. That is, we directly get the next theorem.
Theorem 5
Let Σ be any alphabet, and let L ⊆ Σ∗ . Then we have: If L ∈ CS thenLT ∈ CS, too.
Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages IV
Moreover, in contrast to the context-free languages we have:
Theorem 6
The context-sensitive languages are closed under intersection.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages IV
Moreover, in contrast to the context-free languages we have:
Theorem 6
The context-sensitive languages are closed under intersection.
For establishing further properties of context-sensitive
languages, we need the following definition.
Definition 4
A Grammar G = [T , N, σ, P] is said to be length-increasing if foreach production (α → β) ∈ P the condition |α| 6 |β| issatisfied. In addition, P may contain the production σ → λand in this case σ does not occur on the right-hand side of any
production from P.
Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages V
Looking at the definition of context-sensitive grammars, we
directly get the following corollary.
Corollary 7
Every context-sensitive grammar is length-increasing.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages V
Looking at the definition of context-sensitive grammars, we
directly get the following corollary.
Corollary 7
Every context-sensitive grammar is length-increasing.
However, one can prove that there are length-increasing
grammars which are not context-sensitive (see below).

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages V
Looking at the definition of context-sensitive grammars, we
directly get the following corollary.
Corollary 7
Every context-sensitive grammar is length-increasing.
However, one can prove that there are length-increasing
grammars which are not context-sensitive (see below).
Nevertheless, one can show the following.
Theorem 8
For every length-increasing grammar there exists an equivalentcontext-sensitive grammar.
Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages VI

Putting it all together directly yields the following equivalence.
Theorem 9
Let L be any language. Then the following statements are equivalent:(1) There exists a context-sensitive grammar G such that L = L(G).
(2) There exists a length-increasing grammar G̃ such that L = L(G̃).

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages VII
Example 1
Let T be any alphabet. We define a grammar G = [T , N, σ, P] as
follows. Let
N = {σ} ∪ {Xi | i ∈ T } ∪ {Ai | i ∈ T } ∪ {Bi | i ∈ T } .
and let P be the following set of productions
1

σ → iσXi

2

σ → Ai Bi

3

Bi Xj → Xj Bi

4Bi → i5

Ai Xj → Ai Bj

6

Ai → iwhere i, j ∈ T .
Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages VIII

Inspecting the productions we see that G is a length-increasing
grammar which is not context-sensitive, since the context in
Production 3 is destroyed.
Nevertheless, by the latter theorem we know that the language
L(G) is context-sensitive.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages VIII

Inspecting the productions we see that G is a length-increasing
grammar which is not context-sensitive, since the context in
Production 3 is destroyed.
Nevertheless, by the latter theorem we know that the language
L(G) is context-sensitive.
Exercise: Prove that the grammar G given in the example above
generates
L = {ww | w ∈ T + } .

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages IX

The notion of length-increasing grammar has another niceimplication which we state next.
Theorem 10
There is an algorithm that on input any context-sensitive grammar
G = [T , N, σ, P] and any string s ∈ T ∗ decides whether or nots ∈ L(G).

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages X
Proof Sketch: Since every context-sensitive grammar is also alength-increasing grammar, it suffices to examine all finite
sequences w0 , w1 , . . . , wn with |wi | < |wi+1 |, i = 0, . . . , n − 1and σ = w0 as well as wn = s, where wi ∈ (T ∪ N)+ . The
number of all those sequences is finite. Let S be the set of all
such sequences.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages X
Proof Sketch: Since every context-sensitive grammar is also alength-increasing grammar, it suffices to examine all finite
sequences w0 , w1 , . . . , wn with |wi | < |wi+1 |, i = 0, . . . , n − 1and σ = w0 as well as wn = s, where wi ∈ (T ∪ N)+ . The
number of all those sequences is finite. Let S be the set of all
such sequences.
Now, the only thing one has to check is whether or not1

wi =⇒ wi+1
G

for all i = 0, . . . , n − 1 .

(2)Thus, one either finds a sequence in S fulfilling (2). Then one
can directly conclude that s ∈ L(G). If all sequences in S fail tosatisfy (2) then s < L(G).
Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages XI

Recall that we have proved the regular languages to be closed
under complement and the context-free languages to be notclosed under complement. As curious as we are, we clearly liketo know whether or not the context-sensitive languages areclosed under complement.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Context-Sensitive Languages XI

Recall that we have proved the regular languages to be closed
under complement and the context-free languages to be notclosed under complement. As curious as we are, we clearly liketo know whether or not the context-sensitive languages areclosed under complement.
To answer this question is by no means easy. As a matter offact, it took more than 20 years to resolve this question. So wehave to be a bit patient. We shall provide an answer in thecourse on “Complexity and Cryptography.”

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Beyond I

Finally, we mention what happens if we pose no restrictions
whatsoever on the set of productions. We shall call the
resulting family of languages L0 , where 0 should remind you tozero restrictions.

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Beyond I

Finally, we mention what happens if we pose no restrictions
whatsoever on the set of productions. We shall call the
resulting family of languages L0 , where 0 should remind you tozero restrictions.
Then, it is quite obvious that all languages L in L0 share theproperty that we can algorithmically enumerate all and only theelements contained in L provided we are given a grammar G
for L. However, as we shall see later, our last Theorem cannot be
generalized to L0 . So, we can directly conclude that CS ⊂ L0 .

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Beyond II

Putting it all together gives us the famous Chomsky Hierarchy,i.e.,
REG ⊂ CF ⊂ CS ⊂ L0 .

Theory of Computationc Thomas Zeugmann

Greibach Normal Form

CFGs to PDAs

Context-Sensitive Languages

BeyondEnd

Thank you!

Theory of Computationc Thomas Zeugmann