COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Push Down Automaton
|
|
|
Turing Machine
|
|
|
Nested Stack Automaton
|
|
|
None of the mentioned
|
Detailed explanation-1: -A nested stack automaton allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols.
Detailed explanation-2: -A pushdown automaton (PDA) is a type of automaton that employs a Stack. Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite state machines but less capable than Turing machines.
Detailed explanation-3: -A push down automaton with only symbol allowed on the stack along with fixed symbol. a)Embedded PDAb)Nested Stack automatac)DPDAd)Counter AutomatonCorrect answer is option āDā.
Detailed explanation-4: -Stack: The stack is a structure in which we can push and remove the items from one end only. It has an infinite size. In PDA, the stack is used to store the items temporarily.
Detailed explanation-5: -A pushdown automaton is a finite state machine with the addition of a stack. This provides more com-putational power, because the stack allows an unlimited amount of memory. Thus pushdown automata can recognize more languages than finite state machines, for example the language L = anbn : n ā„ 0.