Top 150+ Solved Theory of Computation MCQ Questions Answer
Q. Which one of the following statement is FALSE?
a. context-free languages are closed under union
b. context-free languages are closed under concatenation
c. context-free languages are closed under intersection
d. context-free languages are closed under Kleene closure
Q. Which of the following regular expression identity is true?
a. r(*) = r*
b. (r*s*)* = (r + s)*
c. (r + s)* = r* + s*
d. r*s* = r* + s*
Q. 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. 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. Context free grammar is not closed under
a. Product operation
b. Union
c. Complementation
d. kleene star
Q. 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
Q. 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
Q. Grammar that produce more than one Parse tree for same sentence is:
a. Ambiguous
b. Unambiguous
c. Complementation
d. Concatenation
Q. 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
Q. 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
Q. 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*
Q. 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