Home / Engineering / Theory of Computation MCQs / Page 4

Theory of Computation MCQs | Page - 4

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.

Q. 31) Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then

(A) L1
(B) L1>=L2
(C) L1 U L2 = .*
(D) L1=L2
View Answer Discuss Share

Q. 32) Which of the following statement is wrong?

(A) Any regular language has an equivalent context-free grammar.
(B) Some non-regular languages can’t be generated by any context-free grammar
(C) Intersection of context free language and a regular language is always context-free
(D) All languages can be generated by context- free grammar
View Answer Discuss Share

Q. 33) Grammar that produce more than one Parse tree for same sentence is:

(A) Ambiguous
(B) Unambiguous
(C) Complementation
(D) Concatenation
View Answer Discuss Share

Q. 34) The language accepted by a Push down Automata:

(A) Type 0
(B) Type 1
(C) Type 2
(D) Type 3
View Answer Discuss Share

Q. 35) The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:

(A) START or READ
(B) POP or REJECT
(C) READ or POP
(D) PUSH or POP
View Answer Discuss Share

Q. 36) Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :

(A) Non regular language of L
(B) Complement of the language L
(C) None of the given
(D) All of above
View Answer Discuss Share

Q. 37) All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:

(A) String
(B) Regular language
(C) Null string
(D) None of the above
View Answer Discuss Share

Q. 38) Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

(A) (0*10*1)*
(B) 0*(10*10*)*
(C) 0*(10*1*)*0*
(D) 0*1(10*1)*10*
View Answer Discuss Share

Q. 39) Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

(A) b*ab*ab*ab
(B) (a+b)*
(C) b*a(a+b)*
(D) b*ab*ab
View Answer Discuss Share

Q. 40) Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

(A) L2-L1 is recursively enumerable
(B) L1-L3 is recursively enumerable
(C) L2 intersection L1 is recursively enumerable
(D) L2 union L1 is recursively enumerable
View Answer Discuss Share