Context-Free Grammars(Theory of Computation) MCQs

Context-Free Grammars(Theory of Computation)

1. Which of the following languages is generated by the grammar S → aSa | bSb | ε?
   A) Palindromes over {a,b} of even length only
   B) All palindromes over {a,b} (any length)
   C) Strings with equal numbers of a and b
   D) Strings of the form a^n b^n
   Answer: B
   Explanation: Grammar builds matching symbols around S and allows ε → all palindromes (odd and even).
2. A grammar is ambiguous if:
   A) It generates more than one string
   B) Some string has two distinct leftmost derivations or two parse trees
   C) It is context-sensitive
   D) It is not in CNF
   Answer: B
   Explanation: Ambiguity means at least one string has two different parse trees/derivations.
3. Which normal form restricts productions to either A → BC or A → a (plus possibly S → ε)?
   A) Greibach Normal Form (GNF)
   B) Chomsky Normal Form (CNF)
   C) Backus-Naur Form (BNF)
   D) Kuroda Normal Form
   Answer: B
   Explanation: CNF has exactly those production shapes.
4. The language { a^n b^n c^n | n ≥ 0 } is:
   A) Context-free
   B) Not context-free but context-sensitive
   C) Regular
   D) Finite
   Answer: B
   Explanation: Equal triple counts not CFL (pumping lemma), but context-sensitive.
5. The class of context-free languages (CFLs) is closed under:
   A) Intersection with arbitrary CFLs
   B) Complementation
   C) Intersection with regular languages
   D) Set difference with CFLs
   Answer: C
   Explanation: CFL ∩ REG is CFL; intersection of two CFLs or complement not closed in general.
6. The pumping lemma for CFLs is used to:
   A) Prove that a language is context-free
   B) Prove that a language is not context-free
   C) Convert grammar to CNF
   D) Minimize grammar
   Answer: B
   Explanation: Pumping lemma gives a necessary condition for CFLs to refute CFLness.
7. A grammar in Greibach Normal Form (GNF) has productions of the form:
   A) A → a α where a is terminal, α is (possibly empty) string of variables
   B) A → BC only
   C) A → ε only
   D) A → α a β with terminals anywhere
   Answer: A
   Explanation: GNF: productions start with a terminal followed by variables.
8. Is the emptiness problem (deciding if L(G)=∅) for CFGs decidable?
   A) Yes, decidable
   B) No, undecidable
   C) Only for CNF grammars
   D) Only for regular grammars
   Answer: A
   Explanation: Compute reachable generating variables; check if start derives terminal string.
9. The membership problem (“w ∈ L(G)?”) for CFGs can be solved in time O(n^3) by:
   A) CYK algorithm (if grammar is CNF)
   B) Earley algorithm only
   C) Pumping lemma
   D) Undecidable
   Answer: A
   Explanation: CYK runs in O(n^3) for CNF grammars; Earley can be similar/better.
10. Every CFL can be generated by a grammar in CNF. True or False?
    A) True (except possibly ε)
    B) False
    Answer: A
    Explanation: Any CFG can be transformed into CNF (with handling of ε separately).
11. The intersection of two context-free languages is always context-free. True or False?
    A) False
    B) True
    Answer: A
    Explanation: Intersection of CFLs need not be CFL (classic counterexample).
12. Which model is equivalent in power to CFGs for recognition?
    A) Deterministic finite automata (DFA)
    B) Pushdown automata (PDA)
    C) Turing machines (TM)
    D) Finite transducers
    Answer: B
    Explanation: PDAs (nondeterministic) accept exactly CFLs.
13. The language { ww^R | w ∈ {a,b}* } (even palindromes of the form ww^R) is:
    A) Context-free
    B) Not context-free
    C) Regular
    D) Finite
    Answer: A
    Explanation: Grammar S → XX^R? More simply S → aSa | bSb | ε generates palindromes including ww^R; language is CFL.
14. Converting a CFG to an equivalent PDA usually yields:
    A) Deterministic PDA always
    B) Nondeterministic PDA (NPDA)
    C) DFA
    D) Turing machine
    Answer: B
    Explanation: General CFG conversion yields nondeterministic PDA.
