PPT Slide

Theorem 3.4.1: for each n>1, there is a relation accepted by an n-NFA that is accepted by no n-DFA.

Theorem 3.4.2: for each DGSM M there exists a 2-DFA A with L(A) = {| x___*}.

Theorem 3.4.3 (projection theorem): {x1___*| _ x2, … , xn___* so __L(A)} is regular for each n-tape acceptor A.

Corollary 3.4.4: algorithms exist to determine if the relation accepted by an n-NFA is empty, finite or infinite.

Previous slide

Next slide

Back to first slide

View graphic version