Multiple choice

Palindromes cannot be recognized by any FSM because

  1. FSM cannot remember arbitrary large amount of information

  2. FSM cannot deterministically fix the mid-point

  3. even if the mid-point is known, FSM cannot find whether the second half of the string matches the first half or not

  4. none of these
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Recognizing palindromes requires comparing the first half of a string with the reversed second half, which necessitates storing the entire first half. An FSM lacks the memory to store strings of arbitrary length.

Keep practicing — related questions