Regular expressions and DFA

Question

Describe the theorem that a language L is recognized by a DFA if and only if L is illustrated by a regular expression.

Answer 1

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!

– (R₁ ∪ R₂), where R₁ and R₂ are reg. exprs.
– (R₁ ° R₂), where R₁ and R₂ are reg. exprs.
– (R₁*), where R₁ 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 = w₁ w₂ w₃…w_k

where each wi ∈ Σ*, and there is a path from the start state to an accept state in which the i^th transition traversed is labeled with R for which w_i ∈ 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 q_i and q_j do

Modify the regular expression from q_i to q_j to “add in” the impact of q_rip

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 q_rip)

Proof: (two directions, first accepted by G → accepted by G’)

• if G accepts string w, then it does so by entering states:
q₀, q₁, q₂, q₃, …, q_accept

• if none are q_rip then G’ accepts w (G’=G on these states)

• else, break state sequence into runs of q_rip:
q₀ q₁ …q_i q_rip q_rip …q_rip q_j …q_accept

• string from q_i to first qrip must satisfy R₁, string from last q_rip to q_j must satisfy R₃, and intermediate string in the red block must satisfy (R₂)*. Thus transition from q_i to q_j in G’ allows this string; thus G’ accepts w

• if G’ accepts string w, then every transition from q_i to q_j traversed in G’ corresponds to either a transition from q_i to q_j in G or transitions from q_i to q_j via q_rip 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