A 3NFA is defined as a 5-tuple M = (Q, , 8, 90, F) exactly as...

  

Transcribed Image Text:

A 3NFA is defined as a 5-tuple M = (Q, , 8, 90, F) exactly as an NFA. However, the acceptance is defined differently. An NFA accepts a string w if there is at least one accept state that can be reached from go when reading the input w. A 3NFA accepts a string w if at least 3 accept states can be reached from go when reading the input w. (a) Prove that every regular language is recognized by a 3NFA. (b) Prove that every 3NFA recognizes a regular language. A 3NFA is defined as a 5-tuple M = (Q, , 8, 90, F) exactly as an NFA. However, the acceptance is defined differently. An NFA accepts a string w if there is at least one accept state that can be reached from go when reading the input w. A 3NFA accepts a string w if at least 3 accept states can be reached from go when reading the input w. (a) Prove that every regular language is recognized by a 3NFA. (b) Prove that every 3NFA recognizes a regular language.