15. Left recursion in a grammar affects top-down parsers because:
    A) It makes grammar ambiguous
    B) It causes infinite recursion in naive recursive-descent parsers
    C) It converts grammar to CNF
    D) It makes grammar regular
    Answer: B
    Explanation: Left recursion leads to nonterminating calls in naive top-down parsing.
16. The language { a^n b^m c^k | n = m or m = k } is:
    A) Context-free (union of two CFLs)
    B) Not context-free
    C) Regular
    D) Context-sensitive only
    Answer: A
    Explanation: Union of {a^n b^n c^k} and {a^n b^m c^m} each CFL → union of CFLs is CFL? Wait: Union of two CFLs is CFL. So A.
    (Note: union of CFLs is CFL — correct.)
17. Ambiguity of CFGs is:
    A) Decidable (always)
    B) Undecidable in general
    C) Decidable for all grammars in CNF
    D) Trivial to check by enumeration
    Answer: B
    Explanation: General ambiguity problem for CFGs is undecidable.
18. A grammar S → SS | a generates:
    A) Balanced parentheses language
    B) {a}* (all nonempty strings of a) with full binary bracketing? Actually generates any positive number of a’s with arbitrary binary concatenation ⇒ defines a+ (one or more a) with different parse trees → ambiguous.
    Options likely: A) { a^n | n ≥ 1 }, B) { a^n b^n }, C) Regular? D) Empty.
    Answer: A {a}^+
    Explanation: S expands to concatenation of copies of a → nonempty strings of a; grammar ambiguous.
19. Which algorithm can transform any CFG to Greibach Normal Form?
    A) Yes, algorithm exists (with elimination of left recursion and left factoring)
    B) No
    C) Only for regular grammars
    D) Only for deterministic grammars
    Answer: A
    Explanation: There is a constructive algorithm to convert CFG to GNF.
20. The equivalence problem for CFGs (do G1 and G2 generate same language?) is:
    A) Decidable
    B) Undecidable
    C) Decidable only for LL(1) grammars
    D) Polynomial time
    Answer: B
    Explanation: Equivalence of two arbitrary CFGs is undecidable.
21. Which of the following is a deterministic CFL (DCFL) example?
    A) { a^n b^n | n ≥ 0 }
    B) { a^n b^n c^n | n ≥ 0 }
    C) { ww | w ∈ {a,b}* }
    D) {a^m b^n | m,n arbitrary }
    Answer: A
    Explanation: {a^n b^n} is deterministic; accepted by a DPDA pushing a’s and popping on b’s.
22. Is the complement of a deterministic CFL always deterministic CFL?
    A) Yes
    B) No (DCFLs closed under complement) — Actually deterministic CFLs are closed under complement. So answer: A.
    Answer: A
    Explanation: Deterministic CFL class closed under complementation.
23. The CYK (Cocke-Younger-Kasami) algorithm requires grammar in:
    A) CNF
    B) GNF
    C) Any form
    D) Greibach only
    Answer: A
    Explanation: CYK works on grammars in Chomsky Normal Form.
24. Which of these languages is context-free but not deterministic context-free?
    A) { a^n b^n }
    B) { ww^R }
    C) { a^i b^j c^k | i=j or j=k } (this is CFL but non-deterministic?) This is known to be CFL but not deterministic? Safer classic example: L = { a^n b^n c^m | n,m ≥0 } ∪ { a^n b^m c^m | n,m ≥0 } is CFL but not DCFL. So answer choose one.
    Answer: The union examples; choose C.
    Explanation: There are CFLs that are inherently ambiguous or non-deterministic (not accepted by any DPDA).
25. A parse tree for a sentence of a CFG corresponds to:
    A) A leftmost derivation only
    B) A rightmost derivation only
    C) Both a leftmost and a rightmost derivation (there is a one-to-one correspondence in context of derivations)
    D) No derivation
    Answer: C
    Explanation: A parse tree yields both leftmost and rightmost derivations (order differs but tree structure same).
