Automata Program NFA construction

Rule 1: There is an FA that accepts any symbol of Σ and there is an FA that accepts ε. If x is in Σ then give an FA that accepts x Give an FA that accepts ε.

Rule 2: Given FA1 that accepts regular expression r1 and FA2 that accepts regular expression r2 then make FA3 that accepts r1 | r2. Add a new start state s and make a ε-transition from this state to the start states of FA1 and FA2. Add a new final state f and make a ε-transition to this state from each of the final states of FA1 and FA2.

Rule 3: Given FA1 that accepts regular expression r1 and FA2 that accepts regular expression r2 then make FA3 that accepts r1·r2.

• Add a ε-transition from the final state of r1 to the start state of r2.
• The start state of FA3 is the start state of FA1 and the final state of FA3 is the final state of FA2.

Rule 4: Given FA1 that accepts regular expression r then make an FA2 that accepts r*.

• Add a new start state s and make a ε-transition from this state to the start state of FA1.
• Make a ε-transition from the final state of F1 to the new start state s.
• The final states of FA1 are no longer final and s is the final state of FA2.