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

## `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)*

(A) 3
(B) 5
(C) 8
(D) 9

(A) 7
(B) 10
(C) 12
(D) 11

## `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

## `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

## `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

## `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

## `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

## `Q. 30) Context free grammar is not closed under`

(A) Product operation
(B) Union
(C) Complementation
(D) kleene star

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