26. The language generated by S → aSb | S → SS | ε is:
    A) { a^n b^n | n ≥ 0 } (union of concatenations → actually SS allows concatenation of such patterns → yields balanced a^n b^n sequences concatenated → equals { a^n1 b^n1 a^n2 b^n2 … } which is { (a^n b^n)^+ } plus ε). So choose option accordingly.
    Answer: A variant: strings formed by concatenation of zero or more blocks a^n b^n.
    Explanation: S either ε or a S b or concatenation → generates sequences of matched a^k b^k blocks.
27. The decision problem “Is a CFG ambiguous?” is:
    A) Decidable for all CFGs
    B) Undecidable in general
    C) Decidable for CNF only
    D) Trivial
    Answer: B
    Explanation: Ambiguity is an undecidable property for CFGs.
28. Eliminating ε-productions from a CFG may:
    A) Always preserve language exactly (including ε) by proper handling
    B) Never preserve language
    C) Make grammar regular
    D) Make grammar ambiguous
    Answer: A
    Explanation: There is a standard elimination that preserves L(G) \ {ε}, with ε handled separately.
29. Which closure property holds for CFLs?
    A) Closed under Kleene star
    B) Closed under intersection with CFLs
    C) Closed under complement
    D) Closed under intersection with CFLs and complement
    Answer: A
    Explanation: CFLs closed under union, concatenation, and star; not closed under intersection with CFLs or complement.
30. Greibach Normal Form is particularly useful to:
    A) Show that every CFL is generated by some LL(1) grammar
    B) Construct a pushdown automaton with leftmost derivations (top-down parser)
    C) Convert CFG to DFA
    D) Prove undecidability
    Answer: B
    Explanation: GNF ensures productions start with terminal enabling top-down PDAs and establishing bounds on derivation length.
31. The language { a^p | p is prime } over unary alphabet is:
    A) Regular
    B) Context-free? Not context-free (primality not CFL)
    C) Context-sensitive only
    D) Finite
    Answer: B (Not CFL) — More precise: not context-free.
    Explanation: Unary prime set not regular; not CFL either (non-CFL).
32. Left factoring a grammar helps in:
    A) Eliminating left recursion only
    B) Making grammar suitable for predictive (LL(1)) parsing by removing common prefixes
    C) Converting to CNF
    D) Minimizing grammar length
    Answer: B
    Explanation: Left factoring resolves choices with common prefixes enabling LL(1) parsing.
33. The language { a^n b^m c^k | n = m or n = k } is:
    A) Context-free
    B) Not context-free
    C) Regular
    D) Context-sensitive only
    Answer: A
    Explanation: It’s union of two CFLs with equality constraints between two counters.
34. An inherently ambiguous language is:
    A) One with no unambiguous CFG generating it
    B) One that has some unambiguous grammar
    C) Always regular
    D) Context-sensitive only
    Answer: A
    Explanation: Inherently ambiguous means every CFG for it is ambiguous.
35. Which of these languages is deterministic context-free? { ww^R | # separation? } Classic: { a^n b^n } is DCFL. Pick that.
    Answer: { a^n b^n }
    Explanation: DPDA can accept by pushing a’s and popping b’s deterministically.
36. The pumping lemma for CFLs states there exists a pumping length p such that any string s with |s| ≥ p can be written as:
    A) s = uvxyz with conditions on v and y pumping
    B) s = xyz with conditions on y only
    C) s = uvw with no constraints
    D) None
    Answer: A
    Explanation: Classic CFL pumping lemma uses five parts where v or y nonempty and pumping within allows infinite variants.
37. Is membership of a string w in L(G) decidable for any CFG G?
    A) Yes (via CYK/Earley)
    B) No
    C) Only for regular grammars
    D) Only for deterministic grammars
    Answer: A
    Explanation: Membership problem is decidable (polynomial) for CFGs.
38. Converting CFG to PDA requires:
    A) Stack usage to handle nested dependencies
    B) No stack (just finite memory)
    C) Turing tape
    D) None
    Answer: A
    Explanation: PDA uses stack to manage nested structure of CFG derivations.
39. A grammar with productions S → 0S1 | 01 is:
    A) Unambiguous (each string has unique parse)
    B) Ambiguous
    C) Not context-free
    D) Regular
    Answer: A
    Explanation: This grammar generates strings 0^n 1^n with unique derivation structure (unambiguous).
