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

6

1

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?

templatetypedef

Posted 2014-09-18T00:45:01.303

Reputation: 8 298

but note the general problem of determining whether a language is CFL is undecidable.

– vzn – 2015-02-24T17:17:56.223

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 – 2015-02-24T19:50:05.883

1

Here's a less banal fact: in 2009 Mans Hulden created a parsing algorithm based on the C-S thorem.

– Fizz – 2015-02-24T21:27:45.940

Answers

-2

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

vzn

Posted 2014-09-18T00:45:01.303

Reputation: 10 652

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 – 2015-02-24T21:39:43.350

Asked: 2014-09-18T00:45:01.303

Viewed: 524 times

Active: 2015-02-24T21:26:00.053