Question

What does it mean to contruct a NFA with 2 layers of the same DFA ?

Answer 1

• Deterministic Finite Automata can be converted into an Non Deterministic Finite Automata(NFA) that recognizes the same language as that DFA follows.
• Consider an arbitrary DFA D;then add a nondeterministic transition from any state of D to itself,thus converting DFA to NFA.
• NFA is easier to construct than DFA for regular language.
• The finite automata are called NFA where there exist many paths for specific input from the current state to the next state.
• Every NFA is not DFA,but each NFA can be translated into DFA.
• NFA also contains multiple next states and epsilon transition.
• Example of NFA
• In this we see that from state q0 for input a,there are two next states q1 and q2,similarly from q0 for input b,the next states are q0 and q1.Thus it is not fixed or determined that with a particular input where to go next.Hence this is called Non Deterministic Finite Automata.