Question bank — Context-free grammars (CFG) — productions, derivations, parse trees

False. A grammar is one specific recipe; many different grammars can generate the exact same language $L(G)$. Confusing the recipe with the dish is the root of most CFG mistakes.

True. Any DFA can be mechanically turned into a right-linear CFG, so regular languages sit strictly inside the context-free languages in the Chomsky hierarchy (the inner boxes of figure s01).

False. The classic witness is $\{{(}^n{)}^n\}$: unbounded nesting needs a stack, which finite states (a DFA) cannot provide, but $S\to (S)\mid \epsilon$ recurses freely.

False. Order in the output matters completely — it's a string! "Context-free" only says the left-hand side of every rule is a single variable, so a rule's applicability never depends on neighbours.

True. An $\epsilon$-rule merely lets a variable vanish; infinity comes from recursion (e.g. $S\to aS$), not from erasing.

False. You need two derivations that yield distinct parse trees (equivalently, two distinct leftmost derivations). Two derivations that differ only in the order you expanded variables are the same tree.

False — it's the reverse. Ambiguity is a property of the grammar: a language can have both ambiguous and unambiguous grammars generating it.

True. Leftmost-derivation ↔ parse-tree is a bijection. That's precisely why we count distinct trees, not distinct derivations, when hunting ambiguity.

False. If $S{\Rightarrow }^{\ast }\epsilon$ (e.g. via $S\to \epsilon$), then $\epsilon \in L(G)$. The matched-parentheses grammar $S\to (S)S\mid \epsilon$ generates $\epsilon$.

False. A sentential form is anything derivable from $S$ (it may still contain variables). Only fully-terminal strings, $w\in {\Sigma }^{\ast }$, belong to $L(G)$.

False. $G_2$ (ambiguous) and $G_3$ (precedence-layered) generate the same arithmetic language; only the set of parse trees changes, collapsing to one tree per string.

No. The LHS has a terminal $a$ next to the variable, so the LHS is not a single variable — that's a context-sensitive rule, outside CFG.

$T$ is an unreachable variable — no derivation from $S$ ever produces $T$ — so it contributes nothing to $L(G)$. The grammar stays valid, but such a rule is useless and is removed by grammar cleanup (see figure s04).

Wrong diagnosis. $G_2$'s flaw is ambiguity (no precedence), not left-recursion. $G_3$ is deliberately left-recursive ($E\to E+T$) to get correct left-associativity — recursion isn't the disease.

Nonsense — two trees for one string still means one language. Ambiguity is about multiple structures for the same string, not multiple languages.

It's harmless to the language (it derives nothing new) but it makes the grammar have infinitely many derivations of any string via useless loops — a cycle that also blocks some parsing algorithms.

False. $G_2$ has neither $\epsilon$-rules nor unit rules yet is ambiguous. Removing $\epsilon$/unit rules (a Chomsky normal form step) does not remove ambiguity.

Because that single restriction is literally the definition of "context-free": the rule $\alpha A\beta \Rightarrow \alpha \gamma \beta$ leaves the context $\alpha ,\beta$ untouched, so a variable can be rewritten regardless of neighbours.

A derivation is a linear list whose order is often arbitrary; the tree discards that incidental ordering and keeps only the structural truth (parent–child), which is what actually determines meaning (compare figures s02 and s03).

The parse tree dictates meaning; a+a*a could mean $a+(a\ast a)$ or $(a+a)\ast a$. Two trees = two possible values, so the compiler cannot decide what the program means.

Each layer encodes one precedence tier — $F$ (factor) tightest, $T$ (term, *) next, $E$ (expression, +) loosest — so * is forced to group before +, killing the ambiguity of $G_2$.

Matching ${(}^n{)}^n$ requires counting unboundedly deep nesting. A CFG's recursion gives an implicit stack (formalised by a pushdown automaton); a regex/DFA has only finitely many states and cannot count without bound.

It states a necessary property of context-free languages, not a sufficient one; it can only ever disprove membership (by finding an unpumpable string), never confirm it.

Left-recursion makes the operator left-associative: a-a-a groups as $(a-a)-a$, matching how subtraction actually works. Right-recursion would wrongly group $a-(a-a)$.

$L(G)=\varnothing$. No production ever reaches a terminal-only string, so nothing is in the language despite $S$ having a rule.

$L(G)=\{\epsilon \}$, the single empty string. Note this is not the empty language $\varnothing$: one member exists, it just happens to be empty.

Yes, with the standard exception rule: CNF forbids $\epsilon$ everywhere except an allowed $S\to \epsilon$ (with $S$ not on any RHS), specifically so that $\epsilon \in L(G)$ can still be expressed.

No. Same language ($L(G_1)=L(G_2)$) says nothing about structure; the grammars can assign totally different trees to the same string, and one may be ambiguous while the other isn't.

Yes — that's the whole point. A finite rule set like $S\to aS\mid \epsilon$ generates infinitely many strings through recursion; grammars are always finite by definition.

Yes. Just list one production $S\to w_i$ per string; a finite set of such rules generates exactly that finite language, and finite languages are even regular.

The variable is non-productive and generates nothing, so any rule mentioning it is effectively dead. Such variables are removed during grammar cleanup before building a Chomsky normal form (figure s04).