## How to convert DFA/NFA to Higher Machine:

We can convert DFA/NFA to any higher machine,

(DFA | NFA + stack ) > DFA | NFA  [In respect to power]

DFA/NFA to Push Down Automata (PDA)

NFA | DFA + α stack = PDA

[Power of DFA | NFA with infinite stack is equal power of PDA]

DFA/NFA to Turing Machine (TM)

NFA | DFA + 2 α stack = Turing Machine (TM)

So, ( DFA | NFA + 2 α stack ) > ( DFA | NFA + 1 α stack ) > ( DFA | NFA )

Note: We can take counter in replace of stack.

But (DFA | NFA + 3 Stack) = DFA | NFA + (2 stack ) i.e. we can add 2 or more infinite stack but power remain same. (May time decreased

Note: No machine will be there which bigger power than TM is.

Q. We can convert DFA to Turing machine Automata by adding

1. One infinite stack

2. Two infinite stacks

3. Three infinite stacks

4. Two infinite counters

Which one is correct?

(a) 1   (b) 2   (c) 2, 3    (d) 2, 3, 4

Explanation:

We know that NFA | DFA + 2 α stack = Turing Machine (TM)

And also know that

(DFA | NFA + 3 Stack)  = DFA | NFA + (2 stack) i.e. we can add 2 or more infinite stack but power remain same. (May time decreased).

We can take counter in replace of stack.

So, option (d) is correct.