7
$\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?

Improve this question
$\endgroup$
3
  • $\begingroup$ but note the general problem of determining whether a language is CFL is undecidable. $\endgroup$
    – vzn
    Commented Feb 24, 2015 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$
    – got trolled too much this week
    Commented Feb 24, 2015 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$
    – got trolled too much this week
    Commented Feb 24, 2015 at 21:27

1 Answer 1

Reset to default
-3
$\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

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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