Mario Román

Search

Search IconIcon to open search

Chomsky-Schutzenberger representation theorem

Last updated Feb 3, 2024

Theorem. Every context-free language arises as the intersection of a regular language and a Dyck language under a homomorphism.

chomsky-schutzenberger-theorem

Proof. The constructive proof of the Chomsky-Schutzenberger representation theorem uses the contour of a multicategory and applies it to the multicategory generated by a context-free grammar.

More.