6
$\begingroup$

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?

$\endgroup$
  • $\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$ – SX welcomes ageist gossip 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$ – SX welcomes ageist gossip Feb 24 '15 at 21:27
-2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.