Michael Sipser Edition 3 Exercise 1 Question 38 (Page No. 89)

Question

An $\text{all-NFA}$  $M$ is a $\text{5-tuple}$ $(Q, Σ, δ, q_{0}, F)$ that accepts $x\in\sum^{*}$ if every possible state that $M$ could be in after reading input $x$ is a state from $F.$ Note $,$ in contrast, that an ordinary $\text{NFA}$ accepts a string if some state among these possible states is an accept state$.$ Prove that $\text{all-NFAs}$ recognize the class of regular languages$.$

Comments

can someone explain this question?

---

Here, in the question, all-NFA is a newly created NFA.

Now, we tried to prove, if  NFA from definition , accept it's states, then all-NFA also accept class of regular language

---

I didn't get u @srestha :(

---

tried. U can chk now

Answer 1

 

An all-NFA  $M$ is a $5-$tuple $(Q,Σ,δ,q_{0},F)$ that accepts $x∈∑^{∗}$ if every possible state that $M$ could be in after reading input $x$ 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 recognize the class of regular languages.

 

Say N be the all-NFA - where reading every input symbol either it reach state F directly which leads it to the final state. Suppose N doesnot reach to final state directly, then there must be a $\epsilon$ transition to reach the final state. Generally we know, NFA doesnot care about every state, but it cares about final production. But here NFA works like every state is a final state. So, it accepts $\left ( a+b \right )^{*}$ or $\sum$$^{*}$.Therefore we can conclude, all-NFA must recognize class of regular languages. Hence proved.

Comments

understood

but what does this means?

NFA doesnot care about every state, but it cares about final production

 

---

means describing an NFA of given language sometimes much easier than DFA for given language.