[Overview] [Previous]
[Next]
Closure II: Union, Concatenation, Negation, Kleene Star, Reverse
General Approach
- Build automata (dfas or nfas) for each of the languages involved.
- Show how to combine the automata to create a new automaton
that recognizes the desired language.
- Since the language is represented by an nfa or dfa, conclude
that the language is regular.
Union of L1 and L2
- Create a new start state.
- Make a
transition from the new start state to each of the original start states.
Concatenation of L1 and L2
- Put a
transition from each final state of L1 to the initial state of
L
2
- Make the original final states of L1 nonfinal
Negation of L1
- Start with a (complete) dfa, not with an nfa.
- Make every final state nonfinal and every nonfinal state final.
Kleene Star of L1
- Make a new start state; connect it to the original start state with a
transition.
- Make a new final state; connect the original final states (which become
nonfinal) to it with
transitions.
- Connect the new start state and new final state with a pair of
transitions.
Reverse of L1
- Start with an automaton with just one final state.
- Make the initial state final and the final state initial.
- Reverse the direction of every arc.
Copyright © 1996 by David Matuszek
Last modified Feb 13, 1996