Theory of Computation MCQ - Regular Language Models

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

A
a* b*
B
(a | b)*
C
(ab)⁺
D
(a | b*)

View Explanation
Comment

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

A
without rewinding capability and unidirectional tape movement.
B
rewinding capacity, and unidirectional tape movement
C
without rewinding capability and bidirectional tape movement
D
rewinding capability and bidirectional tape movement

View Explanation
Comment

28 Palindromes can't be recognized by any FSM because

A
FSM can't remember arbitrarily large of information
B
FSM can't deterministically fix the mid-point
C
even if mid-point is known, FSM be can't be found whether, second half of the string matches the first half
D
all of these

View Explanation
Comment

29 If ∑ = {a, b, c, d, e, f } then number of strings in ∑ of length 4 such that no symbol is used more than once in a string is

A
35
B
360
C
49
D
720

View Explanation
Comment

Here string length is 4 so we can create string of length 4 by 6 values. Suppose at first place we can arrange any value by 6 methods.so 6. then Remaining total numbers are 5 so we can arrange them by 5 methods at second place. then remaining total numbers are 4 so we can arrange them by 4 methods. now remaining total numbers are 3 and we can arrange them by 3 methods. so according to permutation technique. We multiply them i.e. 6*5*4*3=360. So, 'B'

30 A language L is accepted by a finite automaton if and only if it is

A
context - free
B
context-sensitive
C
recursive
D
Right-linear

View Explanation
Comment