Classical

Theory Of Computation MCQ - Regular languages and finite automata

16:  

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 :
Strings of odd number of zeroes can be generated by the regular expression (00) *0.Pumping lemma can be used to prove the non-regularity of the other options.


17:  

The main difference between a DFSA and an NDFSA is

A.

in DFSA,  ε transition may be present

B.

in NDFSA, ε transitions may be present

C.

in DFSA, from any given state, there can't be any alphabet leading to two diferent states

D.

in NDFSA, from any given state, there can't be any alphabet leading to two diferent states

 
 

Option: C

Explanation :


18:  

 If w  ∈ (a, b)* satisfy abw = wab, then (w) is

A.

even

B.

odd

C.

null

D.

none of these

 
 

Option: A

Explanation :


19:  

 A PDM behaves like an FSM wnen the number of auxiliary memory it has, is

A. 0
B. 1
C. 2
D. None of these
 
 

Option: A

Explanation :


20:  

Finite state machine can recognize

A. any grammar
B. only context-free grammar
C. Both (a) and (b)
D. only regular grammar
 
 

Option: D

Explanation :




Suggest an improvement