Context-Free Grammars

(1)

CS 208: Automata Theory and Logic

Lecture 6: Context-Free Grammar Ashutosh Trivedi

A

start B

b

∀x(La(x)→ ∃y.(x<y)∧Lb(y))

a

b

a

Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

(2)

Context-Free Grammars

Pushdown Automata

Properties of CFLs

(3)

Ashutosh Trivedi – 3 of 45

Context-Free Grammars

Noam Chomsky

(linguist, philosopher, logician, and activist)

“ Agrammarcan be regarded as adevicethat enumerates thesentencesof alanguage. We study a sequence of restrictions that limit grammars first toTuring machines, then to two types of systems from which a phrase structure description of a generated language can be drawn, and finally to finite state Markov sources (finite automata). ”

(4)

Grammars

A (formal)grammarconsists of

1. Afiniteset ofrewriting rulesof the form

φ→ψ

whereφandψare strings of symbols.

2. A special “initial” symbolS(Sstanding forsentence);

3. A finite set of symbols stand for “words” of the language called terminal vocabulary;

4. Other symbols stand for “phrases” and are callednon-terminal vocabulary.

Given such a grammar, a valid sentence can begeneratedby 1. starting from the initial symbolS,

2. applying one of the rewriting rules to form a new stringφby applying a ruleS→φ₁,

3. and apply another rule to form a new stringφ₂and so on, 4. until we reach a stringφ_nthat consists only ofterminal symbols.

(5)

Grammars

A (formal)grammarconsists of

1. Afiniteset ofrewriting rulesof the form

φ→ψ

whereφandψare strings of symbols.

2. A special “initial” symbolS(Sstanding forsentence);

3. A finite set of symbols stand for “words” of the language called terminal vocabulary;

4. Other symbols stand for “phrases” and are callednon-terminal vocabulary.

Given such a grammar, a valid sentence can begeneratedby 1. starting from the initial symbolS,

2. applying one of the rewriting rules to form a new stringφby applying a ruleS→φ₁,

3. and apply another rule to form a new stringφ₂and so on, 4. until we reach a stringφ_nthat consists only ofterminal symbols.

(6)

Examples

Consider the grammar

S → AB (1)

A → C (2)

CB → Cb (3)

C → a (4)

where{a,b}are terminals, and{S,A,B,C}are non-terminals.

We can derive the phrase “ab” from this grammar in the following way: S → AB, from (1)

→ CB, from (2)

→ Cb, from (3)

→ ab, from (4)

(7)

Examples

S → AB (1)

A → C (2)

CB → Cb (3)

C → a (4)

where{a,b}are terminals, and{S,A,B,C}are non-terminals.

We can derive the phrase “ab” from this grammar in the following way:

S → AB, from (1)

→ CB, from (2)

→ Cb, from (3)

→ ab, from (4)

(8)

Examples

S → NounPhrase VerbPhrase (5)

NounPhrase → SingularNoun (6)

SingularNoun VerbPhrase → SingularNoun comes (7)

SingularNoun → John (8)

We can derive the phrase “John comes” from this grammar in the following way:

S → NounPhrase VerbPhrase, from (1)

→ SingularNoun VerbPhrase, from (2)

→ SingularNoun comes, from (3)

→ John comes, from (4)

(9)

Types of Grammars

Depending on therewriting ruleswe can characterize the grammars in the following four types:

1. type 0 grammarswith no restriction on rewriting rules;

2. type 1 grammarshave the rules of the form αAβ→αγβ

whereAis a nonterminal,α, β, γare strings of terminals and nonterminals, andγis non empty.

3. type 2 grammarshave the rules of the form A→γ

whereAis a nonterminal, andγis a string (potentially empty) of terminals and nonterminals.

4. type 3 grammarshave the rules of the form A→aBorA→a

whereA,Bare nonterminals, andais a string (potentially empty) of terminals.

(10)

Types of Grammars

1. Unrestricted grammarswith no restriction on rewriting rules;

2. Context-sensitive grammarshave the rules of the form αAβ→αγβ

3. Context-free grammarshave the rules of the form A→γ

4. Regular grammarshave the rules of the form

(also left-linear grammars)

(11)

Types of Grammars

1. Unrestricted grammarswith no restriction on rewriting rules;

2. Context-sensitive grammarshave the rules of the form αAβ→αγβ

3. Context-free grammarshave the rules of the form A→γ

4. Regular grammarshave the rules of the form A→aBorA→a

