(b) Repeat the following until no new arcs can be added:
(1) Find a state (A, B) that lacks a tran si tion for some x in Σ.
(2) Add a transition on x from state (A, B) to state ( ( , ),
δ A x
δ ( , ))
B x . (If this state does not already exist, create it).
Nega tion of L 1
(a) Start with a complete DFA, not with an NFA
(b) Make every final state nonfinal and every nonfinal state final.
Kleene star of L 1
(a) Make a new start state; connect it to the original start state with a
λ-transition.
(b) Make a new final state; connect the original final state (which
becomes nonfinal) to it with λ-transitions.
(c) Connect the new start state and new final state with a pair of
λ-transitions.
Reverse of L 1
(a) Start with an automaton with just one final state.
(b) Make the initial state final and final state initial.
(c) Reverse the direction of every arc.
The same construction is used for both intersection and set difference. The
distinction is in how the final states are selected.
Inter sec tion
Make a state (A, B) as final if both
(i) A is a final state in L 1 and
(ii) B is a final state in L 2
Set Dif fer ence
Mark a state (A, B) as final if A is a final state in L 1 , but B is not a final state in L 2 .
1.8 PUMPING LEMMA
1.8.1 Prin ci ple of Pumping Lemma
• If an infi nite lan guage is reg u lar, it can be defined by a DFA.
• The DFA has some finite num ber of states (say).
• Since the lan guage is infi nite, some strings of the lan guage should have
length > n.
DFA and NFA
93