Home / Engineering / Theory of Computation MCQs / Page 2

# Theory of Computation MCQs | Page - 2

Dear candidates you will find MCQ questions of Theory of Computation here. Learn these questions and prepare yourself for coming examinations and interviews. You can check the right answer of any question by clicking on any option or by clicking view answer button.

(A) a*
(B) ab*
(C) (a/b)*
(D) a*b*c

## `Q. 12) Grammars that can be translated to DFAs:`

(A) Left linear grammar
(B) Right linear grammar
(C) Generic grammar
(D) All of these

## `Q. 13) Two strings x and y are indistinguishable if:`

(A) δ*(s, x) = δ* (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y
(B) if for every string z Є ∑* either both xz and yz are in language A on ∑* or both xz and yz are not in A
(C) Both above statements are true
(D) None of the above

(A) N2
(B) 2N
(C) 2N
(D) N!

## `Q. 15) Regular expressions are`

(A) Type 0 language
(B) Type 1 language
(C) Type 2 language
(D) Type 3 language

## `Q. 16) The regular expression 0*(10)* denotes the same set as`

(A) (1*0)*1*
(B) 0+(0+10)*
(C) (0+1)*10(0+1)*
(D) None of the above

## `Q. 17) Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?`

(A) L1 = {0,1}* − L
(B) L1 = {0,1}*
(C) L1 is a subset of L
(D) L1 = L

## `Q. 18) Which of the statements is true:`

(A) The complement of a regular language is always regular.
(B) Homomorphism of a regular language is always regular.
(C) Both of the above are true statements
(D) None of the above

## `Q. 19) The regular sets are closed under:`

(A) Union
(B) Concatenation
(C) Kleene closure
(D) All of the above

## `Q. 20) Any given transition graph has an equivalent:`

(A) regular
(B) DFSM (Deterministic Finite State Machine)
(C) NDFSM
(D) All of them

Download our easy to use, user friendly Android App from Play Store. And learn MCQs with one click.