Non-context-free languages

Non-context-free languages
- are all regular languages context-free ?
- are some non-regular languages context-free ?
- are all non-regular languages context-free ?
[Section 2.3]
Pumping Lemma for CFLs
[Section 2.3]
Suppose we have a string with a parse tree where a variable is
repeated in its subtree.
Pumping Lemma for CFLs
[Section 2.3]
Thm 2.34 [the pumping lemma for CFLs]:
If A is a CFL, then there is a number p s.t. for every s ∈ A of
length ≥ p there exist u,v,x,y,z s.t.
0. s = uvxyz
1. for each i ≥ 0, uvixyiz ∈ A
2. |vy| > 0
3. |vxy| ≤ p
Pumping Lemma for CFLs
Example: B = { anbncn | n ≥ 0 }
[Section 2.3]
Pumping Lemma for CFLs
Example: C = { aibjck | 0 ≤ i ≤ j ≤ k }
[Section 2.3]
Pumping Lemma for CFLs
Example: D = { ww | w ∈ {0,1}* }
[Section 2.3]

Download Report