40. The emptiness problem for intersection of a CFL and regular language (is L(CFG) ∩ L(REG) = ∅?) is:
    A) Decidable
    B) Undecidable
    C) Only decidable for deterministic CFGs
    D) NP-complete
    Answer: A
    Explanation: CFL ∩ REG is CFL; emptiness for CFGs is decidable.
41. Is universality (L(G) = Σ*) for CFGs decidable?
    A) Undecidable
    B) Decidable
    C) Only for regular grammars
    D) NP-hard
    Answer: A
    Explanation: Universality for CFGs is undecidable.
42. The class of deterministic CFLs is closed under intersection with regular languages. True or False?
    A) True
    B) False
    Answer: A
    Explanation: DCFL ∩ REG is DCFL.
43. Remove unit productions (A → B) from a CFG: language preserved?
    A) Yes (algorithm exists to eliminate unit rules preserving language)
    B) No
    C) Only for CNF
    D) Only for deterministic grammars
    Answer: A
    Explanation: Standard elimination of unit productions preserves the generated language.
44. A CFG is in Chomsky Normal Form (CNF) cannot have:
    A) Productions of form A → a
    B) Productions of form A → BC
    C) ε-productions (except maybe S→ε)
    D) Unit productions A → B
    Answer: D
    Explanation: CNF disallows unit productions; only A→BC or A→a allowed (plus S→ε optional).
45. The minimal pumping length in the CFL pumping lemma is:
    A) Guaranteed to exist but not necessarily efficiently computable from the grammar size
    B) Always equal to number of variables
    C) Infinite
    D) Zero
    Answer: A
    Explanation: Some p exists but computing smallest p isn’t trivial.
46. A DPDA recognizes exactly the deterministic CFLs. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Deterministic PDA characterize DCFLs.
47. The problem “Given CFG G and regular language R, is L(G) ⊆ R?” is:
    A) Decidable (use intersection and emptiness)
    B) Undecidable
    C) Only for unary alphabets
    D) NP-complete
    Answer: A
    Explanation: L(G) ⊆ R iff L(G) ∩ (Σ* \ R) = ∅; complement of regular is regular; test emptiness.
48. Which of these operations can produce a non-CFL from CFL operands?
    A) Intersection of two CFLs
    B) Union of two CFLs
    C) Concatenation of two CFLs
    D) Kleene star of a CFL
    Answer: A
    Explanation: Intersection of two CFLs may not be CFL.
49. The language { a^n b^m | n divides m } is:
    A) Context-free? Likely not; arithmetic divisibility not CFL.
    B) Not context-free
    C) Regular
    D) Context-sensitive
    Answer: B
    Explanation: Divisibility relations generally exceed CFL capabilities.
50. Ambiguity can sometimes be resolved by:
    A) Refactoring grammar (e.g., eliminating ambiguous rules)
    B) It is impossible for inherently ambiguous languages
    C) Using precedence and associativity declarations in parser generators
    D) All of the above (A and C possible, but B states impossible for some)
    Answer: D (interpreted as A and C plus note some languages inherently ambiguous cannot be disambiguated)
    Explanation: Often refactoring or parsing rules remove ambiguity, but inherent ambiguity may remain unfixable.
51. The Parikh image of a CFL is:
    A) Semilinear (Parikh’s theorem)
    B) Arbitrary set
    C) Noncomputable
    D) Regular
    Answer: A
    Explanation: Parikh theorem: vector of symbol counts of CFLs is a semilinear set.
52. The membership problem for deterministic context-free languages is:
    A) Decidable in linear time (for real-time DPDAs or using LR parsing)
    B) Undecidable
    C) Exponential time only
    D) Only approximate
    Answer: A
    Explanation: Many deterministic CFG parsing algorithms (LR, LALR, recursive descent) parse in linear time.
53. The language { a^n b^m a^n | n,m ≥ 0 } is:
    A) Not context-free (requires matching outer a counts across arbitrary middle b’s)
    B) Context-free
    C) Regular
    D) Context-sensitive only
    Answer: A
    Explanation: Copying matching a^n at both ends with arbitrary b middle is non-CFL.
