Parikh's Theorem

We know that every regular language is context-free but a context-free language need not be regular. In 1966, Rohit Parikh showed that if th order of the symbols in a context-free language is ignored, it is impossible to distinguish it from a regular set, thus implying that context-free languages can have a richer structure than those obtained rom regular sets.

Parikh used properties of semi-linear sets and derivation trees and presented some interesting combinatorial arguments to arrive at his result. Although Goldstine came up with a simplified proof 11 years later, Parikh's theorem is still considered remarkable since the exact conditions controlling the structure of the derivation trees that he defined are nontrivial.

In this talk, we will define these terms and use them to prove Parikh's theorem, and time permitting, discuss some of its applications.