I came across generalized nondeterministic finite automata (GNFAs) in Sipser\'s

Question

I came across generalized nondeterministic finite automata (GNFAs) in Sipser's Introduction to the Theory of Computation. These are automata where transitions are labelled with regular expressions, rather than single symbols from the alphabet. I thought he would explain why GNFAs are allowed. I mean, an appropriate explanation would be that GNFAs are equivalent to NFAs, or GNFAs are equivalent to DFAs or some such argument. But I couldn't find any such explanation in the book.

Online, I read in this article that you can convert a GNFA to an NFA as follows:

For each transition arrow in the GNFA, we insert the complete automaton accepting the language generated by the transition arrow

Explanation / Answer

You are correct in your understanding of the construction: For every transition arrow, say from state A to state B in the GNFA labeled by a regular expression R, you replace that transition by the NFA, N, for R, with an ?-transition from A to the start state of N and ?-transitions from the final states of N (which you then "un-finalize") to state B. Do this for every transition in the GNFA and you'll wind up with an ordinary NFA.

To show that the two accept the same language, it's enough to rely on the previous result (Lemma 1.55 in Sipser) that any regular expression denotes a language that is recognized by a NFA

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.