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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.