Can we convert a non-deterministic finite automata into a deterministic finite Automata?

Compiler Design Programming Languages Computer Programming

Yes, we can convert a NFA into DFA. For every NFA there exists an equivalent DFA. The equivalence is defined in terms of languages acceptance. Since NFA is nothing but a finite automata in which zero, one or more transitions on an input symbols are permitted. It can always construct finite automata which will simulate all moves of DFA on a particular input symbol in parallel, then get a finite automata in which there will be exactly one transition on every input symbol. Here, corresponding to a NFA there exist a DFA. To construct DFA equivalent to NFA, it should be remembered that states of DFA are a collection of states of NFA.

Algorithm NFA – to – DFA

Input − NFA with set of states N = {n₀,n₁……n_n}, with start state n₀.

Output − DFA, with set of states D′={d₀,d₁,d₂……d_n}, with start state d₀.

d₀=ε−closure (n₀)

D′={d₀}

set d₀ unmarked

while there is an unmarked state d in D′. {    set d marked {       For each input symbol 'a' {          Let T be a set of states in NFA to which there is a transition on 'a' from some state ni in d d′=ε−closure (T).          If d′ is not already present in D′ {             D′=D′∪{d′}             Add transition d→d′,labeled 'a'             set d′ unmarked          }       }    } }

Example − Design Lexical Analyzer for the following LEX Program.

AUXILIARY DEFINITION S letter = A|B|C|…….|Z digit = 0 |1|2|………|9 TRANSLATION RULES begin    {return 1} end      {return 2} If       {return 3} then     {return 4} else     {return 5} letter  (letter+digit)* {value=Install ( );return 6} digit + {value=Install ( );return 7} <      {value=1;return 8} <=     {value=2;return 8} =      {value=3;return 8} < >    {value=4;return 8} >      {value=5;return 8} >=     {value=6;return 8}

Solution