Mario Román

Home

❯

notes

❯

pieces

❯

Chomsky Schutzenberger representation theorem

Chomsky-Schutzenberger representation theorem

Apr 29, 20251 min read

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.

  • examples of the Chomsky-Schutzenberger representation theorem
  • contour rule translation

Graph View

Backlinks

  • constructive proof of the Chomsky-Schutzenberger representation theorem
  • contour rule translation
  • monoidal Chomsky-Schutzenberger representation theorem

Mario Román, CC-BY-SA. Built with Quartz © 2025.

  • GitHub
  • ArXiv
  • OrcID