109) Which of the following regular expressions denotes a language comprising all possible strings over the alphabet {a, b }?

Answer is:

(a | b)*

Theory of Computation MCQ with Answers

For more MCQ's Click Here

110) An FSM (Finite State Machine) can be considered to be a TM (Turing Machine) of finite tape length

Answer is:

without rewinding capability and unidirectional tape movement.

111) Palindromes can't be recognized by any FSM because

Answer is:

all of these

Explanation:

Palindromes can't be recognized by any FSM because
* FSM can't remember arbitrarily large of information
* FSM can't deterministically fix the mid-point
* even if midpoint is known, FSM be can't be found whether, second half of the string matches the first half