Which of the following languages requires a context-free grammar and cannot be described by any regular expression?
A{ aⁿ | n ≥ 0 }
B{ aⁿbⁿ | n ≥ 0 }
C{ strings over {a,b} containing at least one a }
D{ ab, ba }
{ aⁿbⁿ } requires counting equal numbers of a's and b's — a form of memory that finite automata cannot provide. The pumping lemma for regular languages proves no DFA can recognize it. The other options are all regular: any finite language or simple pattern is describable by a regex. CFGs handle { aⁿbⁿ } via the rule S → aSb | ε.
Question 2 True / False
If two different context-free grammars both generate the same string w, then w is ambiguous.
TTrue
FFalse
Answer: False
Ambiguity is a property of a single grammar with respect to a single string: a string is ambiguous in grammar G if G produces more than one distinct parse tree for it. Having two different grammars that each generate the same string says nothing about ambiguity. In fact, many different grammars generate the same language — and a language is only inherently ambiguous if every grammar for it is ambiguous.
Question 3 Short Answer
What is the difference between a context-free grammar and the context-free language it defines?
Think about your answer, then reveal below.
Model answer: A grammar is a finite set of production rules; the language is the (potentially infinite) set of all terminal strings derivable from the start symbol by applying those rules. Multiple different grammars can define the same language.
This distinction is crucial for understanding equivalence and ambiguity. Algorithms like CYK parse strings relative to a grammar, not a language. When we say a language is context-free, we mean there exists at least one CFG that generates exactly that set of strings.