Language L has two CFGs: Grammar G₁ allows some strings to be derived in multiple ways (ambiguous), while Grammar G₂ derives every string in exactly one way (unambiguous). What can we conclude about L?
AL is not context-free because an ambiguous grammar exists for it
BL is context-free, and the existence of an unambiguous grammar confirms this
CL is inherently ambiguous — the unambiguous G₂ must be incorrect
DG₁ and G₂ generate different languages; the unambiguous one defines the 'true' L
Ambiguity is a property of a grammar, not a language. A context-free language is inherently ambiguous only if every possible grammar for it is ambiguous — a much stronger condition. The existence of even one unambiguous grammar means the language is not inherently ambiguous. Since G₂ is unambiguous and generates L, L is a context-free language with a clean, unambiguous grammar. Options A and C confuse grammar-level ambiguity with language-level properties.
Question 2 Multiple Choice
A student argues that {a^n b^n c^n | n ≥ 0} is context-free because 'a pushdown automaton can count the a's on the stack, match them to b's, and then match the remaining stack contents to c's.' What is the flaw in this reasoning?
APushdown automata cannot use their stack to count symbols
BThe stack can match a's to b's by popping as b's are read, but once the stack is empty at the end of the b's, no memory remains to verify the count of c's
CThe language is regular and therefore too simple to require a context-free grammar
DThe pumping lemma does not apply to languages defined with three distinct symbol types
The PDA runs correctly through the a's (pushing) and b's (popping), leaving an empty stack at the boundary. But to verify c's match the original count, it would need to remember n — and the stack is now empty. A single stack cannot simultaneously count two independent quantities. The student's PDA has used up its memory. This is precisely why {a^n b^n c^n} is not context-free: the language requires tracking two independent equalities (|a|=|b| and |b|=|c|), and a stack can only enforce one balance constraint at a time.
Question 3 True / False
If a context-free grammar for a language is ambiguous, then the language itself is inherently ambiguous and no unambiguous grammar for it can exist.
TTrue
FFalse
Answer: False
Ambiguity is a property of a specific grammar, not the language. Many context-free languages have both ambiguous and unambiguous grammars. For example, a naive grammar for arithmetic expressions may allow multiple parse trees for '2+3×4' (the order of operations is ambiguous), but a carefully structured grammar using separate nonterminals for expressions, terms, and factors yields unambiguous parse trees. Inherent ambiguity — where every grammar for the language is ambiguous — is a special, provably rare property that requires separate proof.
Question 4 True / False
The class of languages generated by context-free grammars is exactly the class of languages recognized by nondeterministic pushdown automata.
TTrue
FFalse
Answer: True
This equivalence is one of the central theorems of formal language theory, proved constructively in both directions. Given any CFG, you can construct an equivalent NPDA that simulates leftmost derivations using its stack. Given any NPDA, you can construct an equivalent CFG using a triple-state encoding of transitions. The equivalence is the reason the two formalisms are used interchangeably: grammars are useful for specifying and understanding languages; NPDAs are useful for reasoning about recognition and complexity.
Question 5 Short Answer
Explain why a pushdown automaton can recognize {a^n b^n | n ≥ 0} but cannot recognize {a^n b^n c^n | n ≥ 0}. What property of the stack makes the difference?
Think about your answer, then reveal below.
Model answer: For {a^n b^n}, the PDA pushes one symbol per 'a' and pops one per 'b'. When the b's are exhausted, the stack being empty confirms that |a| = |b| — one counting task, one stack. For {a^n b^n c^n}, after matching a's to b's the stack is empty, and there is no memory left to verify that the number of c's equals n. The stack is a LIFO structure that can track one nested or balanced counting relationship. Matching c's to the original a-count would require a second independent counter, which a single stack cannot provide. This limitation is formalized by the pumping lemma for CFLs: any sufficiently long string in a CFL can be pumped by repeating two substrings simultaneously, but {a^n b^n c^n} requires all three counts to change together — something the two-substring pumping structure cannot achieve.
This is why natural language, which has cross-serial dependencies (a phenomenon called 'crossing dependencies' in Swiss German), cannot be fully modeled by CFGs, motivating mildly context-sensitive grammar formalisms in computational linguistics.