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 :

Click on Discuss to view users comments.

thangam said: (6:31am on Wednesday 20th May 2015)
gate 1999(1.4) give that answer C.so B is right or wrong?

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

deena said: (10:13pm on Monday 1st April 2013)
Please give explanaton

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:





Suggest an improvement