Context-Free Languages (Theory of Computation) MCQs

Context-Free Languages (Theory of Computation) MCQs

Note: these questions assume the usual alphabets (like Σ = {a,b,c} or {0,1}) unless a question states otherwise.

1. Q1: Which of the following languages is context-free?
   A. { a^n b^n c^n | n ≥ 0 }
   B. { a^n b^m c^{n+m} | n,m ≥ 0 }
   C. { a^n b^n b^n | n ≥ 0 }
   D. { a^{p} | p is prime }
   Answer: B.
   Solution: B can be generated by grammar S → AB, A → aA c | ε, B → bB c | ε (or equivalently count n and m into c’s). A and C require equal three-way matching — not CFL. D is not CFL.
2. Q2: The class of context-free languages (CFLs) is closed under which of the following operations?
   A. Intersection with an arbitrary CFL
   B. Complement
   C. Intersection with a regular language
   D. Symmetric difference with an arbitrary CFL
   Answer: C.
   Solution: CFLs are closed under intersection with regular languages (use product construction PDA×DFA). They are not closed under general intersection or complement.
3. Q3: Which language is deterministic context-free (DCFL)? Σ={a,b}
   A. { a^n b^n | n ≥ 0 }
   B. { ww^R | w ∈ Σ* } (palindromes)
   C. { a^n b^m a^n | n,m ≥ 0 }
   D. { a^n b^n c^m | n,m ≥ 0 }
   Answer: A.
   Solution: a^n b^n is a standard DCFL recognized by a deterministic PDA. Palindromes require two-way matching non-deterministically. D is CFL but not deterministic in general when combined patterns across letters; C is non-CFL.
4. Q4: Which problem for context-free grammars is undecidable?
   A. Emptiness (L(G) = ∅ ?)
   B. Membership for a fixed string w (w ∈ L(G) ?)
   C. Equivalence of two CFGs (L(G1) = L(G2) ?)
   D. Finiteness (|L(G)| finite?)
   Answer: C.
   Solution: Emptiness, membership (CYK), and finiteness are decidable for CFGs; language equivalence for general CFGs is undecidable.
5. Q5: The pumping lemma for CFLs states that for some p, any string z with |z| ≥ p can be written z = uvwxy with constraints and:
   A. v and x together can be pumped (i.e., u v^i w x^i y ∈ L)
   B. v pumped alone must preserve membership for all i
   C. Only w can be pumped
   D. Anything can be pumped arbitrarily
   Answer: A.
   Solution: Pumping lemma for CFLs: z = u v w x y, |vwx| ≤ p, vx ≠ ε, and ∀i ≥ 0, u v^i w x^i y ∈ L.