54. Which grammar form ensures no left recursion and productions start with a terminal?
    A) Greibach Normal Form (GNF)
    B) CNF
    C) Regular grammar
    D) Chomsky type-0
    Answer: A
    Explanation: GNF productions begin with terminal, so no left recursion.
55. Is emptiness of intersection of two CFGs decidable?
    A) Undecidable in general
    B) Decidable
    C) Only for deterministic CFGs
    D) NP-hard
    Answer: A
    Explanation: Intersection of two CFGs may not be CFG; emptiness problem for intersection is undecidable in general.
56. Which of the following is true about LL(1) grammars?
    A) They are a subset of deterministic context-free grammars
    B) They can represent all CFLs
    C) They are always ambiguous
    D) They require left recursion
    Answer: A
    Explanation: LL(1) grammars are deterministic and parsable by predictive parser; they form a strict subset of DCFLs.
57. The CYK algorithm returns whether w ∈ L(G) in O(n^3). For inputs of length 50, complexity roughly proportional to:
    A) 125,000 ops (50^3)
    B) 2500 ops
    C) 50 ops
    D) Exponential in n
    Answer: A
    Explanation: Cubic in input length.
58. Which CFG generates the language of balanced parentheses?
    A) S → ( S ) S | ε
    B) S → SS | (S) | ε (equivalent)
    C) Both A and B
    D) Neither
    Answer: C
    Explanation: Both grammars produce balanced parentheses.
59. The problem of determining whether a CFG generates any string of even length only is:
    A) Decidable (analyze productions modulo 2)
    B) Undecidable
    C) NP-complete
    D) Requires Turing machine
    Answer: A
    Explanation: Length modulo k properties can be computed via reachability in grammar graph.
60. Are leftmost and rightmost derivations always of equal length (number of steps) for a given parse tree?
    A) Yes (same number of production applications)
    B) No
    Answer: A
    Explanation: Any derivation corresponding to same parse tree uses same number of production expansions.
61. A grammar that generates regular language can be:
    A) Context-free (since regular ⊂ CFL)
    B) Not context-free
    C) Only regular grammars
    D) None
    Answer: A
    Explanation: Regular grammars are a subset of CFGs.
62. The language { a^n b^n | n ≥ 0 } ∪ { a^n b^2n | n ≥ 0 } is context-free. True or False?
    A) True (union of two CFLs)
    B) False
    Answer: A
    Explanation: Finite union of CFLs is CFL.
63. The set of sentential forms reachable from start variable in finite steps can be:
    A) Infinite (since variables can expand arbitrarily)
    B) Always finite
    C) Equal to language only
    D) Empty
    Answer: A
    Explanation: There may be infinitely many sentential forms (though language may be infinite).
64. A regular grammar is a CFG where productions are of form:
    A) A → aB or A → a or A → ε (right-linear)
    B) A → BC only
    C) A → aA only
    D) None
    Answer: A
    Explanation: Right-linear (or left-linear) forms generate regular languages.
65. The problem “Does CFG G generate finite language?” is:
    A) Decidable (check cycles that generate terminals)
    B) Undecidable
    C) Only for CNF
    D) NP-hard
    Answer: A
    Explanation: Detect cycles that can generate unbounded strings to decide finiteness.
66. Removing useless symbols (nonproductive or unreachable) from CFG: effect on L(G)?
    A) Language preserved exactly
    B) Language reduced unpredictably
    C) Always empties grammar
    D) Creates ambiguity
    Answer: A
    Explanation: Removing useless symbols gives equivalent grammar generating same language.
67. The leftmost derivation of abba under grammar S→ aSb | ε yields:
    A) A valid derivation (a b b a? careful) Actually this grammar yields palindromes of form a^n b^n with equal count and mirrored positions, so abba (a b b a) is not of form a^n b^n (that’s a^2 b^2 = aabb) but S produces symmetric matching: abba produced by S→ a S b with S→ b? Not matching. Hmm safer: choose another grammar. Skip. (Ensure questions unambiguous.)
68. (restate) For grammar S → a S a | b S b | ε, the leftmost derivation of abba exists. True or False?
    A) True (abba is palindrome)
    B) False
    Answer: A
    Explanation: Palindrome grammar derives abba.
