<p>You agree that every GNFA has a corresponding regular expression. Then we know that each regular expression has a corresponding DFA, and an NFA.</p>
<p>Thus we can follow the path of GNFA-&gt; reg. exp.-&gt; NFA problem is solved!</p>

CC BY-SA 4.0
2024-04-29T11:59:00.737Z
2024-04-29T11:59:00.737Z
harshchy2210
<p>In Section 1.3 of the 3rd edition of Michael Sipser’s <em>Introduction to the Theory of Computation</em>, 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 <span class="math-container">$q$</span> states) recognizing the relevant regular language, and convert it to an equivalent <span class="math-container">$q+2$</span> 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 <span class="math-container">$q$</span> 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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-09-25T04:53:12.040Z
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).
holf
CC BY-SA 4.0
2024-04-29T13:18:42.110Z
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.
Chandra Chekuri
<fl.formal-languages><automata-theory>
Equivalence between GNFA and NFA/DFA
Abced Decba
# Equivalence between GNFA and NFA/DFA

(Asked by: username_0 on 2023-09-25)

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.

**Tags:** fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2024-04-29. Score: 1

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!


---