whereA,Bare nonterminals, andais a string (potentially empty) of terminals. (also left-linear grammars)

(12)

Do regular grammars capture regular languages?

– Regular grammars to finite automata – Finite automata to regular grammars

(13)

Context-Free Languages: Syntax

Definition (Context-Free Grammar)

Acontext-free grammaris a tupleG= (V,T,P,S)where

– Vis a finite set ofvariables(nonterminals, nonterminals vocabulary);

– Tis a finite set ofterminals(letters);

– P⊆V×(V∪T)^∗is a finite set ofrewriting rulescalledproductions, – We writeA→βif(A, β)∈P;

– S∈Vis a distinguishedstartor “sentence” symbol.

Example:G0ⁿ1ⁿ = (V,T,P,S)where – V={S};

– T={0,1}; – Pis defined as

S → ε

S → 0S1

– S=S.

(14)

Context-Free Languages: Syntax

Definition (Context-Free Grammar)

Acontext-free grammaris a tupleG= (V,T,P,S)where

– Vis a finite set ofvariables(nonterminals, nonterminals vocabulary);

– Tis a finite set ofterminals(letters);

– P⊆V×(V∪T)^∗is a finite set ofrewriting rulescalledproductions, – We writeA→βif(A, β)∈P;

– S∈Vis a distinguishedstartor “sentence” symbol.

Example:G0ⁿ1ⁿ = (V,T,P,S)where – V={S};

S → ε

(15)

Context-Free Languages: Semantics

Derivation:

– LetG= (V,T,P,S)be a context-free grammar.

– LetαAβbe a string in(V∪T)^∗V(V∪T)^∗

– We say thatαAβyieldsthe stringαγβ, and we writeαAβ⇒αγβif A→γis a production rule inG.

– For stringsα, β∈(V∪T)^∗, we say thatαderivesβand we write α=⇒^∗ βif there is a sequenceα₁, α₂, . . . , α_n∈(V∪T)^∗s.t.

α→α₁→α₂· · ·α_n→β.

Definition (Context-Free Grammar: Semantics)

ThelanguageL(G)accepted by a context-free grammarG= (V,T,P,S)is the set

L(G) ={w∈T^∗ : S=⇒^∗ w}.

(16)

Context-Free Languages: Semantics

Derivation:

– LetG= (V,T,P,S)be a context-free grammar.

– LetαAβbe a string in(V∪T)^∗V(V∪T)^∗

– We say thatαAβyieldsthe stringαγβ, and we writeαAβ⇒αγβif A→γis a production rule inG.

– For stringsα, β∈(V∪T)^∗, we say thatαderivesβand we write α=⇒^∗ βif there is a sequenceα₁, α₂, . . . , α_n∈(V∪T)^∗s.t.

α→α₁→α₂· · ·α_n→β.

Definition (Context-Free Grammar: Semantics)

ThelanguageL(G)accepted by a context-free grammarG= (V,T,P,S)is

(17)

CFG: Example

RecallG0ⁿ1ⁿ = (V,T,P,S)where – V={S};

S → ε

S → 0S1

– S=S.

The string 000111∈L(G0ⁿ1ⁿ), i.e.S=⇒^∗ 000111 as

S⇒0S1⇒00S11⇒000S111⇒000111.

(18)

Prove that 0

ⁿ

1

ⁿ

is accepted by the grammar G

₀ⁿ₁ⁿ

.

The proof is in two parts.

– First show that every stringwof the form 0ⁿ1ⁿcan be derived fromS using induction overw.

– Then, show that for every stringw∈ {0,1}^∗derived fromS, we have thatwis of the form 0ⁿ1ⁿ.

(19)

CFG: Example

Consider the following grammarG= (V,T,P,S)where – V={E,I};T={a,b,0,1};S=E; and

– Pis defined as

E → I|E+E|E∗E|(E) I → a|Ia|Ib|I0|I1

The string(a1+b0∗a1)∈L(G), i.e. E=⇒^∗ (a1+b0∗a1)as

E ⇒ (E)⇒(E+E)⇒(I+E)⇒(I1+E)⇒(a1+E)=⇒^∗ (a1+b0∗a1).

E ⇒ (E)⇒(E+E)⇒(E+E∗E)⇒(E+E∗I)=⇒^∗ (a1+b0∗a1). Leftmost and rightmost derivations:

1. Derivations are not unique

2. Leftmost and rightmost derivations

3. Define⇒_lmand⇒_rmin straightforward manner.

