**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.

Context-Free Grammars

Pushdown Automata

Properties of CFLs

**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). ”

**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→φ_{1},

3. and apply another rule to form a new stringφ_{2}and so on,
4. until we reach a stringφ_{n}that consists only ofterminal symbols.

**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→φ_{1},

3. and apply another rule to form a new stringφ_{2}and so on,
4. until we reach a stringφ_{n}that consists only ofterminal symbols.

**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)

**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)

**Examples**

Consider the grammar

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)

**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.

**Types of Grammars**

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

1. Unrestricted grammarswith no restriction on rewriting rules;

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

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

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

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

4. Regular grammarshave the rules of the form

(also left-linear grammars)

**Types of Grammars**

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

1. Unrestricted grammarswith no restriction on rewriting rules;

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

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

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

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

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)

**Do regular grammars capture regular languages?**

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

**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^{n}1^{n} = (V,T,P,S)where
– V={S};

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

S → ε

S → 0S1

– S=S.

**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^{n}1^{n} = (V,T,P,S)where
– V={S};

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

S → ε

**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α_{1}, α_{2}, . . . , α_{n}∈(V∪T)^{∗}s.t.

α→α_{1}→α_{2}· · ·α_{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}.

**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α_{1}, α_{2}, . . . , α_{n}∈(V∪T)^{∗}s.t.

α→α_{1}→α_{2}· · ·α_{n}→β.

### Definition (Context-Free Grammar: Semantics)

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

**CFG: Example**

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

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

S → ε

S → 0S1

– S=S.

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

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

**Prove that** 0

^{n}

## 1

^{n}

**is accepted by the grammar** G

_{0}

^{n}

_{1}

^{n}

**.**

The proof is in two parts.

– First show that every stringwof the form 0^{n}1^{n}can be derived fromS
using induction overw.

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

**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⇒_{lm}and⇒_{rm}in straightforward manner.

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

**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⇒_{lm}and⇒_{rm}in straightforward manner.

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

**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⇒_{lm}and⇒_{rm}in straightforward manner.

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

**Exercise**

Consider the following grammar:

S → AS|ε.

S → aa|ab|ba|bb

Give leftmost and rightmost derivations of the stringaabbba.

**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.

**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.

**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.

**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→ε.

**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^{n}b^{n}c^{m}d^{m} : n,m≥1} ∪ {a^{n}b^{m}c^{n}d^{m} : n,m≥1}.
Write a grammar accepting this language. Show that the string
a^{2}b^{2}c^{2}d^{2}has two leftmost derivations.

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

**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^{n}b^{n}c^{m}d^{m} : n,m≥1} ∪ {a^{n}b^{m}c^{n}d^{m} : n,m≥1}.
Write a grammar accepting this language. Show that the string
a^{2}b^{2}c^{2}d^{2}has two leftmost derivations.

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

**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^{n}b^{n}c^{m}d^{m} : n,m≥1} ∪ {a^{n}b^{m}c^{n}d^{m} : n,m≥1}.
Write a grammar accepting this language. Show that the string
a^{2}b^{2}c^{2}d^{2}has two leftmost derivations.

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

**Reading exercise**

– Giveparse treerepresentation of previous derivation exercises.

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

– Are parse trees unique?

– There are some inherently ambiguous languages.

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

**Reading exercise**

– Giveparse treerepresentation of previous derivation exercises.

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

– Are parse trees unique?

– There are some inherently ambiguous languages.

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

Write a grammar accepting this language. Show that the string
a^{2}b^{2}c^{2}d^{2}has two leftmost derivations.

**Reading exercise**

– Giveparse treerepresentation of previous derivation exercises.

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

– Are parse trees unique?

– There are some inherently ambiguous languages.

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

Write a grammar accepting this language. Show that the string
a^{2}b^{2}c^{2}d^{2}has two leftmost derivations.

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

– What does that mean from application side?

**Reading exercise**

– Giveparse treerepresentation of previous derivation exercises.

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

– Are parse trees unique?

– There are some inherently ambiguous languages.

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

Write a grammar accepting this language. Show that the string
a^{2}b^{2}c^{2}d^{2}has two leftmost derivations.

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

– What does that mean from application side?

**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^{i}b^{j} : i≤2j}orL={a^{i}b^{j} : i<2j}orL={a^{i}b^{j} : i6=2j}
5. L={a^{i}b^{j}c^{k} : i=k}

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

8. L={w∈ {0,1}^{∗} : |w|_{a}=|w|_{b}}.

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

**Syntactic Ambiguity in English**

—Anthony G. Oettinger

**Syntactic Ambiguity in English**

Context-Free Grammars

Pushdown Automata

Properties of CFLs

**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

**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

**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

**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

**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

