Classical

Theory Of Computation MCQ - Regular languages and finite automata

46:  

 Consider regular expression (0 + 1) (0 + 1) ....... n times. Minimum state finite automaton that recognizes the language represented by this regular expression contains 

A.

n states

B.

 n + 1 states

C.

 n + 2 states

D.

 none of these

 
 

Option: B

Explanation :


47:  

 If regular set A is represented by A = (01 + 1)* and the regular set 'B' is represented by B = ((01)*1*)*, then 

A.

A  ⊂ B

B.

 B ⊂ A

C.

A and B are uncomparable 

D.

 A=B 

 
 

Option: D

Explanation :


48:  

 Which of the following can be recognized by a Deterministic Finite-state Automaton ? 

A.

 Numbers, 1,2,4, ....... zN ..... written in binary. 

B.

 

Numbers 1, 2, 4, ........, zN ...... written in unbinary.
C.

Set of binary string in which number of zeros is same as the number of ones. 

D.

 Set (1,101,11011,1110111, ......}

 
 

Option: A

Explanation :


49:  

 Which of the following are not regular ?

A.

String of 0’s whose length is a perfect square

B.

Set of all palindromes made up of 0’s and 1's 

C.

Strings of 0’s, whose length is a prime number 

D.

All of these

 
 

Option: D

Explanation :


50:  

 An FSM with

A.

1 stack is more powerful than an FSM with no stack

B.

2 stacks is more powerful than a FSM with 1 stack

C.

both (a) and (b)

D.

none of these

 
 

Option: C

Explanation :




Suggest an improvement