AFL

State the regular pumping lemma

L satisfies the pumping lemma with pumping number n if for every word w ∈ L with |w| <= n, we have:

(1) w=xyz

(2) |y|>0

(3) |xy|<=n

(4) x y^k z in L for every k a natural number(or 0)

Prove the regular pumping lemma

If regular, generated by a deterministic automata.

Let n=|Q|, number of states in DFA.

w=a0 a1.. an-1 v for word in l length more than n.

DFA goes through n+1 states q0 to qn.

By pigeonhole, at least one state repeats, so qi=qj for 1<=i<=j<=n

let x=a0…ai-1, y=ai…aj-1, z=aj…an-1v

Clearly |y|>0, |xy|<=n and reading y is a loop in the DFA from ai to ai.

So xy^kz in L for all k natural, so done

State the context free pumping lemma

L satisfies the context-free pumping lemma with pumping number n if for every word w ∈ L with |w| >= n, we have:

(1) w=xuyvz

(2) |uv|>0

(3) |uyv|<=n

(4) w=x u^k y v^k z is in L for all k a natural number (or 0)

Prove the context free pumping lemma

If L context-free, then a grammar in CNF generates it.

let m=|V| and set n=2^m +1

Any w in L with length n or more has a parse tree with height at least m+1.

On a root to leaf path of length m+2 there are m+1 variable nodes.

By pigeonhole, some variable, say A, appears at least twice.

Let T0 and T1 be parse subtrees rooted at the first and second instances of A respectively.

Let w=xuyvz with T1 generating y and T0 generating uyv.

Replace T1 recursively to generate xu^kyv^kz in L for all k>=0.

What is Chomsky Normal Form

A→BC and A→a

What is a regular language, context free language, non contracting language

regular: A→a and A→aB

context-free: A→β for |β|>=1
non-contracting: α → β and |α| <= |β|