**Lecture
13 (Non-context-free Languages), 10/11/17**

**Concepts, definitions (in italics):**

·
Role of stack characters in
transformation from PDAs to CFGs: they allowed us to pair up transitions for
rules of type 2, but they cannot appear in the rules (why?)

·
Chomsky Normal Form – how deep is
the tree for string of length n (length of longest derivation is 2n-1, did this
for homework)

·
Pumping Lemma for CFLs (p. 125)

o uses a CFG in Chomsky normal form, so all internal nodes
have 2 children except for those at lowest level (which have 1)

o tree terms: depth,
subtree rooted at node X

·
Negation
of PL property

o Converse of PL

o Contrapositive of
PL

·
Note:
Converse of PL is not true; some non-CF
languages also obey CF property

·
We can use the Pumping Lemma for
CFLs (actually, its contrapositive) to show that the following languages are
not context-free:

- L
_{1}= {**a**^{n}**b**^{n}**c**^{n}: n ≥ 0} - L
_{2}= {ww: w is over {0, 1} (or any alphabet with at least two characters)}

·
Teaching moment: for L_{2},
w = **0 ^{p }1 0^{p} 1**
does not work, but w =

·
Note: the intersection of regular
and context-free language is context free

o Given a DFA M1 and
a PDA M2, we can create a new PDA that
accepts the intersection of L(M1) and L(M2), whose states are pairs of states
from M1 and M2 respectively

o Example: L_{1}
= {w in {a,b,c}* where #a’s
= #b’s = #c’s}; L_{2} = **a**^{n} **b**^{n} **c**^{n} is the
intersection of L_{0} = a* b* c* and L_{1}. Since L_{0} is regular but L_{2}
is not CF, L_{1} is not CF

**Reading:**

- Chapter 2 through end of p. 129 (end of section 2.3)

**Skills:**

·
Know new definitions, understand new
concepts.

·
Understand the Pumping Lemma for
CFLs

·
Be able to apply either the pumping
lemma or the closure rules to show that a language is not regular