← Quiz: Turing Machine Traces: all 10 questions
Quiz: Turing Machine Traces · Question 5 of 10
Why can the palindrome language not be recognised by a DFA, but can by a Turing machine?
Why can the palindrome language not be recognised by a DFA, but can by a Turing machine?
- A.Palindromes are finite
- B.A DFA cannot remember the whole first half, but a TM can go back and forth and erase matched symbols
- C.A DFA cannot read the letter b
- D.A TM has more states
Answer & explanation
Correct answer: A DFA cannot remember the whole first half, but a TM can go back and forth and erase matched symbols
The TM uses its tape as unlimited memory; the DFA has only a fixed number of states.
Can you get the rest right without peeking?
Take the timed Quiz: Turing Machine Traces quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →