(iii) The regular expression ∅ denotes the language ∅; no strings
belong to this language, not even the empty string.
(iv) For juxtaposition, strings in L r
( )
1 followed by strings in L r
( )
2 , we
chain the NFAs together as shown.
(v) The “+” denotes “or” in a regular expression, we would use an
NFA with a choice of paths.
(vi) The star (*) denotes zero or more applications of the regular
expression, hence a loop has to be set up in the NFA.
1.4.6 NFAs to Reg u lar Expres sion
The basic approach to convert NFA, to Regular Expressions is as follows:
(i) If an NFA has more than one final state, convert it to an NFA with
only one final state. Make the original final states nonfinal, and
add a λ-transition from each to the new (single) final state.
DFA and NFA
83
NFA for ∅
NFA for rr 12
λ
λ
λ
Mr () 1
Mr () 2
NFA for +
rr 1 2
λ
Mr () 1
Mr () 2
λ
λ
λ
λ
λ
Mr () 1
λ
λ