09/07 - Nondeterministic Finite Automata 2.4

Question 1

Definition of Σ_Ee

Answer 1

For any alphabet Σ, we define Σ_Ee to be the set Σ_Ee = Σ ∪ {Ee}.
Recall the notion of a power set: For any set Q, the power set of Q, denoted by P(Q), is the set of all subsets of Q, i.e.,
P(Q) = {R : R ⊆ Q}.

Question 2

Definition 2.4.1: A nondeterministic finite automaton (NFA)

Answer 2

A nondeterministic finite automaton (NFA) is a 5-tuple
M = (Q,Σ,δ,q,F), where
1. Q is a finite set, whose elements are called states,
2. Σ is a finite set, called the alphabet; the elements of Σ are called symbols,
3. δ : Q × Σ_Ee → P(Q) is a function, called the transition function,
4. q is an element of Q; it is called the start state,
5. F is a subset of Q; the elements of F are called accept states.

As for DFAs, the transition function δ can be thought of as the “program” of the finite automaton M = (Q,Σ,δ,q,F):

• Let r ∈ Q, and let a ∈ Σ_Ee. Then δ(r, a) is a (possibly empty) subset of Q. If the NFA M is in state r, and if it reads a (where a may be the empty string ǫ), then M can switch from state r to any state in δ(r, a). If δ(r, a) = ∅, then M cannot continue and the computation hangs.

Question 3

Definition 2.4.2

Answer 3

Let M = (Q,Σ,δ,q,F) be an NFA, and let w ∈ Σ^∗. We say that M accepts w, if w can be written as w = y_1y_2 …y_m, where y_i ∈ Σ_Ee for all i with 1 ≤ i ≤ m, and there exists a sequence r_0,r_1,…,r_m of states in Q, such that
• r_0 = q,
• r_i+1 ∈ δ(r_i ,y_i+1), for i = 0, 1, …, m−1, and
• r_m ∈ F.
Otherwise, we say that M rejects the string w.

Question 4

Definition 2.4.3

Answer 4

Let M = (Q,Σ,δ,q,F) be an NFA. The language L(M) accepted by M is defined as
L(M) = {w ∈ Σ^∗ : M accepts w}.

Question 5

As for DFAs, the transition function δ can be thought of as the “program” of the finite automaton M = (Q,Σ,δ,q,F):

Answer 5

Let r ∈ Q, and let a ∈ Σ_Ee. Then δ(r, a) is a (possibly empty) subset of Q. If the NFA M is in state r, and if it reads a (where a maybe the empty string Ee), then M can switch from state r to any state in δ(r, a). If δ(r, a) = ∅, then M cannot continue and the computation hangs.