NFA with ε-moves: Formal definition

NFA with ε-moves
Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA. This
automaton replaces the transition function with the one that allows the empty string ε as a
possible input. The transitions without consuming an input symbol are called ε-transitions. In the
state diagrams, they are usually labelled with the Greek letter ε. ε-transitions provide a
convenient way of modelling the systems whose current states are not precisely known: i.e., if we
are modelling a system and it is not clear whether the current state (after processing some input
string) should be q or q', then we can add an ε-transition between these two states, thus putting
the automaton in both states simultaneously.
Formal definition
Nondeterministic Finite Automata with ε transitions (ε-NFA)

• A Non-Deterministic Finite Automata with ε transitions is a 5-tuple (Q, Σ, q 0, δ, F)
where – Q is a finite set (of states)
Σ is a finite alphabet of symbols –
q 0 ∈ Q is the start state
F ⊆ Q is the set of accepting states
δ is a function from Q x (Σ ∪ {ε}) to 2Q (transition function)
Conversion from NFA with ε to DFA

Non-deterministic finite automata (NFA) is a finite automata where for some cases
when a specific input is given to the current state, the machine goes to multiple
states or more than 1 states. It can contain ε move. It can be represented as M = {Q,
∑, δ, q 0, F}.
Were
1. Q: finite set of states

2. ∑: finite set of the input symbol
3. q 0: initial state
4. F: final state
5. δ: Transition function
NFA with ∈ move: If any FA contains ε transaction or move, the finite automata is
called NFA with ∈ move.
ε-closure: ε-closure for a given state A means a set of states which can be reached from the
state A with only ε(null) move including the state A itself.
Steps for converting NFA with ε to DFA:

Step 1: We will take the ε-closure for the starting state of NFA as a starting state of
DFA.
Step 2: Find the states for each input symbol that can be traversed from the present.
That means the union of transition value and their closures for each state of NFA
present in the current state of DFA.
Step 3: If we found a new state, take it as current state and repeat step 2.
Step 4: Repeat Step 2 and Step 3 until there is no new state present in the transition
table of DFA.
Step 5: Mark the states of DFA as a final state which contains the final state of NFA.
Example 1:
Convert the NFA with ε into its equivalent DFA.
Solution:
Let us obtain ε-closure of each state.
1. ε-closure {q0} = {q0, q1, q2}

2. ε-closure {q1} = {q1}
Now, let ε-closure {q0} = {q0, q1, q2} be state A.
Hence
δ'(A, 0) = ε-closure {δ((q0, q1, q2), 0) }

= ε-closure {δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0) }
= ε-closure {q3}
= {q3} call it as state B.
δ'(A, 1) = ε-closure {δ((q0, q1, q2), 1) }

= ε-closure {δ((q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1) }
= ε-closure {q3}
= {q3} = B.
The partial DFA will be
Now,
δ'(B, 0) = ε-closure {δ(q3, 0) }

= ϕ
δ'(B, 1) = ε-closure {δ(q3, 1) }
= ε-closure {q4}
= {q4} i.e. state C
For state C:
1. δ'(C, 0) = ε-closure {δ(q4, 0) }

=ϕ
2. δ'(C, 1) = ε-closure {δ(q4, 1) }
=ϕ
The DFA will be,

Example 2:
Convert the given NFA into its equivalent DFA.
Solution: Let us obtain the ε-closure of each state.
1. ε-closure(q0) = {q0, q1, q2}

2. ε-closure(q1) = {q1, q2}
3. ε-closure(q2) = {q2}
Now we will obtain δ' transition. Let ε-closure(q0) = {q0, q1, q2} call it as state A.
δ'(A, 0) = ε-closure{δ((q0, q1, q2), 0)}

= ε-closure{δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0)}
= ε-closure{q0}
= {q0, q1, q2}
δ'(A, 1) = ε-closure{δ((q0, q1, q2), 1)}

= ε-closure{δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1)}
= ε-closure{q1}
= {q1, q2} call it as state B
δ'(A, 2) = ε-closure{δ((q0, q1, q2), 2)}

= ε-closure{δ(q0, 2) ∪ δ(q1, 2) ∪ δ(q2, 2)}
= ε-closure{q2}
= {q2} call it state C
Thus we have obtained
1. δ'(A, 0) = A
2. δ'(A, 1) = B
3. δ'(A, 2) = C
The partial DFA will be:
Now we will find the transitions on states B and C for each input.
Hence
δ'(B, 0) = ε-closure{δ((q1, q2), 0)}

= ε-closure{δ(q1, 0) ∪ δ(q2, 0)}
= ε-closure{ϕ}
= ϕ
δ'(B, 1) = ε-closure{δ((q1, q2), 1)}

= ε-closure{δ(q1, 1) ∪ δ(q2, 1)}
= ε-closure{q1}
= {q1, q2} i.e. state B itself
δ'(B, 2) = ε-closure{δ((q1, q2), 2)}

= ε-closure{δ(q1, 2) ∪ δ(q2, 2)}
= ε-closure{q2}
= {q2} i.e. state C itself
Thus we have obtained
1. δ'(B, 0) = ϕ
2. δ'(B, 1) = B
3. δ'(B, 2) = C
The partial transition diagram will be
Now we will obtain transitions for C:
δ'(C, 0) = ε-closure{δ(q2, 0)}

= ε-closure{ϕ}
= ϕ

= ε-closure{ϕ}
= ϕ

= {q2}
Hence the DFA is

As A = {q0, q1, q2} in which final state q2 lies hence A is final state. B = {q1, q2} in which
the state q2 lies hence B is also final state. C = {q2}, the state q2 lies hence C is also a final
state.

NFA with ε-moves: Formal definition

Uploaded by

Copyright:

Available Formats

NFA with ε-moves: Formal definition

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

NFA with ε-moves: Formal definition

Uploaded by

Copyright:

Available Formats

NFA with ε-moves

Nondeterministic Finite Automata with ε transitions (ε-NFA)

Conversion from NFA with ε to DFA

1. Q: finite set of states

Steps for converting NFA with ε to DFA:

Let us obtain ε-closure of each state.

1. ε-closure {q0} = {q0, q1, q2}

δ'(A, 0) = ε-closure {δ((q0, q1, q2), 0) }

δ'(A, 1) = ε-closure {δ((q0, q1, q2), 1) }

The partial DFA will be

δ'(B, 0) = ε-closure {δ(q3, 0) }

1. δ'(C, 0) = ε-closure {δ(q4, 0) }

The DFA will be,

Solution: Let us obtain the ε-closure of each state.

1. ε-closure(q0) = {q0, q1, q2}

δ'(A, 0) = ε-closure{δ((q0, q1, q2), 0)}

δ'(A, 1) = ε-closure{δ((q0, q1, q2), 1)}

δ'(A, 2) = ε-closure{δ((q0, q1, q2), 2)}

Thus we have obtained

The partial DFA will be:

δ'(B, 0) = ε-closure{δ((q1, q2), 0)}

δ'(B, 1) = ε-closure{δ((q1, q2), 1)}

δ'(B, 2) = ε-closure{δ((q1, q2), 2)}

The partial transition diagram will be

Now we will obtain transitions for C:

δ'(C, 0) = ε-closure{δ(q2, 0)}

δ'(C, 1) = ε-closure{δ(q2, 1)}

δ'(C, 2) = ε-closure{δ(q2, 2)}

Hence the DFA is

You might also like