COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Stack is empty
|
|
|
Acceptance state
|
|
|
Both (a) and (b)
|
|
|
None of the mentioned
|
Detailed explanation-1: -Solutions for A string is accepted by a PDA whena)Stack is emptyb)Acceptance statec)Both (a) and (b)d)None of the mentionedCorrect answer is option ‘C’.
Detailed explanation-2: -The string is accepted by the PDA when we get to the acceptance state and see that the stack is empty. Usually, PDAs can accept by accepting state, accepting empty stack, or accepting both empty state and empty stack.
Detailed explanation-3: -Explanation: To accept a string, PDA needs to halt at an accepting state and with a stack empty, else it is called rejected.
Detailed explanation-4: -Which of the following can be accepted by a DPDA? Explanation: Theorem: The language pal of palindromes over the alphabet 0, 1 cannot be accepted by any finite automaton, and it is therefore not regular. Explanation:The possible change in the stack contents is a change in the number of A’s on the stack.
Detailed explanation-5: -Explanation: Push down automata is for Context free languages and they are termed as Type 2 languages according to Chomsky hierarchy.