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:
  1. 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.
  2. 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.
  3. 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.
  4. 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