Figure 3.14
Figure 3.15
The process of converting an nfa to a regular expression is mechanical but
tedious. It leads to regular expressions that are complicated and of little practical
use. The main reason for presenting this process is that it gives the idea for the
proof of an important result.
Theorem 3.2
Let L be a regular language. Then there exists a regular expression r such that L
= L(r).
Proof: If L is regular, there exists an nfa for it. We can assume without loss of
generality, that this nfa has a single final state, distinct from its initial state. We
convert this nfa to a complete generalized transition graph and apply the
procedure nfa-to-rex to it. This yields the required regular expression r.