Q. A language is regular if and only if
✅ Correct Answer: (A)
Accepted by DFA
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. Which of the following is not a regular expression?
✅ Correct Answer: (B)
[(0+1)-(0b+a1)*(a+b)]*
Q. Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is
✅ Correct Answer: (D)
9
Q. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
✅ Correct Answer: (D)
11
Q. Which of the following denotes Chomskianhiearchy?
✅ Correct Answer: (A)
REG ⊂ CFL ⊂ CSL ⊂ type0
Q. The concept of FSA is much used in this part of the compiler
✅ Correct Answer: (A)
Lexical analysis
Q. 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
✅ Correct Answer: (C)
is type 1 but not type 2
Q. The following CFG is in S → aBB**spaceB → bAA**spaceA → a**spaceB → b
✅ Correct Answer: (D)
Greibach normal form
Q. Which of the following statements is wrong?
✅ Correct Answer: (D)
Context Sensitive Grammar(CSG) can be recognized by Finite State Machine
Q. Context free grammar is not closed under
✅ Correct Answer: (C)
Complementation
Jump to