Classical

Theory Of Computation MCQ - Regular languages and finite automata

1:  

 Number of states of the FSM required to simulate behaviour of a computer with a memory capable of storing "m" words, each of length 'n'

A.

m x 2n

B.

2mn

C.

2m+n

D.

all of these

 
 

Option: B

Explanation :

For every data here length is ‘n’ and memory's states are defined in terms of power of 2, 
Here the total memory capability for all the words = mn
Hence number of states are 2mn

Click on Discuss to view users comments.

vikki gound said: (11:06am on Thursday 23rd May 2013)
total length m nso required memory=2^m n

Write your comments here:



2:  

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:



3:  

 If two finite states machine M and N are isomorphic, then

A. M can be transformed to N, merely re-labelling its states
B. M can be transformed to N, merely re-labelling its edges
C. Both (a) and (b)
D. None of these
 
 

Option: A

Explanation :

Click on Discuss to view users comments.

Write your comments here:



4:  

Power of

A. DFSM and NDFSM are same
B. DFSM and NDFSM are different
C. DPDM and NDPDM are diferent
D. Both (A) and (C)
 
 

Option: D

Explanation :

Click on Discuss to view users comments.

Aman said: (8:52pm on Wednesday 26th July 2017)
Because there is an algorithm to convert DFSM to NDFSM and there may or may not be possible DPDM for every NDPDM so both are different

Write your comments here:



5:  

 Which of the folowing pairs of regular expressions are equivalent ?

A.

1 (01)* and (10)* 1

B.

x (xx) * and (xx) * x

C.

x+ and x+x*+

D.

All of these

 
 

Option: D

Explanation :

Option (a) and option (b) are similar deriving expressions using rule :-  (pq)*p = p(qp)*

Option (c) will also be valid since:-

(x+x*+) will be

--->(xx*)(x*x**)

--->(xx*)(x*x*)                                (Using x** = x*)

--->(xx*)(x*)                     (Using x*x* = x*)

--->(xx*)                              (Using x*x* = x*)

--->x+

So, the answer will be all of these (Option d)

Click on Discuss to view users comments.

Naween said: (6:32am on Friday 17th May 2013)
I think this ans is wrong as all are true as we expand each and every one all seems are true
Mrugesh said: (3:02am on Thursday 29th August 2013)
As property(PQ)*P = P(QP)* option A and B are also correct... So answer should be D !!!
taraka said: (10:16pm on Thursday 12th September 2013)
from the identity rules (PQ)*P=P(QP)* So option A and B also correct so final Option is D.

Write your comments here:





Suggest an improvement

 


Syllabus covered in this section is-

  • Regular languages and finite automata
  • Context free languages and Push-down automata
  • Recursively enumerable sets and Turing machines
  • Undecidability, NPcompleteness
  • Models of computation-Finite Automata
  • Pushdown Automata
  • Non-detenninism and NFA. DPDA and PDAs and Languages accepted by these Structures
  • Grammars, Languages,
  • Non- computability and Examples of non-computable problems

This Section covers Theory of Computation Questions Answers .These questions can be used for the preparation of various competitive and academic exams like

  • UGC NET Computer Science
  • Pre PhD Entrance Exam
  • DOEACC Exams
  • Kendriya Vidyalaya Sangathan Entrance Exam
  • Undergraduate Computer Science Examinations
  • GATE Computer Science
  • Post Graduate Computer Science Test
  •  PhD Entrance Exam
  • Computer Engineering
  • National Eligibility Test (NET)
  • State Eligibility Test (SET)

Who can benefit

  • Theory of Computation Objective Questions Answers can be used by any student who is preparing for PhD entrance exam, pre PhD entrance exam, entrance exam or any other such exam.
  • Any student who is preparing for DOEACC exams can also use Theory of Computation questions answers for preparation of his exams.
  • Automata Theory mcq can be useful for the students who are pursuing any undergraduate or post graduate degree in computer science like BE, ME , Btech, Mtech, .BSc, MSc, BCA, MCA, BS, MS  or any other such degree
  • Theory of Computation mcq with answers and explanation can also be useful for the students who are preparing for any competitive exam or recruitment exams like GATE Computer Science, UGC NET Computer Science, Kendriya Vidyalaya Sangathan PGT exam, PSU, IES or any other such exam.
  • Theory of Computation multiple choice questions answers can also be used by any candidate who wants to gain credits in Theory of Computation in BS Computer science or MS Computer science.
  • Theory of Computation mcq questions answers can be used for the preparation of National Eligibility Test (NET) and State Eligibility Test (SET).
  • You can download Theory of Computation mcq pdf from this site.
  • You can get access to Theory of Computation multiple choice questions answers EBook.

Various Search Terms Used For This Section Are

  • Theory of Computation Quiz Questions With Answers

  • Theory of Computation Exam Questions Answers

  • Theory of Computation Mcq Questions Answers

  • Theory of Computation Mcq Pdf Download

  • Automata Theory Questions Answers

  • Automata Theory Quiz