4. Find leftmost and rightmost derivations of(a1+b0∗a1).

(20)

CFG: Example

– Pis defined as

E ⇒ (E)⇒(E+E)⇒(I+E)⇒(I1+E)⇒(a1+E)=⇒^∗ (a1+b0∗a1).

E ⇒ (E)⇒(E+E)⇒(E+E∗E)⇒(E+E∗I)=⇒^∗ (a1+b0∗a1).

Leftmost and rightmost derivations: 1. Derivations are not unique

(21)

CFG: Example

– Pis defined as

E ⇒ (E)⇒(E+E)⇒(I+E)⇒(I1+E)⇒(a1+E)=⇒^∗ (a1+b0∗a1).

E ⇒ (E)⇒(E+E)⇒(E+E∗E)⇒(E+E∗I)=⇒^∗ (a1+b0∗a1).

Leftmost and rightmost derivations:

1. Derivations are not unique

(22)

Exercise

Consider the following grammar:

S → AS|ε.

S → aa|ab|ba|bb

Give leftmost and rightmost derivations of the stringaabbba.

(23)

Parse Trees

– A CFG provide astructureto a string

– Such structure assignsmeaning to a string, and hence a unique structure is really important in several applications, e.g. compilers – Parse treesare a successful data-structures to represent and store such

structures

– Let’s review the Tree terminology:

– A tree is adirected acyclic graph(DAG) where every node has at most incoming edge.

– Edge relationship asparent-childrelationship

– Every node has at most one parent, and zero or more children – We assume an implicit order on children (“from left-to-right”)

– There is a distinguishedrootnode with no parent, while all other nodes have a unique parent

– There are some nodes with nochildrencalledleaves—other nodes are calledinterior nodes

– Ancestor and descendent relationships are closure of parent and child relationships, resp.

(24)

Parse Trees

structures

(25)

Parse Trees

structures

(26)

Parse Tree

Given a grammarG= (V,T,P,S), the parse trees associated withGhas the following properties:

1. Eachinterior nodeis labeled by a variable inV.

2. Eachleafis either a variable, terminal, orε. However, if a leaf isεit is the only child of its parent.

3. If an interior node is labeledAand has children labeledX1,X2, . . . ,Xk

from left-to-right, then

A→X1X2. . .Xk

is a production isP. Only timeXican beεis when it is the only child of its parent, i.e. corresponding to the productionA→ε.

(27)

Reading exercise

– Giveparse treerepresentation of previous derivation exercises.

– Are leftmost-derivation and rightmost derivation parse-trees always different?

– Are parse trees unique?

– Answer isno. A grammar is calledambiguousif there is at least one string with two different leftmost (or rightmost) derivations.

– There are some inherently ambiguous languages.

L={aⁿbⁿc^md^m : n,m≥1} ∪ {aⁿb^mcⁿd^m : n,m≥1}. Write a grammar accepting this language. Show that the string a²b²c²d²has two leftmost derivations.

– There is no algorithm to decide whether a grammar is ambiguous. – What does that mean from application side?

(28)

Reading exercise

(29)

Reading exercise

(30)

Reading exercise

(31)

Reading exercise

L={aⁿbⁿc^md^m : n,m≥1} ∪ {aⁿb^mcⁿd^m : n,m≥1}.

Write a grammar accepting this language. Show that the string a²b²c²d²has two leftmost derivations.

(32)

Reading exercise

– There is no algorithm to decide whether a grammar is ambiguous.

– What does that mean from application side?

(33)

Reading exercise

– There is no algorithm to decide whether a grammar is ambiguous.

– What does that mean from application side?

(34)

In-class Quiz

Write CFGs for the following languages:

1. Strings ending with a 0

2. Strings containing even number of 1’s 3. palindromes over{0,1}

4. L={aⁱb^j : i≤2j}orL={aⁱb^j : i<2j}orL={aⁱb^j : i6=2j} 5. L={aⁱb^jc^k : i=k}

6. L={aⁱb^jc^k : i=j} 7. L={aⁱb^jc^k : i=j+k}.

8. L={w∈ {0,1}^∗ : |w|_a=|w|_b}.

9. Closure underunion,concatenation, andKleenestar 10. Closure undersubstitution,homomorphism, andreversal

(35)

Syntactic Ambiguity in English

—Anthony G. Oettinger

(36)

Syntactic Ambiguity in English

(37)

Pushdown Automata

Properties of CFLs

(38)

Pushdown Automata