69. The Chomsky hierarchy ranks grammars: Type-3 ⊂ Type-2 ⊂ Type-1 ⊂ Type-0. Which corresponds to CFGs?
    A) Type-2
    B) Type-3
    C) Type-1
    D) Type-0
    Answer: A
    Explanation: CFGs are Type-2 grammars.
70. A grammar is useless if:
    A) No terminal string reachable from its variables (nonproductive) or variable unreachable from start
    B) It is ambiguous
    C) It has left recursion
    D) It is not CNF
    Answer: A
    Explanation: Useless symbols are unreachable or nonproductive and can be removed.
71. The language { a^i b^j c^k | i = j or j = k } — we saw earlier similar — is CFL. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Union of two CFLs with equality constraints on two counters.
72. A PDA that accepts by empty stack recognizes same class as one that accepts by final state. True or False?
    A) True (they are equivalent)
    B) False
    Answer: A
    Explanation: Acceptance by empty stack and by final state are equivalent for PDAs.
73. LL(1) grammars are not closed under union. True or False?
    A) True (union might break LL(1))
    B) False
    Answer: A
    Explanation: LL(1) is a restrictive subclass; union needn’t preserve properties.
74. Which grammar is left-recursive? A → A a | b ?
    A) Yes (A → A a)
    B) No
    Answer: A
    Explanation: Left recursion when variable appears as leftmost symbol on RHS.
75. An unambiguous grammar always produces a unique parse tree for each string. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Unambiguous means exactly one parse tree per string.
76. Which of the following languages is inherently ambiguous? { a^i b^j c^k | i = j or j = k } is known example of inherently ambiguous? Actually classic example is L = {a^i b^j c^k | i = j or j = k} is inherently ambiguous.
    Answer: That language is inherently ambiguous.
    Explanation: Some strings have two distinct parses and no unambiguous grammar exists.
77. Is it decidable whether a given CFG is ambiguous?
    A) Undecidable
    B) Decidable
    Answer: A
    Explanation: Ambiguity of CFGs is undecidable.
78. A simple unambiguous grammar for arithmetic expressions using precedence and associativity can be constructed. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Use separate nonterminals per precedence level to ensure unambiguous parse.
79. The yield (frontier) of a parse tree is:
    A) The string of terminals read from the leaves left to right
    B) The set of variables used
    C) The first terminal only
    D) None
    Answer: A
    Explanation: Yield is the derived terminal string.
80. A grammar in CNF has no terminal symbols in right-hand sides longer than 1. True or False?
    A) True
    B) False
    Answer: A
    Explanation: CNF restricts RHS to either two variables or single terminal.
81. The problem of universality for deterministic CFLs is:
    A) Decidable? For DCFLs universality undecidable? I believe universality for DCFLs is undecidable. But need confirm: Universality is undecidable for CFLs generally; for DCFLs also undecidable. So answer: Undecidable.
    Answer: Undecidable.
    Explanation: Universality remains undecidable in general for deterministic CFLs as well.
82. Which conversion can cause exponential blowup in grammar size?
    A) Converting NFA to DFA equivalent for regular languages analogous converting ambiguous CFG to unambiguous? For CFGs, converting to CNF grows polynomially. Converting PDA to equivalent DPDA may blow up. But commonly converting CFG to equivalent regular expression can blow up? Hmm choose: Converting CFG to equivalent regular expression not always relevant. Safer: Converting ambiguous grammar to unambiguous grammar may cause blowup. But classic: converting NFA to DFA exponential; for grammars, elimination to GNF can be exponential. I’ll choose: Converting grammar to Greibach Normal Form may cause blowup.
    Answer: Conversion to GNF can cause blowup in size.
    Explanation: Transformations to normal forms can increase grammar size significantly.
83. The closure of CFLs under homomorphism: true or false?
    A) True
    B) False
    Answer: A
    Explanation: CFLs closed under homomorphism and inverse homomorphism.
84. For a CFG G, the set of lengths of strings in L(G) is:
    A) Ultimately periodic (semilinear)
    B) Arbitrary
    C) Infinite only
    D) Finite only
    Answer: A
    Explanation: Parikh image semilinear implies lengths form ultimately periodic set.
