COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
Push down Automata
|
|
Turing machine
|
|
NDFA
|
|
All of the mentioned
|
Detailed explanation-1: -Explanation: The composite TM accepts the language of palindromes over a, b by comparing the input string to its reverse and accepting if and only if the two are equal.
Detailed explanation-2: -A string w is called palindrome if reading w from left to right gives the same result as reading w from right to left.An even palindrome has even number of symbols.
Detailed explanation-3: -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-4: -For an even-length palindrome a TM is defined after the machine runs and erases the first and last element without encountering a mismatch. Later on the turing machine accepts the string and the string is even-length palindrome.
Detailed explanation-5: -A two-tape Turing machine has two read/write tapes, and corresponding two read/write heads, and one state. After each transition, the read/write heads will write each a symbol on their current position, then moves to right both or left both, or one left and other right, and the machine changes from qi to qj.