09/10 - DFAs are Equivalent to NFAs 2.5

Question 1

Theorem

Answer 1

a language can be accepted by a DFA if and only if it can be accepted by an NFA.

The proof for this is VERY important

Question 2

Transition functions and NFA and DFA

Answer 2

• the transition function of a DFA maps a state and a symbol to a state, where as
• the transition function of an NFA maps a state and a symbol to a set of zero or more states.

Question 3

Theorem 2.5.1

Answer 3

Let N = (Q, Σ, δ, q, F ) be a nondeterministic finite automaton. There exists a deterministic finite automaton M, such that L(M) = L(N).

Question 4

Theorem 2.5.2

Answer 4

Let A be a language. Then A is regular if and only if there exists a nondeterministic finite automaton that accepts A.

Question 5

Changing NFA to DFA

Answer 5

We start by presenting the conversion for the case when N does not contain Ee-transitions. In other words, the state diagram of N does not contain any edge that has Ee as a label. (Later, we will extend the conversion to the
general case.) Let the DFA M be defined as M = (Q′
, Σ, δ′, q′, F′), where
• the set Q′ of states is equal to Q′ = P(Q); observe that |Q′| = 2|Q|,
• the start state q′ is equal to q′ = {q}; so M has the “same” start state as N,
• the set F′ of accept states is equal to the set of all elements R of Q′ having the property that R contains at least one accept state of N, i.e., F′ = {R ∈ Q′: R ∩ F 6= ∅},
• the transition function δ′ : Q′ × Σ → Q′ is defined as follows: For each R ∈ Q′ and for each a ∈ Σ,
δ′(R, a) = r∈R_U δ(r, a)

Question 6

the Ee-closure of r

Answer 6

the Ee-closure of r, denoted by C_Ee(r), is defined to be the set of all states of N that can be reached from r, by making zero or more Ee-transitions.For any state R of the DFA M (hence, R ⊆ Q), we define
C_Ee(R) = r∈R_U C_Ee(r).

Question 7

How do we define the start state q′ of the DFA M

Answer 7

q′ = C_Ee(q) = C_Ee({q}).