# Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?

The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}$ such that $L = h(D_\Sigma \cap R)$, where $D_\Sigma$ is the Dyck language over $\Sigma$. This is a necessary and sufficient condition for a language to be context-free, so in principle it seems like it should be possible to show that a language is not context-free by showing that there are no valid choices for $h$, $\Sigma$, and $R$ satisfying the theorem.

This earlier question talks about approaches for showing that a language is not context-free, but doesn't mention this approach. Additionally, I can't seem to find any constructive examples of proofs of non-context-freeness along these lines.

Are there any known examples of languages that have been shown not to be context-free by means of the Chomsky-Schutzenberger theorem?

• but note the general problem of determining whether a language is CFL is undecidable.
– vzn
Feb 24, 2015 at 17:17
• I guess I'm saying a banality here, but in practice the pumping lemma (for CF languages) is infinitely easier to use as a proof technique at least for textbook-level problems.
– Fizz
Feb 24, 2015 at 19:50
• Here's a less banal fact: in 2009 Mans Hulden created a parsing algorithm based on the C-S thorem.
– Fizz
Feb 24, 2015 at 21:27

## 1 Answer

here is a construction not exactly as requested but related/ somewhat similar. the contrapositive of the Chomsky-Schutzenberger theorem can be used to prove a language is not unambiguously CFL. it describes the close connection of the construction to generating functions that yields key insight into the problem.

see ORDINARY GENERATING FUNCTIONS OF CONTEXT-FREE GRAMMARS / TANNER SWETT, EDWARD ABOUFADEL, sec 2.6 p 6

• It think you're confusing this representation theorem of C&S with the homonymous enumeration theorem for unambiguous CFLs. It's the latter that's used in the paper you cited for the purpose you cited.
– Fizz
Feb 24, 2015 at 21:39