Home / Engineering / Theory of Computation MCQs / Page 3

Theory of Computation MCQs | Page - 3

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. 21) A language is regular if and only if

(A) Accepted by DFA
(B) Accepted by PDA
(C) Accepted by LBA
(D) Accepted by Turing machine
View Answer Discuss Share

Q. 22) Which of the following is not a regular expression?

(A) [(a+b)*-(aa+bb)]*
(B) [(0+1)-(0b+a1)*(a+b)]*
(C) (01+11+10)*
(D) (1+2+0)*(1+2)*
View Answer Discuss Share

Q. 23) Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is

(A) 3
(B) 5
(C) 8
(D) 9
View Answer Discuss Share

Q. 24) How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?

(A) 7
(B) 10
(C) 12
(D) 11
View Answer Discuss Share

Q. 25) Which of the following denotes Chomskianhiearchy?

(A) REG ⊂ CFL ⊂ CSL ⊂ type0
(B) CFL ⊂ REG ⊂ type0 ⊂ CSL
(C) CSL ⊂ type0 ⊂ REG ⊂ CFL
(D) CSL ⊂ CFL ⊂ REG ⊂ type0
View Answer Discuss Share

Q. 26) The concept of FSA is much used in this part of the compiler

(A) Lexical analysis
(B) Parser
(C) Code generation
(D) Code optimization
View Answer Discuss Share

Q. 27) The following grammar G = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S → aAB**spaceAB → CD**spaceCD → CE**spaceC → aC**spaceC → b**spacebE → bc is

(A) is type 3
(B) is type 2 but not type 3
(C) is type 1 but not type 2
(D) is type 0 but not type 1
View Answer Discuss Share

Q. 28) The following CFG is in S → aBB**spaceB → bAA**spaceA → a**spaceB → b

(A) Chomsky normal form but not strong Chomsky normal form
(B) Weak Chomsky normal form but not Chomsky normal form
(C) Strong Chomsky normal form
(D) Greibach normal form
View Answer Discuss Share

Q. 29) Which of the following statements is wrong?

(A) The regular sets are closed under intersection
(B) The class of regular sets is closed under substitution
(C) The class of regular sets is closed under homomorphism
(D) Context Sensitive Grammar(CSG) can be recognized by Finite State Machine
View Answer Discuss Share

Q. 30) Context free grammar is not closed under

(A) Product operation
(B) Union
(C) Complementation
(D) kleene star
View Answer Discuss Share