Anthony G. Oettinger

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

– Introduced independently byAnthony G. Oettinger in 1961 and byMarcel-Paul Sch ¨utzenbergerin 1963 – Generalization ofε-NFA with a “stack-like” storage

mechanism

– Precisely capturecontext-freelanguages – Deterministic version is not as expressive as

non-deterministic one

(39)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

⊥ pushdown stack

(40)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

1

⊥ pushdown stack

(41)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

1 1

⊥ pushdown stack

(42)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥ 1

1 1

⊥ pushdown stack

(43)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

0 1 1 1

⊥ pushdown stack

(44)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

0 1 1 1

⊥ pushdown stack

(45)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥ 1

1 1

⊥ pushdown stack

(46)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

1 1

⊥ pushdown stack

(47)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

1

⊥ pushdown stack

(48)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

⊥ pushdown stack

(49)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

⊥ pushdown stack

(50)

Example 1: L = {ww : w ∈ { 0 , 1 }

^∗

}

input tape 1 1 1 0 0 1 1 1

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

⊥ pushdown stack

(51)

Pushdown Automata

q0

start q1 q2

0,X7→0X

1,X7→1X

ε,X7→X

0,07→ε

1,17→ε

ε,⊥ 7→ ⊥

Apushdown automatais a tuple(Q,Σ,Γ, δ,q0,⊥,F)where:

– Qis afinite setcalled thestates;

– Σis afinite setcalled thealphabet;

– Γis afinite setcalled thestack alphabet;

– δ:Q×Σ×Γ→2^Q×Γ^∗is thetransition function;

– q0∈Qis thestart state;

– ⊥ ∈Γis thestart stack symbol;

– F⊆Qis the set ofaccepting states.

(52)

Semantics of a PDA

– LetP= (Q,Σ,Γ, δ,q0,⊥,F)be a PDA.

– Aconfiguration(or instantaneous description) of a PDA is a triple (q,w, γ)where

– qis thecurrent state,

– wis theremaining input, and

– γ∈Γ^∗is the stack contents, where written as concatenation of symbols form top-to-bottom.

– We define the operator`(derivation) such that if(p, α)∈δ(q,a,X) then

(q,aw,Xβ)`(p,w, αβ),

for allw∈Σ^∗andβ∈Γ^∗. The operator⊥^∗is defined as transitive closure of⊥in straightforward manner.

– Arunof a PDAP= (Q,Σ,Γ, δ,q0,⊥,F)over an input wordw∈Σ^∗is a sequence of configurations

(q ,w , β ),(q,w , β ), . . . ,(q ,w , β )

(53)

Semantics: acceptance via final states

1. We say that a run

(q0,w0, β₀),(q1,w1, β₁), . . . ,(qn,wn, β_n) isaccepted via final stateifqn∈Fandwn=ε.

2. We say that a wordwisaccepted via final statesif there existsa runof Poverwthat is accepted via final state.

3. We writeL(P)for the set of words accepted via final states.

4. In other words,

L(P) ={w : (q0,w,⊥)`^∗(qn, ε, β)andqn∈F}.

5. ExampleL={ww : w∈ {0,1}^∗}with the notion ofconfiguration, computation,run, andacceptance.

(54)

Semantics: acceptance via final states

(q0,w0, β₀),(q1,w1, β₁), . . . ,(qn,wn, β_n) isaccepted via final stateifqn∈Fandwn=ε.

2. We say that a wordwisaccepted via final statesif there existsa runof Poverwthat is accepted via final state.

3. We writeL(P)for the set of words accepted via final states.

4. In other words,

L(P) ={w : (q0,w,⊥)`^∗(qn, ε, β)andqn∈F}.

5. ExampleL={ww : w∈ {0,1}^∗}with the notion ofconfiguration,

(55)

Semantics: acceptance via empty stack

(q0,w0, β₀),(q1,w1, β₁), . . . ,(qn,wn, β_n) isaccepted via empty stackifβ_n=εandwn=ε.

2. We say that a wordwisaccepted via empty stackif there existsa run ofPoverwthat is accepted via empty stack.

3. We writeN(P)for the set of words accepted via empty stack.

4. In other words

