Math 2.0

Computer science Automata and formal languages Theorem

Parikh's theorem

Builds on Context-free languageRegular languagePresburger arithmetic

Statement

Let Σ={a1,…,ak}\Sigma = \set{a_1, \dots, a_k} be a finite alphabet. The Parikh map ψ ⁣:Σ∗→ℕk\psi \colon \Sigma^* \to \N^k sends a word ww to (∣w∣a1,…,∣w∣ak)(\abs{w}_{a_1}, \dots, \abs{w}_{a_k}), where ∣w∣a\abs{w}_{a} is the number of occurrences of aa in ww. A set M⊆ℕkM \subseteq \N^k is linear if M={v0+n1v1+⋯+nmvm:n1,…,nm∈ℕ}M = \set{v_0 + n_1 v_1 + \cdots + n_m v_m : n_1, \dots, n_m \in \N} for some v0,…,vm∈ℕkv_0, \dots, v_m \in \N^k, and semilinear if it is a finite union of linear sets. Let L⊆Σ∗L \subseteq \Sigma^* be a context-free language. Then:

  1. the set ψ(L)\psi(L) is semilinear;
  2. there is a regular language R⊆Σ∗R \subseteq \Sigma^* with ψ(R)=ψ(L)\psi(R) = \psi(L).

Remarks

The two parts are equivalent, because the Parikh images of regular languages are exactly the semilinear sets. The proof decomposes parse trees. Each tree is built from a bounded tree by inserting pumping pieces, as in the pumping lemma, and each pumping piece adds a vector from a finite set. Example: L={anbn:n≥0}L = \set{a^n b^n : n \ge 0} has ψ(L)={(n,n):n∈ℕ}\psi(L) = \set{(n, n) : n \in \N}, a linear set with v0=(0,0)v_0 = (0,0) and v1=(1,1)v_1 = (1,1), and the regular language (ab)∗(ab)^* has the same image. A consequence is that every context-free language over a one-letter alphabet is regular. The theorem does not say that LL itself is regular: {anbn}\set{a^n b^n} is not.

Going deeper

For a student

Parikh's theorem is a tool to show that a language is not context-free: if its letter counts do not form a semilinear set, it is not. For example, {an2:n≥0}\set{a^{n^2} : n \ge 0} is not context-free, since {n2}\set{n^2} is not a finite union of arithmetic progressions. The semilinear sets are exactly the subsets of ℕk\N^k definable in Presburger arithmetic, which links the theorem to logic. It is also used in the verification of systems with counters.

Reading path

To understand this page from the ground up, read these 9 pages in order. The foundations come first.

Show the path as a graph
Complete theory, concept, no evidence levelComplete theoryconceptCongruence modulo n, concept, no evidence levelCongruence modulo nconceptContext-free language, concept, no evidence levelContext-free languageconceptIntegers, object, no evidence levelIntegersobjectNatural numbers, object, no evidence levelNatural numbersobjectPeano axioms, concept, no evidence levelPeano axiomsconceptRegular language, concept, no evidence levelRegular languageconceptPresburger arithmetic, example, no evidence levelPresburger arithmeticexampleParikh's theorem, statement, no evidence levelParikh's theoremstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Complete theory concept
  2. Congruence modulo n concept
  3. Context-free language concept
  4. Integers object
  5. Natural numbers object
  6. Peano axioms concept
  7. Regular language concept
  8. Presburger arithmetic example
  9. Parikh's theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Parikh's_theorem
About this page
Tag7DSXBWD96M
URIm2://7DSXBWD96M
Kindstatement, theorem
WritingW0 stub
MSC68Q45, 68R15
StatusThis copy of the site has no build data. Run m2 status 7DSXBWD96M.
AboutContext-free language
UsesContext-free language, Regular language, Presburger arithmetic
Same as
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.