Question

An all- $\mathit{N}\mathit{F}\mathit{A}\mathit{M}\mathit{i}\mathit{s}\mathit{a}\mathbf{5}\mathbf{-}\mathit{t}\mathit{u}\mathit{p}\mathit{l}\mathit{e}\left(Q,\Sigma ,\delta ,q0,F\right)$that accepts $\mathbf{x}\mathbf{\in }\mathbf{\Sigma }\mathbf{*}$ if every possible state that M could be in after reading input M is a state from F. Note, in contrast, that an ordinary NFA accepts a string if some state among these possible states is an accept state. Prove that all-NFAs recognizes the class of regular languages.

Short answer

All-NFA recognizes the class of regular language.

Step-by-step solution

To State the NFA

The Using of subset construction algorithm, each NFA can be translated to an equivalent DFA; a DFA recognizing the same formal language. NFAs only recognize regular languages.

To Clear the Every DFA can be viewed as an all-NFA

Clearly every DFA can be viewed as an all – NFA.

LetLbe the any regular language.

Let$M=\left(Q,\sum ,\delta ,q_o,F\right)$ be the DFA that recognizesL.

Clearly for each input stringx,

There is exactly one possible state$q\in Q$ that M could be in after readingx.

Hence, if M is viewed as an all-NFA, then it acceptsxif and only if $q\in F$, which happens if and only if $x\in L$.

Therefore, when M is viewed as an all – NFA, it also recognizes the language L.

Thus, every regular language is recognized by some all – NFA.

Proof for the Step 2 as follows:

Let$N=\left(Q,\sum ,\delta ,q_o,F\right)$ be an all – NFA.

Let A be the language recognized by N.

To Simplify the prove that expression

Now, prove that A is regular.

Constructing a DFA $M=\left(Q\text{'},\sum ,\delta \text{'},q_o^{\text{'}},F\right)$that recognizes A.

$M=\left(Q\text{'},\sum ,\delta \text{'},q_o^{\text{'}},F\right)$

Where $Q\text{'}=P\left(Q\right)$, where $P\left(Q\right)$is the set of subsets of Q

For $R\in Q\text{'}$and $a\in \sum$

For any subset$S\subset Q,E\left(S\right)$is the set of all sates$q\in Q$that can be reached from S by travelling along arrows including the members of S themselves.

$q_o^{\text{'}}=E\left(\left\{q_o\right\}\right)$

$F\text{'}=\left\{R\in Q\text{'}|R\subset F\right\}$

To Consider an Input String

Now, consider an input string $x\in \sum *$.

Let R be the set of states that the all NFA N could be in after reading x.

Then x is fed to the DFA M defined above, M will end at state R.

By the definition of all-NFA , have $x\in A\iff R\subset F$.

By the definition of M, M accepts x if and only if $R\in F\text{'}$, which is equivalent to $R\subset F$.

Hence M recognizes A.

Therefore, every all-NFA recognizes a regular language.