N(P) ={w : (q0,w,⊥)`^∗(qn, ε, ε)}.

IsL(P) =N(P)?

(56)

Semantics: acceptance via empty stack

(q0,w0, β₀),(q1,w1, β₁), . . . ,(qn,wn, β_n) isaccepted via empty stackifβ_n=εandwn=ε.

2. We say that a wordwisaccepted via empty stackif there existsa run ofPoverwthat is accepted via empty stack.

3. We writeN(P)for the set of words accepted via empty stack.

4. In other words

N(P) ={w : (q0,w,⊥)`^∗(qn, ε, ε)}.

IsL(P) =N(P)?

(57)

Equivalence of both notions

Theorem

For every language defind by a PDA with empty stack semantics, there exists a PDA that accept the same language with final state semantics, and vice-versa.

Proof.

– Final state to Empty stack

– Add a new stack symbol, say⊥⁰, as the start stack symbol, and in the first transition replace it with⊥⊥⁰before reading any symbol.

(How? and Why?)

– From every final state make a transition to a sink state that does not read the input but empties the stack including⊥⁰.

– Empty Stack to Final state

– Replace the start stack symbol⊥⁰and⊥⊥⁰before reading any symbol. (Why?)

– From every state make a transition to a new unique final state that does not read the input but removes the symbol⊥⁰.

(58)

Equivalence of both notions

Theorem

For every language defind by a PDA with empty stack semantics, there exists a PDA that accept the same language with final state semantics, and vice-versa.

Proof.

– Final state to Empty stack

– Add a new stack symbol, say⊥⁰, as the start stack symbol, and in the first transition replace it with⊥⊥⁰before reading any symbol.

(How? and Why?)

– From every final state make a transition to a sink state that does not read the input but empties the stack including⊥⁰.

– Empty Stack to Final state

– Replace the start stack symbol⊥⁰and⊥⊥⁰before reading any symbol.

(Why?)

(59)

Formal Construction: Empty stack to Final State

LetP= (Q,Σ,Γ, δ,q0,⊥)be a PDA. We claim that the PDA P⁰= (Q⁰,Σ,Γ⁰, δ⁰,q⁰₀,⊥⁰,F⁰)is such thatN(P) =L(P⁰), where

1. Q⁰ =Q∪ {q⁰₀} ∪ {qF} 2. Γ⁰= Γ∪ {⊥⁰} 3. F⁰={qF}. 4. δ⁰is such that

– δ⁰(q,a,X) =δ(q,a,X)for allq∈QandX∈Γ, – δ⁰(q⁰₀, ε,⊥⁰) ={(q₀,⊥⊥⁰)}and

– δ⁰(q, ε,⊥⁰) ={(qF,⊥⁰)}for allq∈Q.

(60)

Formal Construction: Final State to Empty Stack

LetP= (Q,Σ,Γ, δ,q0,⊥,F)be a PDA. We claim that the PDA P⁰= (Q⁰,Σ,Γ⁰, δ⁰,q⁰₀,⊥⁰)is such thatL(P) =N(P⁰), where

1. Q⁰ =Q∪ {q⁰₀} ∪ {qF} 2. Γ⁰= Γ∪ {⊥⁰} 3. δ⁰is such that

– δ⁰(q,a,X) =δ(q,a,X)for allq∈QandX∈Γ, – δ⁰(q⁰₀, ε,⊥⁰) ={(q₀,⊥⊥⁰)}and

– δ⁰(q, ε,X) ={(qF, ε)}for allq∈QandX∈Γ.

– δ⁰(qF, ε,X) ={(qF, ε)}for allX∈Γ.

(61)

Expressive power of CFG and PDA

Theorem

A language iscontext-freeif and only if some pushdown automaton accepts it.

Proof.

1. For an arbitrary CFGGgive a PDAPGsuch thatL(G) =L(PG).

– Leftmost derivation of a string using the stack – One state PDA accepting by empty stack

– Proof via a simple induction over size of an accepting run of PDA 2. For an arbitrary PDAPgive a CFGGPsuch thatL(P) =L(GP).

– Modify the PDA to have the following properties such that each step is either a “push” or “pop”, and has a single accepting state and the stack is emptied before accepting.

– For every state pair ofPdefine a variableApqinPGgenerating strings such that PDA moves from statepto stateqstarting and ending with empty stack.

– Three production rules

Apq=aArsbandApq=AprArqandApp=ε.

(62)

Expressive power of CFG and PDA

Theorem

Proof.

1. For an arbitrary CFGGgive a PDAPGsuch thatL(G) =L(PG). – Leftmost derivation of a string using the stack

– One state PDA accepting by empty stack

– Proof via a simple induction over size of an accepting run of PDA

