Properties of Context-Free Languages

a^n b^n c^n is not context-free

The language { a^n b^n c^n : n >= 0 } is the famous wall that context-free grammars cannot climb. It is every string that is some number of a's, then the SAME number of b's, then the SAME number of c's: ε, abc, aabbcc, aaabbbccc, and so on. Its two-letter cousin a^n b^n IS context-free (one stack matches a's against b's), so it is tempting to think a third letter is no harder. It is — and the reason is the single stack of a pushdown automaton.

Here is the obstacle in plain words. To accept a^n b^n c^n a PDA would push a marker for each a, then pop one marker per b to confirm the b's match the a's. But by the time the b's are matched, the stack is empty — the memory of n has been spent. There is nothing left to compare the c's against. One stack can lock together exactly ONE pair of equal counts; the third group is unguarded. No amount of cleverness with a single stack gets around this, and the pumping lemma for context-free languages turns this intuition into a rigorous proof.

Its importance is twofold. It is the canonical witness that the context-free class is STRICTLY smaller than the next level up (these three-way counting languages live in the context-sensitive class), and it is the engine behind the non-closure results: intersecting the CFLs a^n b^n c^m and a^m b^n c^n produces exactly a^n b^n c^n, proving CFLs are not closed under intersection. Whenever you see a language demanding three or more independent equal counts, your alarm for 'probably not context-free' should ring.

Members: ε, abc, aabbcc, aaabbbccc. Non-members: ab (counts 1,1,0 unequal), aabbc (a's = b's = 2 but c's = 1), aabbbccc (b's not equal to a's). The defining demand a's = b's = c's is precisely what a single stack cannot enforce.

Three independent equal counts: one stack can lock only one pair, so this language is not context-free.

It is the THREE-way equality that breaks context-freeness; { a^n b^n } with two groups is context-free, and even { a^n b^n c^m } (only the a's and b's must match) is context-free. Adding a third matched group is the killer.

Also called
three-equal-counts language三段相等語言anbncn