An all-NFA M is a 5-tuple (Q,Σ,δ,q0 ,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.