Computer Science 456/656: Automata and Formal Languages
Spring 2001
Proof of Theorem Given in Class
Wednesday, Wednesday 24, 2001
Theorem: Let M be a DFA,
and let L be the language accepted by M.
Then there is some regular expression that
generates L.
Proof: By induction.
We assume that the statement
already holds for all DFA's that have fewer edges than M.
Case 1: M has no transitions.
If the start state of M is a final state, L is the language of
just one string, the empty string. The regular expression is just Lambda.
Otherwise, L is the empty language. The regular expression is just
the empty set symbol.
Case 2: M has at least one transition.
Pick one transition, call it e.
The start state for e is some state qi,
the end state for e is some state qj,
and the symbol for e is some alphabet symbol a.
Consider the following four DFA's:
-
M1, consisting of all the same states
as M, the same start state as M, the same final states as M,
and all the same transitions as M except for e.
-
M2, consisting of all the same states
as M, the same start state as M,
all the same transitions as M except for e,
and just one final state, qi.
-
M3, consisting of all the same states
as M, all the same transitions as M except for e,
start state qj,
and just one final state, qi.
-
M4, consisting of all the same states
as M, with start state qj,
all the same transitions as M except for e,
and the same final states as M.
Let Li be the language accepted by
Mi. By the inductive hypothesis, since each Mi
has fewer transitions than M, there is a regular expression
xi that generates Li.
Then the following regular expression generates L:
y = x1+x2(ax3)*ax4

Back to
Course Page