**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

**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

**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

**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

**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

**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

**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

**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

**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.

**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 , β )

**Semantics: acceptance via final states**

1. We say that a run

(q0,w0, β_{0}),(q1,w1, β_{1}), . . . ,(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.

**Semantics: acceptance via final states**

1. We say that a run

(q0,w0, β_{0}),(q1,w1, β_{1}), . . . ,(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,

**Semantics: acceptance via empty stack**

1. We say that a run

(q0,w0, β_{0}),(q1,w1, β_{1}), . . . ,(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)?

**Semantics: acceptance via empty stack**

1. We say that a run

(q0,w0, β_{0}),(q1,w1, β_{1}), . . . ,(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)?

**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⊥^{0}, as the start stack symbol, and in the
first transition replace it with⊥⊥^{0}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⊥^{0}.

– Empty Stack to Final state

– Replace the start stack symbol⊥^{0}and⊥⊥^{0}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⊥^{0}.

**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⊥^{0}, as the start stack symbol, and in the
first transition replace it with⊥⊥^{0}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⊥^{0}.

– Empty Stack to Final state

– Replace the start stack symbol⊥^{0}and⊥⊥^{0}before reading any symbol.

(Why?)

**Formal Construction: Empty stack to Final State**

LetP= (Q,Σ,Γ, δ,q0,⊥)be a PDA. We claim that the PDA
P^{0}= (Q^{0},Σ,Γ^{0}, δ^{0},q^{0}_{0},⊥^{0},F^{0})is such thatN(P) =L(P^{0}), where

1. Q^{0} =Q∪ {q^{0}_{0}} ∪ {qF}
2. Γ^{0}= Γ∪ {⊥^{0}}
3. F^{0}={qF}.
4. δ^{0}is such that

– δ^{0}(q,a,X) =δ(q,a,X)for allq∈QandX∈Γ,
– δ^{0}(q^{0}_{0}, ε,⊥^{0}) ={(q_{0},⊥⊥^{0})}and

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

**Formal Construction: Final State to Empty Stack**

LetP= (Q,Σ,Γ, δ,q0,⊥,F)be a PDA. We claim that the PDA
P^{0}= (Q^{0},Σ,Γ^{0}, δ^{0},q^{0}_{0},⊥^{0})is such thatL(P) =N(P^{0}), where

1. Q^{0} =Q∪ {q^{0}_{0}} ∪ {qF}
2. Γ^{0}= Γ∪ {⊥^{0}}
3. δ^{0}is such that

– δ^{0}(q,a,X) =δ(q,a,X)for allq∈QandX∈Γ,
– δ^{0}(q^{0}_{0}, ε,⊥^{0}) ={(q_{0},⊥⊥^{0})}and

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

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

**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=ε.

**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=ε.

**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=ε.

**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.

**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).

**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).

**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=γ_{1}⇒_{lm}γ_{2} ⇒_{lm}· · · ⇒_{lm}γ_{n}=w.

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

**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,

**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^{0},YX)or(q^{0}, ε).

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).

**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^{0},YX)or(q^{0}, ε).

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).

**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.

**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.

Context-Free Grammars

Pushdown Automata

Properties of CFLs

**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^{n}1^{n} : 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.

**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^{n}1^{n} : 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.

**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^{n}1^{n} : 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.

**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^{n}1^{n} : n≥1}.

### Theorem

### Theorem (DPDA 6= PDA)

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

**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.

**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.

**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^{i}wx^{i}y∈L.

**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^{i}wx^{i}y∈L.

**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=ε,

**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^{i}wx^{i}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.

**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^{i}wx^{i}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.

**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^{i}wx^{i}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.

**Pumping Lemma for CFLs**

### Theorem

^{i}wx^{i}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

**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^{i}wx^{i}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^{i}wx^{i}y6∈L.

=⇒

L∈Σ^{∗}is not acontext-freelanguage.

**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^{i}wx^{i}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

**Example**

Prove that the following languages are not context-free:

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

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

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

**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.

**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.

**Intersection and Complementaion**

### Theorem

Context-free languages are not closed underintersectionandcomplementation.

### Proof.

– Consider the languages

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

– Both languages are CFLs.

– What isL1∩L2?

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

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

**Intersection and Complementaion**

### Theorem

Context-free languages are not closed underintersectionandcomplementation.

### Proof.

– Consider the languages

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

– Both languages are CFLs.

– What isL1∩L2?

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

– Hence CFLs are not closed underintersection.

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

**Intersection and Complementaion**

### Theorem

Context-free languages are not closed underintersectionandcomplementation.

### Proof.

– Consider the languages

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

– Both languages are CFLs.

– What isL1∩L2?

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

– Hence CFLs are not closed underintersection.