2. For an arbitrary PDAPgive a CFGGPsuch thatL(P) =L(GP). – Modify the PDA to have the following properties such that each step is

either a “push” or “pop”, and has a single accepting state and the stack is emptied before accepting.

(63)

Expressive power of CFG and PDA

Theorem

Proof.

(64)

Expressive power of CFG and PDA

Theorem

Proof.

(65)

From CFGs to PDAs

Given a CFGG= (V,T,P,S)consider PDAPG= ({q},T,V∪T, δ,q,S)s.t.:

– for everya∈Twe have

δ(q,a,a) = (q, ε), and – for variableA∈Vwe have that

δ(q, ε,A) ={(q, β) : A→βis a production ofP}.

ThenL(G) =N(PG).

Example. Give the PDA equivalent to the following grammar I → a|b|Ia|Ib|I0|I1

E → I|E∗E|E+E|(E).

(66)

From CFGs to PDAs

Given a CFGG= (V,T,P,S)consider PDAPG= ({q},T,V∪T, δ,q,S)s.t.:

– for everya∈Twe have

δ(q,a,a) = (q, ε), and – for variableA∈Vwe have that

δ(q, ε,A) ={(q, β) : A→βis a production ofP}.

ThenL(G) =N(PG).

Example. Give the PDA equivalent to the following grammar I → a|b|Ia|Ib|I0|I1

E → I|E∗E|E+E|(E).

(67)

From CFGs to PDAs

Theorem

We have that w∈N(P)if and only if w∈L(G).

Proof.

– (If part). Supposew∈L(G). Thenwhas a leftmost derivation S=γ₁⇒_lmγ₂ ⇒_lm· · · ⇒_lmγ_n=w.

It is straightforward to see that by induction onithat (q,w,S)`^∗(q,yi, α_i)wherew=xiyiandxiα_i=γ_i.

(68)

From CFGs to PDAs

Theorem

We have that w∈N(P)if and only if w∈L(G).

Proof.

– (Only If part). Supposew∈N(P), i.e.(q,w,S)`^∗(q, ε, ε).

We show that if(q,x,A)`^∗(q, ε, ε)thenA⇒^∗xby induction over number of moves taken byP.

– Base case.x=εand(q, ε)∈δ(q, ε,A). It follows thatA→εis a production inP.

– inductive step. Let the first step beA→Y1Y2. . .Yk. Letx1x2. . .xkbe the part of input to be consumed by the timeY1. . .Ykis popped out of the stack.

It follows that(q,xi,Yi)`^∗(q, ε, ε), and from inductive hypothesis we get thatYi⇒xiifYiis a variable, andYi=xiisYiis a terminal. Hence,

(69)

From PDAs to CFGs

Given a PDAP= (Q,Σ,Γ, δ,q0,⊥,{qF})with restriction that every transition is either pushes a symbol or pops a symbol form the stack, i.e.

δ(q,a,X)contains either(q⁰,YX)or(q⁰, ε).

Consider the grammarGp = (V,T,P,S)such that – V={Ap,q : p,q∈Q}

– T= Σ – S=Aq0,qF

– andPhas transitions of the following form:

– Aq,q→εfor allq∈Q;

– Ap,q→Ap,rAr,qfor allp,q,r∈Q,

– Ap,q→a Ar,sbifδ(p,a, ε)contains(r,X)andδ(s,b,X)contains(q, ε).

We have thatL(Gp) =L(P).

(70)

From PDAs to CFGs

Given a PDAP= (Q,Σ,Γ, δ,q0,⊥,{qF})with restriction that every transition is either pushes a symbol or pops a symbol form the stack, i.e.

δ(q,a,X)contains either(q⁰,YX)or(q⁰, ε).

Consider the grammarGp = (V,T,P,S)such that – V={Ap,q : p,q∈Q}

– T= Σ – S=Aq0,qF

– andPhas transitions of the following form:

– Aq,q→εfor allq∈Q;

– Ap,q→Ap,rAr,qfor allp,q,r∈Q,

– Ap,q→a Ar,sbifδ(p,a, ε)contains(r,X)andδ(s,b,X)contains(q, ε).

We have thatL(Gp) =L(P).

(71)

From PDAs to CFGs

Theorem

If Ap,q⇒^∗x then x can bring the PDA P from state p on empty stack to state q on empty stack.

Proof.

We prove this theorem by induction on the number of steps in the derivation ofxfromAp,q.

– Base case. IfAp,q⇒^∗xin one step, then the only rule that can generate a variable free string in one step isAp,p→ε.

