1
$\begingroup$

In Section 1.3 of the 3rd edition of Michael Sipser’s Introduction to the Theory of Computation, it is proven that regular expressions are equivalent to deterministic finite automatas (DFAs). That is, every language generated by a regular expression is regular (has a DFA recognizing it) (1), and every regular language is generated by some regular expression (2). The forward direction (1) is proven inductively based on the recursive definition of regular expressions, and the converse is proven as follows: take a DFA (of say $q$ states) recognizing the relevant regular language, and convert it to an equivalent $q+2$ state generalized non-deterministic finite automata (GNFA), and then repeatedly iterate a conversion step that removes a single state of the GNFA and modifies the transition function to yield an equivalent GNFA. After $q$ iterations of this conversion step what remains is a two state GNFA with a single transition arrow; the regular expression on this arrow is what is desired.

My question: why are GNFAs equivalent to NFAs? Showing that a NFA has equivalent GNFA is easy; it is a step in the proof by Sipser. On the other hand, I’m not so sure how to show every GNFA has an equivalent NFA/DFA.

$\endgroup$
2
  • 5
    $\begingroup$ That is not really needed in the proof you mention. A DFA A is transformed into a GNFA K of the form Q1 --R--> Q2 recognizing the same languages. The language recognized by K is the language of the regexp R, hence the DFA A is recognized by the regexp R, which proves 2. Now orthogonally, it proves that GNFA and DFA recognize the same set of languages. The transformation can be applied on any GNFA to reduce it to a GNFA with two states whose language is hence recognized by a regexp and hence by a DFA from (1). $\endgroup$
    – holf
    Commented Sep 25, 2023 at 4:53
  • $\begingroup$ If you know the Thompson construction to convert a regular expression into an NFA with single start and single accepting state, you can use that construction on each arc of the GNFA to see that one gets an equivalent NFA. The proof is quite straight forward/intuitive though a formal one may be laborious - one needs to walk through the definition of what strings are accepted by an NFA. $\endgroup$ Commented Apr 29 at 13:18

1 Answer 1

1
$\begingroup$

You agree that every GNFA has a corresponding regular expression. Then we know that each regular expression has a corresponding DFA, and an NFA.

Thus we can follow the path of GNFA-> reg. exp.-> NFA problem is solved!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.