85. The membership problem for intersection of CFL and CFL is:
    A) Undecidable in general (since intersection may not be CFL)
    B) Decidable always
    Answer: A
    Explanation: Because intersection may simulate Turing power leading to undecidability in some formulations.
86. A pushdown automaton can be made deterministic for every CFL. True or False?
    A) False
    B) True
    Answer: A
    Explanation: Some CFLs are inherently nondeterministic (not DCFLs).
87. The yield (frontier) of any parse tree has length equal to:
    A) Number of leaves (terminals), yes
    B) Number of internal nodes
    C) Number of variables
    D) None
    Answer: A
    Explanation: Terminals at leaves produce the derived string.
88. Ambiguity may be necessary for some languages (inherently ambiguous). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Some languages have no unambiguous CFG.
89. Which algorithm decides whether L(G) is finite?
    A) Detect cycles in derivation graph that can produce terminals → if none, finite
    B) CYK
    C) Pumping lemma
    D) Undecidable
    Answer: A
    Explanation: Finiteness decidable by analyzing dependency graph for productive cycles.
90. The language { a^n b^n c^m | n,m ≥ 0 } is:
    A) Context-free
    B) Not context-free
    C) Regular
    D) Context-sensitive only
    Answer: A
    Explanation: Can be generated by S → A C, A → aAb | ε, C → cC | ε.
91. Which of these algorithms builds a parse table for LL(1) parsing?
    A) Compute FIRST and FOLLOW sets then table entries
    B) CYK
    C) Earley
    D) CYK + closure
    Answer: A
    Explanation: LL(1) parse table computed using FIRST/FOLLOW.
92. A grammar S → aS | Sb | ε generates:
    A) All strings in a* b? Actually check: can produce any a’s on left and b’s on right but S → aS adds a to left; S → Sb adds b to right; so L = { a^i b^j | i,j ≥0 } = a b* .
    Answer: a* b*
    Explanation: Left and right generation produce independent counts.
93. The intersection of a CFL with a regular language is:
    A) CFL (closed)
    B) Not CFL
    C) Regular only
    D) Undecidable
    Answer: A
    Explanation: Use product construction of PDA and DFA.
94. An LR(0) grammar:
    A) Is suitable for LR(0) parsing without lookahead if no conflicts
    B) Always ambiguous
    C) Equivalent to LL(1) grammar
    D) Undecidable detection
    Answer: A
    Explanation: LR(0) parser works if parsing table has no conflicts.
95. The emptiness problem for CFGs (L(G) = ∅?) complexity is:
    A) Polynomial time (linear)
    B) Undecidable
    C) Exponential
    D) NP-hard
    Answer: A
    Explanation: Reachability of generating variables solvable in linear/polynomial time.
96. Which of the following languages is not context-free? { a^n b^n c^n | n ≥ 0 } — classic.
    Answer: Not context-free.
    Explanation: Requires equality of three counters.
97. Deterministic linear bounded automaton recognizes:
    A) Context-sensitive languages
    B) Context-free languages
    C) Regular languages
    D) Recursively enumerable only
    Answer: A
    Explanation: LBA accepts context-sensitive languages.
98. Does every CFG have an equivalent unambiguous grammar?
    A) No — some languages are inherently ambiguous
    B) Yes
    Answer: A
    Explanation: Inherently ambiguous languages have no unambiguous grammar.
99. The S → AB, A → aA | ε, B → bB | ε grammar generates:
    A) a* b*
    B) a^n b^n
    C) (ab)*
    D) a+b+
    Answer: A
    Explanation: A produces a* and B produces b; concatenation a b*.
100. The pumping lemma for CFGs guarantees you can pump in two places (v and y). This differs from regular pumping which pumps one substring. True or False?
     A) True
     B) False
     Answer: A
     Explanation: CFL pumping splits string as uvxyz with v and y pumpable.
101. Final conceptual: Kleene’s theorem relates:
     A) Regular expressions and finite automata
     B) Context-free grammars and PDAs
     C) CFGs and TMs
     D) All grammars and machines
     Answer: A
     Explanation: Kleene’s theorem: regular expressions ↔ finite automata; CFGs ↔ PDAs is another classic equivalence.

About the Author

examhopeinfo@gmail.com

Administrator

Visit Website View All Posts