MCQ IN COMPUTER SCIENCE & ENGINEERING

Detailed explanation-1: -A push down automata is like a finite state machine but with one auxiliary memory such as stack so that it can recognize the strings. Explanation: A push down automata if contains more than one stack i.e. two or more stack or auxiliary memory than it is known as Turing machine.

Detailed explanation-2: -Explanation: A pushdown automata behaves like a Turing machine when the number of auxiliary memory is 2 or more. PDA with 2 or more auxiliary memory have same expressive power.

Detailed explanation-3: -A PDA with two stacks is equivalent to a Turing machine. To show a TM is at least as powerful as a two-stack PDA, we can use the fact that a TM is exactly as powerful as a two-tape TM. In a two-tape TM, we can restrict usage of the tapes to simulate their being stacks.

Detailed explanation-4: -A pushdown automaton is computationally equivalent to a ‘restricted’ Turing Machine (TM) with two tapes which is restricted in the following manner-On the first tape, the TM can only read the input and move from left to right (it cannot make changes). On the second tape, it can only ‘push’ and ‘pop’ data.

Detailed explanation-5: -PDA is more powerful than (A) Turing machine (B) Multi tape Turing machine (C) Finite automata (D) All of these Answer : C Explanation: A PDA is more powerful than FA. Any language which can be acceptable by FA can also be acceptable by PDA. PDA also accepts a class of language which even cannot be accepted by FA.