[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 L_{1} and L_{2}

- Create a new start state.
- Make a
transition from the new start state to each of the original start states.

## Concatenation of L_{1} and L_{2}

- Put a
transition from each final state of L
_{1} to the initial state of
L
_{2
} - Make the original final states of L
_{1} 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
}