Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.

Question

Bipin Tiwari · Accepted Answer

A DFA is a finite automation consisting of five tuples: (Q, Σ, δ, q0, F) where: Q is a finite set of states. Σ is a finite set of symbols called the alphabet. δ is the transition function where δ: Q × Σ → Q q0 is the initial state from where any input is processed (q0 ∈ Q). F is a set of final state/states of Q (F ⊆ Q). An NFA is finite automation consisting of five tuples: (Q, Σ, δ, q0, F) where: Q is a finite set of states. Σ is a finite set of symbols called the alphabet. δ is the transition function where δ: Q × Σ → 2^Q (Here the power set of Q (2^Q) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states) q0 is the initial state from where any input is processed (q0 ∈ Q). F is a set of final state/states of Q (F ⊆ Q). Conversion from NFA to DFA: Suppose there is an NFA N < Q, ∑, q0, δ, F > that recognizes a language L. Then the DFA D < Q’, ∑, q0, δ’, F’ > can be constructed for language L as: Step 1: Initially Q’ = ɸ. Step 2: Add q0 to Q’. Step 3: For each state in Q’, find the possible set of states for each input symbol using the transition function of NFA. If this set of states is not in Q’, add it to Q’. Step 4: Final state of DFA will be all states containing F (final states of NFA) Example Consider the following NFA shown in Figure 1. The following are the various parameters for NFA. Q = { q0, q1, q2 } ∑ = ( a, b ) F = { q2 } δ (Transition Function of NFA) Step 1: Q’ = ɸ Step 2: Q’ = {q0} Step 3: For each state in Q’, find the states for each input symbol. Currently, a state in Q’ is q0, find moves from q0 on input symbols a and b using the transition function of NFA and update the transition table of DFA. δ’ (Transition Function of DFA) Now { q0, q1 } will be considered as a single state. As its entry is not in Q’, add it to Q’. So Q’ = { q0, { q0, q1 } } Now, moves from state { q0, q1 } on different input symbols are not present in the transition table of DFA, we will calculate it like this: δ’ ( { q0, q1 }, a ) = δ ( q0, a ) ∪ δ ( q1, a ) = { q0, q1 } δ’ ( { q0, q1 }, b ) = δ ( q0, b ) ∪ δ ( q1, b ) = { q0, q2 } Now we will update the transition table of DFA. δ’ (Transition Function of DFA) Now { q0, q2 } will be considered as a single state. As its entry is not in Q’, add it to Q’. So Q’ = { q0, { q0, q1 }, { q0, q2 } } Now, moves from state {q0, q2} on different input symbols are not present in the transition table of DFA, we will calculate it like: δ’ ( { q0, q2 }, a ) = δ ( q0, a ) ∪ δ ( q2, a ) = { q0, q1 } δ’ ( { q0, q2 }, b ) = δ ( q0, b ) ∪ δ ( q2, b ) = { q0 } Now we will update the transition table of DFA. δ’ (Transition Function of DFA) As there is no new state generated, we are done with the conversion. The final state of DFA will be state which has q2 as its component i.e., { q0, q2 } The following are the various parameters for DFA. Q’ = { q0, { q0, q1 }, { q0, q2 } } ∑ = ( a, b ) F = { { q0, q2 } } and transition function δ’ as shown above. The final DFA for the above NFA has been shown in Figure 2.

Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.

Leave your Answer:

Hits Counter

Question

Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.

Leave your Answer: