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.

Click on Discuss to view users comments.

Aman said: (9:18pm on Wednesday 26th July 2017)
option A) it is not a regular language bcz it has infinte memory and does not contain an AP series.option B) 0^n1^n 0^nis also an palindrome but it is not regular because it need 2 unit memory for acceptance.option C) again it does not mantain AP series so it is not regular.option D is right

Write your comments here:



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 :

Click on Discuss to view users comments.

Aman said: (9:25pm on Wednesday 26th July 2017)
tranisition function in DFA is (Q*E)=Q and NFA (Q*E)=2^Q

Write your comments here:



18:  

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

A.

even

B.

odd

C.

null

D.

none of these

 
 

Option: A

Explanation :

Click on Discuss to view users comments.

Abhishek said: (12:06am on Wednesday 9th January 2013)
please explain
arti gaikawad said: (8:54pm on Wednesday 13th March 2013)
pls explain the procedure how this query get solved
vikki gound said: (11:29am on Thursday 23rd May 2013)
because W will take only even number of string

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:







Suggest an improvement