---
title: "The Algebraic Theory of Context-Free Languages"
authors:
  - "Noam Chomsky"
  - "Marcel-Paul Schützenberger"
year: 1963
venue: "Computer Programming and Formal Systems (Studies in Logic and the Foundations of Mathematics 35)"
arxiv: null
doi: "10.1016/S0049-237X(08)72023-8"
source: "https://doi.org/10.1016/S0049-237X(08)72023-8"
topics:
  - context-free
  - algebraic-language-theory
  - chomsky
seed_rank: 602
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "languages"
relevance_score: 8
lineage: foundations-of-computing
cites:
  - title: "On Certain Formal Properties of Grammars"
    url: "https://doi.org/10.1016/S0019-9958(59)90362-6"
    year: 1959
    arxiv: null
    doi: "10.1016/S0019-9958(59)90362-6"
  - title: "Three Models for the Description of Language"
    url: "https://doi.org/10.1109/TIT.1956.1056813"
    year: 1956
    arxiv: null
    doi: "10.1109/TIT.1956.1056813"
  - title: "Representation of Events in Nerve Nets and Finite Automata"
    url: "https://www.cs.cmu.edu/~cdm/resources/Kleene1951.pdf"
    year: 1956
    arxiv: null
    doi: null
see:
  - "601-on-certain-formal-properties-of-grammars"
  - "599-three-models-for-the-description-of-language"
  - "530-representation-of-events-in-nerve-nets-and-finite-automata"
---

# The Algebraic Theory of Context-Free Languages

## One-sentence takeaway

Chomsky and Schützenberger recast context-free languages as supports of algebraic formal power series, so CFL structure becomes a theorem about noncommutative generating functions.

## Why it matters here

This is the algebraic reason a CFG has a generating function and why Dyck/ palindrome-style nesting is the canonical hard core of parsing — the same nesting ano's surface syntax and GRID COMMAND command grammars have to decide how to accept.

## Key ideas

- Formal power series with noncommuting variables encode word counts; CFLs are the supports of algebraic series.
- The Chomsky–Schützenberger representation theorem: every CFL is a homomorphic image of the intersection of a Dyck language with a regular language.
- Pushdown / parenthesis structure is isolated as the combinatorial essence of context-freeness.
- Kleene's regular events sit inside the algebraic hierarchy as the rational series.
- The paper is the North-Holland chapter (Braffort–Hirschberg, *Computer Programming and Formal Systems*, 1963), pp. 118–161.

## Caveats

## Links

- DOI: [10.1016/S0049-237X(08)72023-8](https://doi.org/10.1016/S0049-237X(08)72023-8)
- ScienceDirect chapter: https://www.sciencedirect.com/science/article/pii/S0049237X08720238