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?

  • $\begingroup$ but note the general problem of determining whether a language is CFL is undecidable. $\endgroup$ – vzn Feb 24 '15 at 17:17
  • $\begingroup$ 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. $\endgroup$ – Fizz Feb 24 '15 at 19:50
  • 1
    $\begingroup$ Here's a less banal fact: in 2009 Mans Hulden created a parsing algorithm based on the C-S thorem. $\endgroup$ – Fizz Feb 24 '15 at 21:27

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.


| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Fizz Feb 24 '15 at 21:39

Your Answer

