Showing posts with label NFA. Show all posts
Showing posts with label NFA. Show all posts

Thursday, April 5, 2012

Conversion from NFA to DFA


Let MN = (QN, ΣN, δN, q0, AN) be an NFA and accepts the language L(MN). There should be an equivalent DFA MD = (QD, ΣD, δD, q0, AD) such that L(MD) = L(MN). The procedure to convert an NFA to its equivalent DFA is shown below:

Step1:
The start state of NFA MN is the start state of DFA MD. So, add q0(which is the start state of NFA) to QD and find the transitions from this state. The way to obtain different transitions is shown in step2.
Step2:
For each state [qi, qj,….qk] in QD, the transitions for each input symbol in Σ can be obtained as shown below:
  1. δD([qi, qj,….qk], a) = δN(qi, a) U δN(qj, a) U ……δN(qk, a)
= [ql, qm,….qn] say.
  1. Add the state [ql, qm,….qn] to QD, if it is not already in QD.
  2. Add the transition from [qi, qj,….qk] to [ql, qm,….qn] on the input symbol a iff the state [ql, qm,….qn] is added to QD in the previous step.
Step3:
The state [qa, qb,….qc] ∈ QD is the final state, if at least one of the state in qa, qb, ….. qc ∈ AN i.e., at least one of the component in [qa, qb,….qc] should be the final state of NFA.
Step4:
If epsilon (∈) is accepted by NFA, then start state q0 of DFA is made the final state.

Obtain an NFA to accept the following language L = {w | w ∈ abab(power)n or aba(power)n where n >=0}


The machine to accept either ababn or aban where n 0 is shown below:


Non deterministic finite automata(NFA)


Definition: An NFA is a 5-tuple or quintuple M = (Q, Σ, δ, q0, A) where
Q is non empty, finite set of states.
Σ is non empty, finite set of input alphabets.
δ is transition function which is a mapping from
Q x {Σ U ε} to subsets of 2Q. This function shows
the change of state from one state to a set of states
based on the input symbol.
q0 ∈ Q is the start state.
A ⊆ Q is set of final states.

Acceptance of language

Definition: Let M = (Q, Σ, δ, q0, A) be a DFA where Q is set of finite states, Σ is set of input alphabets (from which a string can be formed), δ is transition function from Q x {ΣU} to 2Q, q0 is the start state and A is the final or accepting state. The string (also called language) w accepted by an NFA can be defined in formal notation as:


L(M) = { w | w ∈ Σ*and δ*(q0, w) = Q with atleast one
Component of Q in A}