Verified
Theorem: a language L is recognized by a DFA if and only if L is described by a regular expression.
Must prove two directions:
(⇒) L is recognized by a DFA implies L is described by a regular expression
(⇐) L is described by a regular expression implies L is recognized by a DFA.
(⇐) L is described by a regular expression implies L is recognized by a DFA
Proof: given regular expression R we will build a NFA that recognizes L(R).
Then NFA,DFA equivalence implies that we have a DFA for L(R)
First show there’s an NFA for the basic regular expressions:
– a, for some a ∈ Σ
– ε, the empty string
– Ø, the empty set
The work is already done by closure properties!
– (R1 ∪ R2), where R1 and R2 are reg. exprs.
– (R1 ° R2), where R1 and R2 are reg. exprs.
– (R1*), where R1 is a regular expression
(⇒) L is recognized by a DFA implies L is described by a regular expression
Proof: given DFA M that recognizes L, we will build a regular expression that does the same thing.
• GNFA definition:
– it is a NFA, but may have regular expressions labeling its transitions
– GNFA accepts string w ∈ Σ* if w can be written
w = w1 w2 w3…wk
where each wi ∈ Σ*, and there is a path from the start state to an accept state in which the ith transition traversed is labeled with R for which wi ∈ L(R)
• We will convert GNFA to Reg. Expr.
• This shows every DFA can be converted, since a DFA is a GNFA.
Converting a GNFA into a regular expression: induction on number of states. The regular expression R labeling the single transition describes the language recognized by the GNFA R (need another minor trick to handle two-state machines with loops)
– how to repair the transitions:
– for every pair of states qi and qj do
Modify the regular expression from qi to qj to “add in” the impact of qrip
summary:
DFA M → k-state GNFA → (k-1)-state GNFA → (k-2)-state GNFA →…→ 2-state GNFA → R
– want to prove that this procedure is correct, i.e. L(R) = language recognized by M
• DFA M equivalent to k-state GNFA
• i-state GNFA equivalent to (i-1)-state GNFA (we will prove…)
• 2-state GFNA equivalent to R
Claim: i-state GNFA G equivalent to (i-1)-state GNFA G’ (obtained by removing qrip)
Proof: (two directions, first accepted by G → accepted by G’)
• if G accepts string w, then it does so by entering states:
q0, q1, q2, q3, …, qaccept
• if none are qrip then G’ accepts w (G’=G on these states)
• else, break state sequence into runs of qrip:
q0 q1 …qi qrip qrip …qrip qj …qaccept
• string from qi to first qrip must satisfy R1, string from last qrip to qj must satisfy R3, and intermediate string in the red block must satisfy (R2)*. Thus transition from qi to qj in G’ allows this string; thus G’ accepts w
• if G’ accepts string w, then every transition from qi to qj traversed in G’ corresponds to either a transition from qi to qj in G or transitions from qi to qj via qrip in G
• In both cases get a corresponding transition in G, putting these together shows G accepts w.
• Conclude: G and G’ recognize the same language.
Theorem: a language L is recognized by a DFA iff L is described by a regular expr.
• Languages recognized by a DFA are termed as regular languages.
• Rephrasing what we know so far:
– regular languages closed under 3 operations
– NFA recognize exactly the regular languages
– regular expressions describe exactly the regular languages