On This Page

This set of Theory of Computation Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation Unit 1 Set 2

Q1 | Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqnn∈ N}). Then which of the following is ALWAYS regular?
  • P ∩ Q
  • P – Q
  • ∑* – P
  • ∑* – Q
Q2 | Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below:A BP - Qq R Sr R Ss R SThe minimum number of states required in Deterministic Finite Automation(DFA) equivalent to NFA is
  • 5
  • 4
  • 3
  • 2
Q3 | Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?
  • L must be either {an I n is odd} or {an I n is even}
  • L must be {an I n is odd}
  • L must be {an I n is even}
  • L must be {an I n = 0}
Q4 | The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .
  • CFL
  • CFG
  • GTG
  • None of the given
Q5 | Type-1 Grammar is known as_____________
  • CFG
  • CSG
  • REGULAR
  • All
Q6 | If G is “S → a S/a”, then L(G) = ?
  • a*
  • ^
  • {a}+
  • Both (a) & (c)
Q7 | “S →a S”, what is the type of this production?
  • Type 0
  • Type 1
  • Type 2
  • Type 3
Q8 | A→abA a type __________productions
  • Type 0
  • Type 1
  • Type 2
  • Type 3
Q9 | The following CFG is inS → AB**spaceB → CD**spaceB → AD**spaceB → b**spaceD → AD**spaceD → d**spaceA → a**spaceC → a
  • Chomsky normal form but not strong Chomsky normal form
  • Weak Chomsky normal form but not Chomsky normal form
  • Strong Chomsky normal form
  • Greibach normal form
Q10 | The language accepted by a Push down Automata:
  • Type0
  • Type1
  • Type2
  • Type3
Q11 | Which of the following problems is undecidable?
  • Membership problem for CFGs
  • Ambiguity problem for CFGs
  • Finiteness problem for Finite state automata FSAs
  • Equivalence problem for FSAs
Q12 | Which one of the following statement is FALSE?
  • context-free languages are closed under union
  • context-free languages are closed under concatenation
  • context-free languages are closed under intersection
  • context-free languages are closed under Kleene closure
Q13 | Which of the following strings is not generated by the following grammar? S → SaSbSε
  • aabb
  • abab
  • aababb
  • aaabb
Q14 | Which of the following regular expression identity is true?
  • r(*) = r*
  • (r*s*)* = (r + s)*
  • (r + s)* = r* + s*
  • r*s* = r* + s*
Q15 | A language L is accepted by a FSA iff it is
  • CFL
  • CSL
  • Recursive
  • Regular
Q16 | Consider the following CFGS → aB S → bA**spaceB → b A → a**spaceB → bS A → aS**spaceB → aBB A → bAA**spaceConsider the following derivation**spaceS ⇒aB**space⇒aaBB**space⇒aaBb**space⇒aabSb**space⇒aabbAb**space⇒aabbab**spaceThis derivation is
  • A leftmost derivation
  • A rightmost derivation
  • Both leftmost and rightmost derivation
  • Neither leftmost nor rightmost derivation
Q17 | Consider the following language L = {anbncndnn ≥ 1} L is
  • CFL but not regular
  • CSL but not CFL
  • Regular
  • Type 0 language but not type 1
Q18 | A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?
  • aaa
  • aba
  • abab
  • aa
Q19 | Which of the following denotes Chomskianhiearchy?
  • REG ⊂ CFL ⊂ CSL ⊂ type0
  • CFL ⊂ REG ⊂ type0 ⊂ CSL
  • CSL ⊂ type0 ⊂ REG ⊂ CFL
  • CSL ⊂ CFL ⊂ REG ⊂ type0
Q20 | The concept of FSA is much used in this part of the compiler
  • Lexical analysis
  • Parser
  • Code generation
  • Code optimization
Q21 | The following grammarG = (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
  • is type 3
  • is type 2 but not type 3
  • is type 1 but not type 2
  • is type 0 but not type 1
Q22 | The following CFG is inS → aBB**spaceB → bAA**spaceA → a**spaceB → b
  • Chomsky normal form but not strong Chomsky normal form
  • Weak Chomsky normal form but not Chomsky normal form
  • Strong Chomsky normal form
  • Greibach normal form
Q23 | Which of the following statements is wrong?
  • The regular sets are closed under intersection
  • The class of regular sets is closed under substitution
  • The class of regular sets is closed under homomorphism
  • Context Sensitive Grammar(CSG) can be recognized by Finite State Machine
Q24 | Context free grammar is not closed under
  • Product operation
  • Union
  • Complementation
  • kleene star
Q25 | Which of the following statement is wrong?
  • Any regular language can be generated by a context-free grammar
  • Some non-regular languages cannot be generated by any CFG
  • the intersection of a CFL and regular set is a CFL
  • All non-regular languages can be generated by CFGs.