There are several operations defined on languages:
L
L
1
2
∪
: strings in either L 1 or L 2 .
L
L
1
2
∩
: strings in both L 1 and L 2 .
L L
1 2 : strings com posed of one string from L, fol lowed by one
string from L 2 .
–L 2 : All strings (over the same alpha bet) not in L 1 .
L 1
* : Zero or more strings from L 1 con cat e nated together
L L
1
2
−
: strings in L 1 that are not in L 2 .
L
R
1
: strings in L 1 , reversed.
We shall show that the set of regular languages is closed under each of
these operations.
1.7.2 Union, Con cat e na tion, Nega tion, Kleene Star, Reverse
The general approach is as follows:
(i) Build automata (DFA or NFA) for each of the languages involved.
(ii) Show how to combine the automata in order to form a new
automaton which recognizes the desired language.
(iii) Since the language is represented by NFA/DFA, we shall
conclude that the language is regular.
Union of L 1 and L 2
(a) Create a new start state
(b) Make a λ-transition from the new start state to each of the original
start states.
Con cat e na tion of L 1 and L 2
(a) Put a λ-transition from each final state of L 1 to the initial state of L 2 .
(b) Make the original final states of L 1 nonfinal.
1.7.3 Inter sec tion and Set Dif fer ence
Just as with the other operations, it can be proved that regular languages are
closed under intersection and set difference by starting with automata for the
initial languages, and constructing a new automaton that represents the
operation applied to the initial languages.
In this construction, a completely new machine is formed, whose states are
labelled with an ordered pair of state names: the first element of each pair is a
state from L 1 and the second element of each pair is a state from L 2 .
(a) Begin by creating a start state whose label is (start state of L 1 , start
state of L 2 ).
92
Theory of Automata, Formal Languages and Computation
L
L
1
2
∪
: strings in either L 1 or L 2 .
L
L
1
2
∩
: strings in both L 1 and L 2 .
L L
1 2 : strings com posed of one string from L, fol lowed by one
string from L 2 .
–L 2 : All strings (over the same alpha bet) not in L 1 .
L 1
* : Zero or more strings from L 1 con cat e nated together
L L
1
2
−
: strings in L 1 that are not in L 2 .
L
R
1
: strings in L 1 , reversed.
We shall show that the set of regular languages is closed under each of
these operations.
1.7.2 Union, Con cat e na tion, Nega tion, Kleene Star, Reverse
The general approach is as follows:
(i) Build automata (DFA or NFA) for each of the languages involved.
(ii) Show how to combine the automata in order to form a new
automaton which recognizes the desired language.
(iii) Since the language is represented by NFA/DFA, we shall
conclude that the language is regular.
Union of L 1 and L 2
(a) Create a new start state
(b) Make a λ-transition from the new start state to each of the original
start states.
Con cat e na tion of L 1 and L 2
(a) Put a λ-transition from each final state of L 1 to the initial state of L 2 .
(b) Make the original final states of L 1 nonfinal.
1.7.3 Inter sec tion and Set Dif fer ence
Just as with the other operations, it can be proved that regular languages are
closed under intersection and set difference by starting with automata for the
initial languages, and constructing a new automaton that represents the
operation applied to the initial languages.
In this construction, a completely new machine is formed, whose states are
labelled with an ordered pair of state names: the first element of each pair is a
state from L 1 and the second element of each pair is a state from L 2 .
(a) Begin by creating a start state whose label is (start state of L 1 , start
state of L 2 ).
92
Theory of Automata, Formal Languages and Computation