edited by
398 views
0 votes
0 votes

There are some simplefications to the constructions of Theorem, where we converted a regular expression
to an $\in-NFA$ Here are three$:$

  1. For the union operator instead of creating new start and accepting states, merge the two start states into one state with all the transitions of both start states. Likewise, merge the two accepting states having all transitions to either go to the merged state instead.
  2. For the concatenation operator merge the accepting state of the first automaton with the start state of the second.
  3. For the closure operator simply add $\in-$transitions from the accepting state to the start state and vice-versa.


Each of these simplifications by themselves still yield a correct construction$;$ that is, the resulting $\in-NFA$ for any regular expression accepts the language of the expression. Which subsets of changes $(1),(2)$ and $(3)$ may be made to the construction together , while still yielding a correct automaton for every regular expession$?$

edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
3
0 votes
0 votes
0 answers
4