– Inductive step. IfAp,q⇒^∗xinn+1 steps. The first step in the derivation must beAp,q→Ap,rAr,qorAp,q→a Ar,sb.

– If it isAp,q→Ap,rAr,q, then the stringxcan be broken into two partsx1x2

such thatAp,r⇒^∗x1andAr,q⇒^∗x2in at mostnsteps. The theorem easily follows in this case.

– If it isAp,q→aAr,sb, then the stringxcan be broken asaybsuch that Ar,s⇒^∗yinnsteps. Notice that frompon readingathe PDA pushes a symbolXto stack, while it popsXin statesand goes toq.

(72)

From CFGs to PDAs

Theorem

If x can bring the PDA P from state p on empty stack to state q on empty stack then Ap,q⇒^∗x.

Proof.

We prove this theorem by induction on the number of steps the PDA takes onxto go frompon empty stack toqon empty stack.

– Base case. If the computation has 0 steps that it begins and ends with the same state and readsεfrom the tape. Note thatAp,p⇒^∗εsince Ap,p→εis a rule inP.

– Inductive step. If the computation takesn+1 steps. To keep the stack empty, the first step must be a “push” move, while the last step must be a “pop” move. There are two cases to consider:

– The symbol pushed in the first step is the symbol popped in the last step.

(73)

Pushdown Automata

Properties of CFLs

(74)

Deterministic Pushdown Automata

A PDAP= (Q,Σ,Γ, δ,q0,⊥,F)isdeterministicif

– δ(q,a,X)has at most one member for everyq∈Q,a∈Σora=ε, and X∈Γ.

– Ifδ(q,a,X)is nonempty for somea∈Σthenδ(q, ε,X)must be empty.

Example.L={0ⁿ1ⁿ : n≥1}.

Theorem

Everyregular languagecan be accepted by adeterministic pushdown automata that accepts by final states.

Theorem (DPDA 6= PDA)

There are some CFLs, for instance{ww}that can not be accepted by a DPDA.

(75)

Deterministic Pushdown Automata

Theorem

Theorem (DPDA 6= PDA)

(76)

Deterministic Pushdown Automata

Theorem

Theorem (DPDA 6= PDA)

(77)

Deterministic Pushdown Automata

Theorem

Theorem (DPDA 6= PDA)

(78)

Chomsky Normal Form

A Context-free grammar(V,T,P,S)is inChomsky Normal Formif every rule is of the form

A → BC

A → a.

whereA,B,Care variables, andais a nonterminal. Also, the start variable Smust not appear on the right-side of any rule, and we also permit the ruleS→ε.

Theorem

Every context-free language is generated by a CFG in Chomsky normal form.

Reading Assignment: How to convert an arbitrary CFG to Chomsky Normal Form.

(79)

Chomsky Normal Form

A Context-free grammar(V,T,P,S)is inChomsky Normal Formif every rule is of the form

A → BC

A → a.

whereA,B,Care variables, andais a nonterminal. Also, the start variable Smust not appear on the right-side of any rule, and we also permit the ruleS→ε.

Theorem

Every context-free language is generated by a CFG in Chomsky normal form.

Reading Assignment: How to convert an arbitrary CFG to Chomsky Normal Form.

(80)

Pumping Lemma for CFLs

Theorem

For every context-free language L there exists a constant p (that depends on L) such that

for every string z∈L of length greater or equal to p, there is aninfinite family of stringsbelonging to L.

Why? Think parse Trees!

Let L be a CFL. Then there exists a constant n such that if z is a string in L of length at least n, then we can write z=uvwxy such that

– |vwx| ≤n – vx6=ε,

– For all i≥0the string uvⁱwxⁱy∈L.

(81)

Pumping Lemma for CFLs

Theorem

– |vwx| ≤n – vx6=ε,

– For all i≥0the string uvⁱwxⁱy∈L.

(82)

Pumping Lemma for CFLs

Theorem

– |vwx| ≤n – vx6=ε,

(83)

Pumping Lemma for CFLs

Theorem

Let L be a CFL. Then there exists a constant n such that if z is a string in L of length at least n, then we can write z=uvwxy such that i)|vwx| ≤n, ii) vx6=ε, and iii) for all i≥0the string uvⁱwxⁱy∈L.

– LetGbe a CFG acceptingL. Letbbe an upper bound on the size of the RHS of any production rule ofG.

– What is theupper boundon the length strings inLwith parse-tree of

