Classical

Theory Of Computation MCQ - Regular languages and finite automata

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*)

 
 

Option: B

Explanation :


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

 
 

Option: A

Explanation :


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 

 
 

Option: D

Explanation :


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

 
 

Option: B

Explanation :

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

 
 

Option: D

Explanation :




Suggest an improvement