PPT Slide

Theorem 3.4.5 (2-NFA pumping lemma): Let L ____* ___* be a 2-NFA relation. Then there exists an integer N (depending on L) with the property that for each __L with len(z1)+len(z2) � N, there exist u1,u2,v1,v2,w1,w2___* so thati) zi = uiviwi, i = 1, 2ii) len(u1v1)+len(u2v2) Š N, and len(v1)+len(v2) � 1, andiii) __L for each k= 0, 1, 2, …

1

2

Theorem 3.4.6: Let L1 and L2 be two relations accepted by n-NFAs. Then L1 _ L2 is accepted by an n-NFA.

Theorem 3.4.7: For n>1 there are relations accepted by n-NFAs (in fact n-DFAs) whose complement and intersection are not accepted by an n-NFA.

Previous slide

Back to first slide

View graphic version