height`+1? Answer:b^`.

– LetN=|V|be the number of variables inG.

– What can we say about the stringszinLof size greater thanb^N? – Answer: in every parse tree ofzthere must be a path where a variable

repeats.

– Consider a minimum size parse-tree generatingz, and consider a path where at least a variable repeats, and consider the last such variable. – Justify the conditions of the pumping Lemma.

(84)

Pumping Lemma for CFLs

Theorem

– What is theupper boundon the length strings inLwith parse-tree of height`+1?

Answer:b^`. – LetN=|V|be the number of variables inG.

repeats.

(85)

Pumping Lemma for CFLs

Theorem

– What can we say about the stringszinLof size greater thanb^N?

– Answer: in every parse tree ofzthere must be a path where a variable repeats.

(86)

Pumping Lemma for CFLs

Theorem

repeats.

– Consider a minimum size parse-tree generatingz, and consider a path

(87)

Applying Pumping Lemma

Theorem (Pumping Lemma for Context-free Languages)

L∈Σ^∗is acontext-freelanguage

=⇒

there existsp≥1such that

for allstrings z∈L with|z| ≥p we have that

there existsu,v,w,x,y∈Σ^∗with z=uvwxy,|vx|>0,|vwx| ≤p such that for alli≥0we have that

uvⁱwxⁱy∈L.

Pumping Lemma (Contrapositive)

For allp≥1we have that

there existsstrings z∈L with|z| ≥p such that

for allu,v,w,x,y∈Σ^∗with z=uvwxy,|vx|>0,|vwx| ≤p we have that there existsi≥0such that

uvⁱwxⁱy6∈L.

=⇒

L∈Σ^∗is not acontext-freelanguage.

(88)

Applying Pumping Lemma

Theorem (Pumping Lemma for Context-free Languages)

L∈Σ^∗is acontext-freelanguage

=⇒

there existsp≥1such that

for allstrings z∈L with|z| ≥p we have that

there existsu,v,w,x,y∈Σ^∗with z=uvwxy,|vx|>0,|vwx| ≤p such that for alli≥0we have that

uvⁱwxⁱy∈L.

Pumping Lemma (Contrapositive)

For allp≥1we have that

there existsstrings z∈L with|z| ≥p such that

for allu,v,w,x,y∈Σ^∗with z=uvwxy,|vx|>0,|vwx| ≤p we have that there existsi≥0such that

(89)

Example

Prove that the following languages are not context-free:

1. L={0ⁿ1ⁿ2ⁿ : n≥0} 2. L={0ⁱ1^j2^k : 0≤i≤j≤k} 3. L={ww : w∈ {0,1}^∗}.

4. L={0ⁿ : nis a prime number}. 5. L={0ⁿ : nis a perfect square}.

6. L={0ⁿ : nis a perfect cube}.

(90)

Closure Properties

Theorem

Context-free languages are closed under the following operations:

1. Union 2. Concatenation 3. Kleene closure 4. Homomorphism 5. Substitution

6. Inverse-homomorphism 7. Reverse

Reading Assignment: Proof of closure under these operations.

(91)

Closure Properties

Theorem

Context-free languages are closed under the following operations:

1. Union 2. Concatenation 3. Kleene closure 4. Homomorphism 5. Substitution

6. Inverse-homomorphism 7. Reverse

Reading Assignment: Proof of closure under these operations.

(92)

Intersection and Complementaion

Theorem

Context-free languages are not closed underintersectionandcomplementation.

Proof.

– Consider the languages

L1 = {0ⁿ1ⁿ2^m : n,m≥0}, and L2 = {0^m1ⁿ2ⁿ : n,m≥0}.

– Both languages are CFLs.

– What isL1∩L2?

– L={0ⁿ1ⁿ2ⁿ : n≥0}and it is not a CFL. – Hence CFLs are not closed underintersection.

– Use De’morgan’s law to prove non-closure undercomplementation.

(93)

Intersection and Complementaion

Theorem

Proof.

– What isL1∩L2?

– L={0ⁿ1ⁿ2ⁿ : n≥0}and it is not a CFL.

– Hence CFLs are not closed underintersection.

– Use De’morgan’s law to prove non-closure undercomplementation.

(94)

Intersection and Complementaion

Theorem

Proof.

– What isL1∩L2?

– L={0ⁿ1ⁿ2ⁿ : n≥0}and it is not a CFL.

– Hence CFLs are not closed underintersection.