6. Q6: Which of the following languages is NOT context-free? Σ={a,b}
   A. { a^i b^j a^k | i + k = j }
   B. { a^n b^n c^m | n,m ≥ 0 } (alphabet extended)
   C. { a^n b^n | n ≥ 0 }
   D. { w#w^R | w ∈ {a,b}* } (separator #)
   Answer: A.
   Solution: A enforces a relation across two separated regions summing to j — can be shown non-CFL via pumping/Ogden. B, C, D are CFLs (D via PDA using # as separator to detect midpoint).
7. Q7: Which statement is true about ambiguity of CFGs?
   A. Ambiguity is decidable.
   B. Every CFL has an unambiguous grammar.
   C. Some CFLs are inherently ambiguous (no unambiguous grammar exists).
   D. Determining if a grammar is ambiguous is in P.
   Answer: C.
   Solution: There exist inherently ambiguous CFLs (e.g., certain unions of languages). Ambiguity is undecidable.
8. Q8: Intersection of two CFLs is:
   A. Always a CFL
   B. Always regular
   C. Not necessarily a CFL
   D. Always context-sensitive
   Answer: C.
   Solution: CFLs are not closed under intersection; counterexample: L1={ a^n b^n c^m } and L2={ a^m b^n c^n } intersect to { a^n b^n c^n } which is not CFL.
9. Q9: Which grammar normal form requires productions of the form A → BC or A → a (plus possibly S → ε)?
   A. Greibach Normal Form
   B. Chomsky Normal Form (CNF)
   C. Backus-Naur Form
   D. Kuroda Normal Form
   Answer: B.
   Solution: CNF: productions are A → BC or A → a; S → ε allowed when ε ∈ L.
10. Q10: The membership problem (given CFG G and w, decide w ∈ L(G)) is solvable in what worst-case time using CYK (for CNF)?
    A. O(n)
    B. O(n^2)
    C. O(n^3)
    D. Undecidable
    Answer: C.
    Solution: CYK algorithm runs in O(n^3 · |G|) for grammar in CNF.
11. Q11: Which of the following is true about deterministic CFLs (DCFLs)?
    A. DCFLs are closed under union.
    B. DCFLs are closed under complement.
    C. DCFLs are closed under intersection with arbitrary CFLs.
    D. DCFLs are closed under reversal.
    Answer: B.
    Solution: DCFLs are closed under complement (by determinization and state swap for DPDA acceptance by final states); they are not closed under union in general. (Reversal of a DCFL need not be DCFL.)
12. Q12: If a language L is context-free and R is regular, then L ∩ R is:
    A. Context-free
    B. Regular only if L finite
    C. Always deterministic context-free
    D. Not necessarily context-free
    Answer: A.
    Solution: Intersection with a regular language preserves the CFL property; construct PDA that simulates DFA on input and PDA on stack.
13. Q13: Which of the following languages is context-free? Σ={0,1}
    A. { 0^n 1^m 0^n | n,m ≥ 0 }
    B. { 0^n 1^n 2^n | n ≥ 0 } (with 2 introduced)
    C. { w ∈ {0,1}* | number of 0’s = number of 1’s }
    D. { a^i b^j c^k | i = j or j = k }
    Answer: D.
    Solution: D is union of two CFLs {a^n b^n c^k} ∪ {a^i b^j c^j} which is CFL (CFLs closed under union). A is non-CFL (requires matching first and last counts with middle arbitrary), B is not CFL, C is non-CFL (requires global equality across two symbols in arbitrary positions; actually {0^n1^n} is CFL but strings with 0s and 1s mixed isn’t CFL unless pattern constrained).
14. Q14: Which of these languages is inherently ambiguous? (classic example)
    A. L = { a^i b^j c^k | i = j or j = k }
    B. L = { a^n b^n | n ≥ 0 }
    C. L = { (ab)^n | n ≥ 0 }
    D. L = { a^m b^n c^p | m+n = p }
    Answer: A.
    Solution: The language {a^i b^j c^k | i = j or j = k} is a well-known inherently ambiguous CFL.
15. Q15: Which of the following is decidable for CFGs?
    A. Whether L(G) is regular
    B. Whether G is ambiguous
    C. Whether L(G) = Σ*
    D. Whether two CFGs are equivalent
    Answer: A.
    Solution: Regularity of a CFG is decidable (via procedures checking equivalence to some regular grammar or using Parikh images and automata). Ambiguity and equivalence are undecidable; universality (L=Σ*) is undecidable in general.
16. Q16: Ogden’s lemma strengthens pumping lemma for CFLs by allowing:
    A. Marking of distinguished positions that must be pumped
    B. Pumping of a single central symbol only
    C. Pumping lemma for regular languages
    D. None of above
    Answer: A.
    Solution: Ogden’s lemma lets you mark k positions; guarantees decomposition where v and x include at least one marked position — stronger tool for non-CFL proofs.
17. Q17: Which conversion is always possible for any CFG G (except trivial ε handling)?
    A. Convert G to an equivalent PDA
    B. Convert G into regular expression
    C. Convert G into DFA without blow-up
    D. Convert G to finite automaton if L(G) infinite
    Answer: A.
    Solution: Every CFG has an equivalent pushdown automaton (PDA). Converting to regular expression or DFA is not always possible.
18. Q18: Which of the following languages is context-free? Σ={a,b,c}
    A. { a^i b^j c^k | i = j and j = k }
    B. { a^i b^j c^k | i = j or j = k }
    C. { a^n b^n c^n d^n | n≥0 }
    D. { a^{2^n} | n ≥ 0 }
    Answer: B.
    Solution: B is union of two CFLs (A1: i=j any k; A2: j=k any i) → CFL. A is {a^n b^n c^n} not CFL. C and D not CFL.
19. Q19: A grammar in Greibach Normal Form (GNF) has productions of the form:
    A. A → a α where α ∈ V* (possibly empty)
    B. A → BC | a
    C. A → ε only
    D. A → α where α is terminal-only
    Answer: A.
    Solution: GNF: productions start with a terminal followed by (possibly empty) string of nonterminals: A → a N*.
20. Q20: Which language is context-free but not deterministic context-free?
    A. L = { a^n b^n c^m | n,m ≥ 0 }
    B. L = { a^n b^n c^n | n ≥ 0 }
    C. L = { ww^R | w ∈ {a,b}* }
    D. L = { a^n b^m | n,m ≥ 0 }
    Answer: C.
    Solution: Palindrome language ww^R is CFL (ambiguously via nondet PDA) but not deterministic CFL in general.
21. Q21: The emptiness problem for CFGs (is L(G)=∅?) is:
    A. Decidable in linear time to grammar size
    B. Undecidable
    C. PSPACE-complete
    D. Equivalent to CFG equivalence
    Answer: A.
    Solution: Emptiness decidable by marking productive nonterminals (reachable from start producing terminals); linear-time algorithms exist.
22. Q22: Which of these operations may lead a CFL to become non-CFL?
    A. Kleene star of a CFL
    B. Concatenation of two CFLs
    C. Intersection of two CFLs
    D. Union of two CFLs
    Answer: C.
    Solution: Intersection of two CFLs need not be CFL. Kleene star, concatenation, and union of CFLs are CFL-closed.
23. Q23: Which of these is true about the universal language problem for CFGs (L(G) = Σ)? A. Decidable B. Undecidable C. Equivalent to membership problem D. Always false for infinite alphabets Answer: B. Solution: Universality (L(G)=Σ) for CFGs is undecidable.
24. Q24: Which type of PDA accepts by empty stack rather than final state?
    A. Deterministic PDA only
    B. Nondeterministic PDA only
    C. Both deterministic and nondeterministic PDAs can be designed to accept by empty stack
    D. Neither — acceptance by empty stack impossible
    Answer: C.
    Solution: Acceptance by empty stack is an equivalent acceptance mode for PDAs (NPDAs); deterministic PDAs can also be made to accept by empty stack with adaptations.
25. Q25: Which of these languages is context-free? Σ={a,b}
    A. { a^n b^{2n} | n ≥ 0 }
    B. { a^{n^2} | n ≥ 0 }
    C. { a^p b^p c^p | p prime }
    D. { a^n b^n a^n | n ≥ 0 }
    Answer: A.
    Solution: A generated by grammar S→a S b b | ε. B, C, D are not CFL.
26. Q26: Which of the following is a correct property?
    A. Every regular language is context-free.
    B. Every context-free language is regular.
    C. CFLs ⊆ Regular languages.
    D. Regular and CFL classes are incomparable.
    Answer: A.
    Solution: Regular languages are a strict subset of CFLs (every regular language has a CFG).
27. Q27: Determining whether a given CFG generates infinitely many strings is:
    A. Undecidable
    B. Decidable (and can be tested by detecting a cycle reachable from start that can produce terminals)
    C. Equivalent to equivalence problem
    D. Co-NP-complete
    Answer: B.
    Solution: Finiteness is decidable: check for productive nonterminal cycles reachable from start.
28. Q28: Which of these is NOT true about CFLs?
    A. CFLs are closed under homomorphism.
    B. CFLs are closed under inverse homomorphism.
    C. CFLs are closed under complement.
    D. CFLs are closed under substitution by regular languages.
    Answer: C.
    Solution: CFLs are not closed under complement. They are closed under homomorphism and inverse homomorphism.
29. Q29: Which language is context-free? Σ={a,b}
    A. { a^n b^n a^m b^m | n,m ≥ 0 }
    B. { a^n b^m c^n | n,m≥0 } (introducing c)
    C. { a^n b^n c^n d^n | n≥0 }
    D. { a^{2^n} | n≥0 }
    Answer: A.
    Solution: A is concatenation of two a^n b^n patterns: (a^n b^n)(a^m b^m) — CFL. B reorders counts across separated symbols may not be CFL depending on alphabet; C and D not CFL.
30. Q30: The problem “Given CFG G and regular language R, is L(G) ⊆ R?” is:
    A. Decidable (reduce to emptiness of L(G) ∩ complement(R))
    B. Undecidable
    C. Equivalent to the halting problem
    D. PSPACE-hard and undecidable
    Answer: A.
    Solution: L(G) ⊆ R iff L(G) ∩ (Σ* \ R) = ∅; complement(R) is regular, intersection CFL∩regular is CFL; emptiness decidable.
31. Q31: Which of the following CFG transformations preserves language except possibly for ε?
    A. Conversion to Chomsky Normal Form (CNF)
    B. Conversion to a regular grammar
    C. Conversion to a right-linear grammar always
    D. Conversion to DFA
    Answer: A.
    Solution: CNF conversion preserves L \ {ε} (and can handle ε specially). Other conversions not always possible.
32. Q32: Which language is context-free? Σ={a,b}
    A. { a^n b^{n!} | n≥1 }
    B. { a^n b^m | n divides m }
    C. { a^i b^j c^k | i = j or i = k } (with c introduced)
    D. { a^n b^n c^n | n≥0 }
    Answer: C.
    Solution: C is union of two CFLs. A and B impose arithmetic divisibility/unbounded nonlinear relations — not CFL. D not CFL.
33. Q33: Which statement about pushdown automata (PDA) is correct?
    A. Every PDA can be determinized into an equivalent DPDA.
    B. Acceptance by final state and by empty stack recognize exactly the same class of languages for NPDAs.
    C. DPDA languages = CFLs.
    D. PDAs have the same expressive power as finite automata.
    Answer: B.
    Solution: For NPDAs, acceptance by empty stack and by final state define the same class (CFLs). Determinization is not always possible; DPDAs are a strict subset of CFLs.
34. Q34: Which CFL is ambiguous?
    A. { a^n b^n | n ≥ 0 } with grammar S→aSb|SS|ε
    B. { a^n b^n | n ≥ 0 } with grammar S→aSb|ε
    C. { (ab)^n | n≥0 } with grammar S→abS|ε
    D. { a^* } with grammar S→aS|ε
    Answer: A.
    Solution: Grammar with S→SS introduces ambiguity for strings that can be split; language itself is unambiguous but that grammar is ambiguous.
35. Q35: Which of the following properties is undecidable for CFGs?
    A. Whether a given terminal a appears in any sentential form of G (occurrence problem)
    B. Whether L(G) contains infinitely many strings
    C. Whether a given CFG generates ε
    D. Whether the language is empty
    Answer: A.
    Solution: Occurrence of a specific terminal in derivations (the “membership of symbol in derivations”) is undecidable in general; B,C,D are decidable.
36. Q36: Which of the following shows that a language is not context-free?
    A. Pumping lemma for regular languages
    B. Pumping lemma for CFLs or Ogden’s lemma
    C. Myhill–Nerode theorem
    D. Union closure property
    Answer: B.
    Solution: Use CFL pumping lemma or Ogden’s lemma to prove non-context-freeness.
37. Q37: Which of these languages is context-free? Σ={a,b}
    A. L = { a^n b^m a^{n+m} | n,m ≥ 0 }
    B. L = { a^n b^n a^n | n ≥ 0 }
    C. L = { a^{n+m} b^n c^m | n,m ≥ 0 } (with c introduced)
    D. L = { a^{p} | p is prime }
    Answer: C.
    Solution: C can be generated with two counters pushed/popped in sequence: generate a^{n+m} on stack in two phases then match b^n and c^m appropriately. A and B are non-CFL; D non-CFL.
38. Q38: The intersection of a CFL and a DCFL is:
    A. Always DCFL
    B. Always CFL
    C. Not necessarily CFL
    D. Always regular
    Answer: B.
    Solution: CFLs are closed under intersection with regular, and more generally intersection with DCFL yields CFL (since DCFL ⊆ CFL and intersection of CFL with DCFL is CFL via PDA×DPDA simulation resulting in PDA).
39. Q39: Which of the following languages is context-free? Σ={0,1}
    A. { w | number of 0’s equals number of 1’s } (in arbitrary order)
    B. { 0^n 1^m 0^n | n,m≥0 }
    C. { 0^i 1^j 0^k | i + k = j }
    D. { 0^n 1^n 0^n | n≥0 }
    Answer: B.
    Solution: B is of form a^n b^m a^n — mirror around middle and can be generated by grammar S→0 S 0 | T, T→1 T | ε. A and C and D are non-CFLs.
40. Q40: Which statement is true about the complement of a CFL?
    A. Complement of any CFL is a CFL.
    B. Complement of a DCFL is a DCFL.
    C. Complement of a CFL is always regular.
    D. Complement of CFL is context-sensitive.
    Answer: B.
    Solution: DCFLs are closed under complement; general CFLs are not closed under complement. Complement might be context-sensitive but that is not always the standard guarantee; B is the best precise fact.
41. Q41: The language L = { a^i b^j c^k | i = j or j = k } is:
    A. Regular
    B. Context-free but inherently ambiguous
    C. Context-free and unambiguous
    D. Not context-free
    Answer: B.
    Solution: L is a classic inherently ambiguous CFL (union of {a^n b^n c^k} and {a^i b^j c^j}).
42. Q42: Which technique can show a language is not context-free even when pumping lemma fails?
    A. Myhill–Nerode
    B. Ogden’s lemma
    C. Regular expression simplification
    D. Arden’s lemma
    Answer: B.
    Solution: Ogden’s lemma is stronger than the pumping lemma and can succeed where pumping lemma fails.
43. Q43: The Parikh mapping of a CFL yields:
    A. A set that is always semilinear
    B. Always finite
    C. Not computable
    D. Always periodic with period 1
    Answer: A.
    Solution: Parikh’s theorem: Parikh image of any CFL is a semilinear set (finite union of linear sets).
44. Q44: Which grammar form guarantees that every production begins with a terminal?
    A. Chomsky Normal Form
    B. Greibach Normal Form
    C. Chomsky–Schützenberger Form
    D. Extended BNF
    Answer: B.
    Solution: GNF productions are of the form A → a α, starting with terminal a.
45. Q45: Which of these languages is not context-free? Σ={a,b,c}
    A. { a^n b^n c^m | n,m ≥ 0 }
    B. { a^m b^n c^n | m,n ≥ 0 }
    C. { a^n b^n c^n | n ≥ 0 }
    D. { a^i b^j c^k | i = j or i = k }
    Answer: C.
    Solution: a^n b^n c^n is classic non-CFL.
46. Q46: Which of the following is true: the set of context-free languages is closed under substitution where each terminal is replaced by a:
    A. Regular language — yes, closure holds.
    B. CFL — closure holds.
    C. Arbitrary language — closure holds.
    D. Deterministic CFL — closure fails.
    Answer: A.
    Solution: CFLs are closed under substitution of terminals by regular languages.
47. Q47: Which problem is decidable for context-free languages?
    A. Ambiguity of a grammar
    B. Emptiness of intersection of two CFLs
    C. Membership (whether a string belongs)
    D. Equivalence of two CFGs
    Answer: C.
    Solution: Membership for CFGs is decidable (CYK). Ambiguity and equivalence undecidable; emptiness of intersection of two CFLs is undecidable.
48. Q48: A CFG for language { a^n b^{2n} | n ≥ 0 } can be:
    A. S → a S b b | ε
    B. S → a S b | ε
    C. S → a a S b b | ε
    D. No CFG exists
    Answer: A.
    Solution: Rule S→a S b b | ε generates one a and two b’s per recursion → a^n b^{2n}.
49. Q49: Which statement about LR(k) grammars is true?
    A. Every CFG is LR(1) for some k.
    B. LR(k) grammars are a subset of deterministic context-free grammars.
    C. LR grammars are inherently ambiguous.
    D. LR(k) cannot parse arithmetic expressions deterministically.
    Answer: B.
    Solution: LR(k) grammars define deterministic languages and are a strict subset of DCFLs; many arithmetic expression grammars are LR(1).
50. Q50: Which of the following context-free language properties is decidable?
    A. Whether L(G) is regular
    B. Whether G is ambiguous
    C. Whether L(G1) = L(G2)
    D. Whether G generates all palindromes over Σ
    Answer: A.
    Solution: Regularity is decidable; ambiguity, equivalence, and universality for palindromes are undecidable.
51. Q51: The set of palindromes over Σ = {a,b} is:
    A. Regular
    B. Context-free but not deterministic context-free
    C. Context-free and deterministic
    D. Not context-free
    Answer: D.
    Solution: The set of all palindromes without a middle marker is not context-free (requires matching both ends without a center marker). With a center marker (like w#w^R) it is CFL.
52. Q52: Which of the following is an example of a deterministic CFL?
    A. { a^n b^n c^m | n,m ≥ 0 }
    B. { {a,b}* } (all strings)
    C. { ww^R | w ∈ {a,b}* }
    D. { a^n b^n c^n | n≥0 }
    Answer: A.
    Solution: A can be recognized deterministically by pushing a’s and matching with b’s, independent c’s consumed afterwards — DPDA exists. B is regular hence DCFL. C and D are non-DCFL.
53. Q53: Which of the following operations preserves context-freeness?
    A. Intersection of two CFLs
    B. Complement of a CFL
    C. Left quotient by regular language
    D. Symmetric difference of two CFLs
    Answer: C.
    Solution: CFLs are closed under left quotient by regular languages (and right quotient). Intersection and complement not generally closed; symmetric difference not guaranteed.
54. Q54: Which of the following languages is context-free? Σ={a,b}
    A. { a^n b^m a^n | n,m ≥ 0 }
    B. { a^n b^n c^n d^m | n,m≥0 } (extra d allowed)
    C. { a^{n^2} | n ≥ 0 }
    D. { a^p b^q | p prime, q prime }
    Answer: A.
    Solution: A can be generated by grammar that pushes for first and last a’s and ignores middle b’s. B contains a^n b^n c^n which is not CFL. C, D not CFL.
55. Q55: Which technique is best to show emptiness of L(G) ∩ R where G is CFG and R is regular?
    A. Convert R to DFA, intersect via PDA×DFA construction, and test CFL emptiness.
    B. Use pumping lemma.
    C. Use Myhill–Nerode theorem.
    D. Convert G to DFA directly.
    Answer: A.
    Solution: Intersection with regular yields CFL whose emptiness can be tested by marking reachable productive nonterminals.
56. Q56: The language L = { a^n b^m c^n d^m | n,m ≥ 0 } is:
    A. Context-free
    B. Intersection of two CFLs but not CFL
    C. Not context-free
    D. Regular
    Answer: B.
    Solution: L = { a^n b^m c^n d^m } = { a^n c^n b^m d^m } rearranged; it’s intersection of { a^n b^m c^n d^m } = L1 ∩ L2 where L1 checks a^n c^n and L2 checks b^m d^m — intersection of CFLs can be non-CFL; L itself is not CFL but is intersection of two CFLs.
57. Q57: Which of the following problems is decidable for PDAs?
    A. Emptiness of language recognized by PDA
    B. Equivalence of two PDAs
    C. Ambiguity of PDA
    D. Minimization of PDA states
    Answer: A.
    Solution: Emptiness for PDAs (CFL emptiness) is decidable. Equivalence and ambiguity are undecidable.
58. Q58: Which set is context-free? Σ={a,b,c}
    A. { a^i b^j c^k | i = j and j ≠ k }
    B. { a^i b^j c^k | i = j or j = k }
    C. { a^n b^n c^n d^n | n≥0 }
    D. { a^{f(n)} | f(n) = n! }
    Answer: B.
    Solution: B is union of two CFLs. A is CFL? i=j and j≠k is difference of two CFLs; but union of CFL with complement issue — B is standard answer.
59. Q59: Which of the following is NOT a closure property of CFLs?
    A. Union
    B. Concatenation
    C. Complement
    D. Kleene star
    Answer: C.
    Solution: CFLs are closed under union, concatenation, and star; not closed under complement.
60. Q60: Which of the following languages is deterministic context-free? Σ={a,b}
    A. { a^n b^n a^n | n≥0 }
    B. { a^n b^m | n,m ≥ 0 }
    C. { w ∈ {a,b}* | #a(w) = #b(w) }
    D. { a^n b^n c^n | n≥0 }
    Answer: B.
    Solution: B is regular hence DCFL. A, C, D not DCFL in general.
61. Q61: Which statement about the membership of nonterminals producing ε is true during CNF conversion?
    A. Nullable nonterminals must be computed and used to add alternative productions.
    B. Nullable nonterminals are irrelevant in CNF conversion.
    C. CNF does not allow ε in any case.
    D. CNF requires introducing terminals into nullable nonterminals only.
    Answer: A.
    Solution: To convert to CNF, nullable nonterminals are found and productions adjusted to preserve derivations (except possibly for ε handled separately).
62. Q62: Which of the following languages is context-free? Σ={a,b,c}
    A. { a^n b^n c^m d^m | n,m≥0 } (two separate matches)
    B. { a^n b^m c^k | n = m·k }
    C. { a^n b^m c^{n+m} | n,m≥0 }
    D. { a^{2^n} | n≥0 }
    Answer: C.
    Solution: C can be generated by producing paired a and c and b and c appropriately (S→AC where A→aA c | ε, C→bC c | ε). A is intersection of two CFLs; B, D not CFL.
63. Q63: For which grammar type is emptiness of intersection of two grammars decidable?
    A. Both regular grammars
    B. Both context-free grammars
    C. One regular and one CFL
    D. One context-free and one recursively enumerable
    Answer: A and C (choose the best single): A.
    Solution: Intersection emptiness is decidable for regular grammars (DFA intersection) and for CFL∩regular (reduce to CFL emptiness). For two arbitrary CFLs it’s undecidable; best single answer A (but note C also decidable — question ambiguous). (Preferred accepted fact: CFL∩regular emptiness decidable.)
64. Q64: Which of the following languages is context-free? Σ={a,b}
    A. { a^n b^{n^2} | n≥0 }
    B. { a^{n} b^{m} c^{n+m} | n,m≥0 } (with c)
    C. { ww | w∈{a,b}* }
    D. { a^p | p prime }
    Answer: B.
    Solution: B can be generated by grammar that produces n a’s and n c’s and independently m b’s and m c’s: S→AC, A→a A c | ε, C→b C c | ε. A, C, D not CFL.
65. Q65: Which is true regarding CFL recognition complexity? For grammar size |G| and input length n, membership via CYK is:
    A. Polynomial-time (O(n^3))
    B. NP-complete
    C. Undecidable
    D. Exponential-time required
    Answer: A.
    Solution: CYK gives polynomial-time membership (O(n^3 · |G|) for CNF).
66. Q66: The language L = { a^i b^j c^k | i = j and j ≠ k } is:
    A. Context-free and unambiguous
    B. Context-free and inherently ambiguous
    C. Not context-free
    D. Regular
    Answer: B.
    Solution: Similar to earlier inherently ambiguous unions; i=j and j≠k is CFL but inherently ambiguous in some constructions (classic examples revolve around such unions). Accept B.
67. Q67: Which set of languages is closed under complement?
    A. Regular languages
    B. Context-free languages
    C. Deterministic context-free languages
    D. A and C
    Answer: D.
    Solution: Regular and DCFL classes are closed under complement; general CFLs are not.
68. Q68: Which of the following operations on CFGs is guaranteed to terminate and preserve equivalence (up to ε)?
    A. Elimination of useless symbols
    B. Deciding ambiguity
    C. Converting to equivalent regular grammar if one exists
    D. Finding minimal CFG (fewest nonterminals)
    Answer: A.
    Solution: Useless symbol elimination (unreachable and unproductive) is decidable and preserves L(G). Ambiguity, minimal grammar problems are undecidable or hard.
69. Q69: Which of the following languages is context-free? Σ={a,b,c}
    A. { a^n b^m c^{n m} | n,m≥0 }
    B. { a^n b^n c^m d^m | n,m≥0 }
    C. { a^{n} b^{n^2} | n≥0 }
    D. { a^n b^n c^{n^2} | n≥0 }
    Answer: B.
    Solution: B is concatenation/product of two independent a^n b^n and c^m d^m; i.e., (a^n b^n)(c^m d^m) → CFL. A, C, D impose multiplicative/exponential relations not CFL.
70. Q70: Which of the following languages is a deterministic CFL?
    A. { a^n b^m a^n | n,m≥0 }
    B. { a^n b^n c^m | n,m≥0 }
    C. { ww^R | w∈{a,b}* }
    D. { a^i b^j c^k | i = j or j = k }
    Answer: B.
    Solution: B can be parsed deterministically by pushing a’s and matching b’s then reading c’s. A, C, D are non-DCFL or ambiguous.
71. Q71: Which of the following languages is context-free? Σ={a,b}
    A. L = { a^{n} b^{2n} a^{n} | n≥0 }
    B. L = { a^n b^m a^n b^m | n,m≥0 }
    C. L = { a^n b^n c^m | n,m≥0 } (with c)
    D. L = { a^{2^n} | n≥0 }
    Answer: C.
    Solution: C is CFL (stack for a^n b^n, then independent c^m). A and B require matching separated parts in ways that are non-CFL; D non-CFL.
72. Q72: Which is true about complements of DCFLs?
    A. Complement of DCFL is not necessarily DCFL.
    B. Complement of DCFL is always DCFL.
    C. Complement of DCFL is always regular.
    D. Complement closure of DCFLs is unknown.
    Answer: B.
    Solution: DCFLs are closed under complement.
73. Q73: Which of the following languages is context-free? Σ={a,b,c}
    A. { a^n b^n c^m d^m e^k | n,m,k≥0 }
    B. { a^n b^m c^n d^m | n,m≥0 }
    C. { a^n b^n c^n d^n | n≥0 }
    D. { a^{n!} | n≥1 }
    Answer: A.
    Solution: A is concatenation of three CFLs a^n b^n, c^m d^m, e^k (regular) → CFL. B imposes cross matches that make it non-CFL. C and D not CFL.
74. Q74: Which technique can give a grammar that is guaranteed to be unambiguous for a given deterministic language?
    A. LR(1)/LR(k) construction from a deterministic grammar
    B. Standard left-recursive ambiguous grammar
    C. Random grammar generation
    D. Pumping lemma application
    Answer: A.
    Solution: Deterministic languages have LR(k) grammars; parser-generator techniques give unambiguous grammars for deterministic languages.
75. Q75: Which of the following is true about the intersection of CFL and CFL complement? (i.e., L ∩ ¬L’)
    A. Always CFL
    B. Decidable emptiness in general
    C. Not necessarily CFL and emptiness undecidable
    D. Always regular
    Answer: C.
    Solution: CFL closedness under complement fails; emptiness of L ∩ ¬L’ is generally undecidable.
76. Q76: Which of the following is context-free? Σ={0,1}
    A. { 0^n 1^{n^2} | n≥0 }
    B. { 0^n 1^n 0^m 1^m | n,m≥0 }
    C. { w ∈ {0,1}* | #0(w) = #1(w) } (unordered)
    D. { 0^n 1^m 0^n | n,m≥0 }
    Answer: B.
    Solution: B is concatenation of two a^n b^n patterns → CFL. C non-CFL, A and D non-CFL.
77. Q77: The set of contexts-free languages is:
    A. Closed under intersection with regular languages and substitution by CFLs.
    B. Closed under complement and intersection with arbitrary CFLs.
    C. Closed under complement but not union.
    D. Closed under symmetric difference only.
    Answer: A.
    Solution: CFLs closed under substitution by regular languages, under substitution by CFLs if certain conditions; main safe fact: closed under intersection with regular languages; substitution by regular languages yes.
78. Q78: Which of these statements is false?
    A. Every deterministic context-free language is unambiguous.
    B. Every unambiguous CFL is deterministic.
    C. Some unambiguous CFLs are not deterministic.
    D. Ambiguity is undecidable for CFGs.
    Answer: B.
    Solution: There exist unambiguous CFLs that are not deterministic; so B false. A true; C true; D true.
79. Q79: Which of the following languages is context-free? Σ={a,b,c}
    A. { a^p b^q c^r | p = q·r }
    B. { a^n b^n c^m | n,m≥0 }
    C. { a^{n^2} b^n | n≥0 }
    D. { a^{F_n} | F_n Fibonacci }
    Answer: B.
    Solution: B is CFL. A, C, D are not CFL.
80. Q80: Which of the following is decidable for CFGs?
    A. Whether L(G) contains infinitely many palindromes
    B. Whether G is LR(1)
    C. Whether L(G) is deterministic context-free
    D. Whether G generates some nonterminal twice in a derivation of length ≤ k
    Answer: D.
    Solution: D is a bounded property checkable by exploring derivations up to length k. A, B, C are generally undecidable or nontrivial.
81. Q81: Which language is context-free? Σ={a,b}
    A. { a^n b^{n} a^{n} | n≥0 }
    B. { a^n b^{m} a^{m} b^{n} | n,m≥0 }
    C. { a^i b^j | i ≠ j }
    D. { a^n b^n }
    Answer: D.
    Solution: D is canonical CFL. A and B require cross-matching beyond CFL; C is regular? Actually C = Σ* \ { a^n b^n } restricted to that form — but not necessarily CFL. Choose D.
82. Q82: Which of the following languages is context-free but inherently ambiguous?
    A. { a^n b^n c^m d^m | n,m≥0 }
    B. { a^n b^m c^m d^n | n,m≥0 }
    C. { a^i b^j c^k | i=j or j=k }
    D. { a^n b^n }
    Answer: C.
    Solution: C is classic inherently ambiguous CFL (union of two balanced patterns).
83. Q83: Which of these is true about converting a PDA to a CFG?
    A. Always possible for NPDAs to produce an equivalent CFG.
    B. Only possible for deterministic PDAs.
    C. PDAs and CFGs are incomparable.
    D. Conversion yields regular grammar.
    Answer: A.
    Solution: For every NPDA there exists an equivalent CFG, and vice versa.
84. Q84: Which of the following languages is context-free? Σ={a,b,c}
    A. { a^n b^m c^{n·m} | n,m≥0 }
    B. { a^n b^n c^m d^m | n,m≥0 }
    C. { a^{n^2} b^n | n≥0 }
    D. { a^n b^n c^n d^n | n≥0 }
    Answer: B.
    Solution: B is concatenation of two independent balanced parts → CFL. A,C,D not CFL.
85. Q85: Which operation, when applied to a CFL, may produce a non-CFL?
    A. Kleene star
    B. Homomorphism
    C. Complement
    D. Concatenation with regular language
    Answer: C.
    Solution: Complement can take CFL outside CFL class.
86. Q86: Which of the following languages is deterministic context-free? Σ={a,b}
    A. { a^n b^n a^m | n,m≥0 }
    B. { a^n b^n }
    C. { w#w^R | w∈{a,b}* }
    D. { a^n b^m c^m d^n | n,m≥0 } (with c,d)
    Answer: B.
    Solution: a^n b^n is DCFL. A is more complex; C non-DCFL; D can be DCFL? D is of form a^n … d^n with middle balanced m — might be DCFL if structured, but B is straightforward.
87. Q87: Which of the following is a correct use of Ogden’s lemma?
    A. Marking positions to ensure pumped substrings include marked positions.
    B. Pumping any substring arbitrarily without restrictions.
    C. Proving regularity.
    D. Showing membership of a string in language.
    Answer: A.
    Solution: Ogden’s lemma allows marking distinguished positions to force pumping to include them, strengthening non-CFL proofs.
88. Q88: The language L = { a^n b^n c^{n^2} | n≥0 } is:
    A. Context-free
    B. Not context-free (non-CFL)
    C. Regular
    D. Deterministic context-free
    Answer: B.
    Solution: Exponential/quadratic relations between counts exceed stack power; non-CFL (use pumping/Ogden).
89. Q89: Which of the following is true?
    A. There exists a CFL that is not the homomorphic image of any regular language.
    B. Every CFL is a homomorphic image of some regular language.
    C. Every regular language is homomorphic image of some CFL only.
    D. Homomorphisms preserve non-context-freeness always.
    Answer: B.
    Solution: Every CFL is the homomorphic image of a Dyck language intersected with a regular set — standard result: CFL = homomorphic image of RL ∩ Dyck etc.
90. Q90: Which of the following is context-free? Σ={a,b}
    A. { a^n b^m | n = m^2 }
    B. { a^n b^m a^{n+m} | n,m≥0 }
    C. { a^n b^n c^m d^m | n,m≥0 } (introducing c,d)
    D. { w ∈ {a,b}* | w contains equal number of a’s and b’s }
    Answer: C.
    Solution: C is concatenation of a^n b^n and c^m d^m → CFL. A,D not CFL; B non-CFL.
91. Q91: Which of the following is a decidable property for CFGs?
    A. Whether the language is deterministic context-free
    B. Whether grammar is ambiguous
    C. Whether grammar generates infinitely many strings
    D. Whether two CFGs generate the same non-empty finite set
    Answer: C.
    Solution: Finiteness/infiniteness decidable; ambiguity and DCFL membership undecidable.
92. Q92: The set { a^n b^n c^m | n,m≥0 } ∪ { a^n b^m c^m | n,m≥0 } is:
    A. Context-free
    B. Non-context-free
    C. Regular
    D. Deterministic context-free only
    Answer: A.
    Solution: Union of two CFLs is CFL.
93. Q93: Which of the following languages is context-free? Σ={a,b,c}
    A. { a^n b^m c^{n+m} | n,m≥0 }
    B. { a^{n} b^{m} c^{n·m} | n,m≥0 }
    C. { a^{F_n} | F_n Fibonacci }
    D. { (ab)^n (ba)^n | n≥0 }
    Answer: A.
    Solution: A generated earlier S→AB with A→a A c | ε and B→b B c | ε. B,C non-CFL. D is { (ab)^n (ba)^n } = { ab ab … ba ba … } — equals (ab)^n (ba)^n; this is equivalent to (ab)^n (ba)^n which is CFL? It’s {ab}^n {ba}^n = (ab)^n(ba)^n is CFL as concatenation of two regular languages? Actually (ab)^n is regular; (ba)^n regular; but coordinating n across both factors requires equality → it’s isomorphic to { (ab)^n (ba)^n } which is { (ab)^n (ba)^n } = { (ab)^n (ba)^n } = non-CFL due to equality constraint. So choose A.
94. Q94: Which of the following statements is true?
    A. Every CFL can be parsed in linear time.
    B. Deterministic CFLs can be parsed in linear time (LR parsing).
    C. Every unambiguous CFL admits an O(n) parser.
    D. All CFLs are inherently exponential to parse.
    Answer: B.
    Solution: Many DCFLs (LR(k), LALR) permit linear-time deterministic parsing. General CFLs parsed in O(n^3) in worst-case (Earley/CYK).
95. Q95: Which of the following is true regarding intersection emptiness of two CFGs? (Given G1, G2)
    A. Decidable by product PDA construction
    B. Undecidable in general
    C. Equivalent to CFG membership problem
    D. Always true if alphabets differ
    Answer: B.
    Solution: Emptiness of intersection of two arbitrary CFLs is undecidable.
96. Q96: Which of the following is context-free? Σ={a,b,c}
    A. { a^n b^m c^{n+m^2} | n,m≥0 }
    B. { a^n b^n c^m d^m e^k | n,m,k≥0 }
    C. { a^{n!} | n≥0 }
    D. { ww | w∈{a,b}* }
    Answer: B.
    Solution: B concatenates balanced pairs a^n b^n and c^m d^m and a regular e^k — CFL. A,C,D non-CFL.
97. Q97: Which of the following problems is undecidable for CFGs?
    A. Is the intersection of two CFLs empty?
    B. Is the language of CFG finite?
    C. Does a CFG generate a particular terminal?
    D. Does a CFG generate ε?
    Answer: A.
    Solution: Emptiness of intersection of two CFLs is undecidable; B, C, D decidable.
98. Q98: Which of the following is an example of a deterministic context-free language?
    A. { a^i b^j c^k | i = j or j = k }
    B. { a^n b^n }
    C. { ww^R | w∈{a,b}* }
    D. { a^n b^m a^n | n,m≥0 }
    Answer: B.
    Solution: B is standard DCFL. A inherently ambiguous; C non-DCFL; D non-DCFL.
99. Q99: Which of the following languages is context-free? Σ={a,b}
    A. { a^n b^{n^2} | n≥0 }
    B. { a^n b^m a^{n+m} | n,m≥0 }
    C. { a^n b^n a^n b^n | n≥0 }
    D. { a^i b^j | i ≤ j·2 }
    Answer: D.
    Solution: D enforces a linear inequality (i ≤ 2j) which is semilinear and can be recognized by a PDA (push a’s, then consume two b’s per popped a etc with nondet adjustments) — construct grammar generating appropriate combos. A,B,C non-CFL.
100. Q100: Which of the following summarises classical facts about CFLs?
     A. CFLs closed under union, concatenation, and star; not closed under intersection or complement. Emptiness and membership decidable; equivalence undecidable.
     B. CFLs closed under complement and intersection only; emptiness undecidable.
     C. CFLs identical to regular languages.
     D. CFLs closed under all Boolean operations.
     Answer: A.
     Solution: This lists the standard closure/decision properties for CFLs.

About the Author

examhopeinfo@gmail.com

Administrator

Visit Website View All Posts