Parikh's theorem

Parikh's theorem in theoretical computer science says that if one looks only at the number of occurrences of each terminal symbol in a context-free language, without regard to their order, then the language is indistinguishable from a regular language.[1] It is useful for deciding that strings with a given number of terminals are not accepted by a context-free grammar.[2] It was first proved by Rohit Parikh in 1961[3] and republished in 1966.[4]

Definitions and formal statement

Let Σ = { a 1 , a 2 , … , a k } {\displaystyle \Sigma =\{a_{1},a_{2},\ldots ,a_{k}\}} be an alphabet. The Parikh vector of a word is defined as the function p : Σ ∗ → N k {\textstyle p:\Sigma ^{*}\to \mathbb {N} ^{k}} , given by[1]

p ( w ) = ( | w | a 1 , | w | a 2 , … , | w | a k ) {\displaystyle p(w)=(|w|_{a_{1}},|w|_{a_{2}},\ldots ,|w|_{a_{k}})}
where | w | a i {\displaystyle |w|_{a_{i}}} denotes the number of occurrences of the letter a i {\displaystyle a_{i}} in the word w {\displaystyle w} .

A subset of N k {\displaystyle \mathbb {N} ^{k}} is said to be linear if it is of the form

u 0 + N u 1 + ⋯ + N u m = { u 0 + t 1 u 1 + ⋯ + t m u m ∣ t 1 , … , t m ∈ N } {\displaystyle u_{0}+\mathbb {N} u_{1}+\dots +\mathbb {N} u_{m}=\{u_{0}+t_{1}u_{1}+\dots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}}
for some vectors u 0 , … , u m {\textstyle u_{0},\ldots ,u_{m}} . A subset of N k {\displaystyle \mathbb {N} ^{k}} is said to be semi-linear if it is a union of finitely many linear subsets.

Theorem — Let L {\displaystyle L} be a context-free language or a regular language, let P ( L ) {\displaystyle P(L)} be the set of Parikh vectors of words in L {\displaystyle L} , that is, P ( L ) = { p ( w ) ∣ w ∈ L } {\textstyle P(L)=\{p(w)\mid w\in L\}} . Then P ( L ) {\displaystyle P(L)} is a semi-linear set.

If S {\displaystyle S} is any semi-linear set, then there exists a regular language (which a fortiori is context-free) whose Parikh vectors is S {\displaystyle S} .

In short, the image under p {\displaystyle p} of context-free languages and of regular languages is the same, and it is equal to the set of semilinear sets.

Two languages are said to be commutatively equivalent if they have the same set of Parikh vectors. Thus, every context-free language is commutatively equivalent to some regular language.

Proof

The second part is easy to prove.

Proof

Given semi-linear set S {\displaystyle S} , to construct a regular language whose set of Parikh vectors is S {\displaystyle S} .

S {\displaystyle S} is a union of 0 or more linear sets. Since the empty language is regular, and union of regular languages is regular, it suffices to prove that any linear set is the set of Parikh vectors of a regular language.

Let S = { u 0 + t 1 u 1 + ⋯ + t m u m ∣ t 1 , … , t m ∈ N } {\displaystyle S=\{u_{0}+t_{1}u_{1}+\dots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}} , then it is the set of Parikh vectors of { z 0 } ⋅ ( ∪ i = 1 m { z i } ) ∗ {\displaystyle \{z_{0}\}\cdot (\cup _{i=1}^{m}\{z_{i}\})^{*}} , where each z i {\displaystyle z_{i}} has Parikh vector u i {\displaystyle u_{i}} .

The first part is less easy. The following proof is credited to Goldstine.[5]

First we need a small strengthening of the pumping lemma for context-free languages:

Lemma — If L {\displaystyle L} is generated by a Chomsky normal form grammar, then ∃ N ≥ 1 {\displaystyle \exists N\geq 1} , such that

For any k ≥ 1 {\displaystyle k\geq 1} , and for any w ∈ L {\displaystyle w\in L} with | w | ≥ N k {\displaystyle |w|\geq N^{k}} , there exists a way to split w {\displaystyle w} into segments u x 1 ⋯ x k z y k ⋯ y 1 v {\displaystyle ux_{1}\cdots x_{k}zy_{k}\cdots y_{1}v} , and a nonterminal symbol A {\displaystyle A} , such that

| x i y i | ≥ 1 {\displaystyle |x_{i}y_{i}|\geq 1} for all i {\displaystyle i} , and | x 1 ⋯ x k z y k ⋯ y 1 | ≤ N k {\displaystyle |x_{1}\cdots x_{k}zy_{k}\cdots y_{1}|\leq N^{k}}

S ⇒ ∗ u A v A ⇒ ∗ z ∀ i , A ⇒ ∗ x i A y i {\displaystyle S\Rightarrow ^{*}uAv\quad A\Rightarrow ^{*}z\quad \forall i,A\Rightarrow ^{*}x_{i}Ay_{i}}

The proof is essentially the same as the standard pumping lemma: use the pigeonhole principle to find k {\displaystyle k} copies of some nonterminal symbol A {\displaystyle A} in the longest path in the shortest derivation tree.

Now we prove the first part of Parikh's theorem, making use of the above lemma.

Proof

First, construct a Chomsky normal form grammar for L {\displaystyle L} .

For each finite nonempty subset of nonterminals U {\displaystyle U} , define L U {\displaystyle L_{U}} to be the set of sentences in L {\displaystyle L} such that there exists a derivation that uses every nonterminal in U {\displaystyle U} , no more and no less. It is clear that L = ∪ U L U {\displaystyle L=\cup _{U}L_{U}} , so it suffices to prove that each p ( L U ) {\displaystyle p(L_{U})} is a semilinear set.

Now fix some U {\displaystyle U} , and let k = | U | {\displaystyle k=|U|} . We construct two finite sets F , G {\displaystyle F,G} , such that p ( L U ) = p ( F ⋅ G ∗ ) {\displaystyle p(L_{U})=p(F\cdot G^{*})} , which is obviously semilinear.

For notational clarity, write ⇒ U ∗ {\displaystyle \Rightarrow _{U}^{*}} to mean "there exists a derivation using no more (but possibly less) than nonterminals in U {\displaystyle U} . With that, we define F , G {\displaystyle F,G} as follows:

F = { w ∈ L U : | w | < N k } {\displaystyle F=\{w\in L_{U}:|w|<N^{k}\}}
G = { x y : 1 ≤ | x y | ≤ N k  and there exists  A ∈ U  such that  A ⇒ U ∗ x A y } {\displaystyle G=\{xy:1\leq |xy|\leq N^{k}{\text{ and there exists }}A\in U{\text{ such that }}A\Rightarrow _{U}^{*}xAy\}}

To prove p ( L U ) ⊂ p ( F ⋅ G ∗ ) {\displaystyle p(L_{U})\subset p(F\cdot G^{*})} , we induct on the length of w ∈ L U {\displaystyle w\in L_{U}} .

If | w | < N k {\displaystyle |w|<N^{k}} , then w ∈ F {\displaystyle w\in F} , so p ( w ) ∈ p ( F ⋅ G ∗ ) {\displaystyle p(w)\in p(F\cdot G^{*})} . Otherwise, by the strengthened pumping lemma, there exists a derivation of w {\displaystyle w} using precisely the elements of U {\displaystyle U} , and is of the form

S ⇒ ∗ d 0 u A v ⇒ ∗ d 1 u x 1 A y 1 v ⇒ ∗ d 2 ⋯ ⇒ ∗ d k u x 1 ⋯ x k A y k ⋯ y 1 v ⇒ ∗ d k + 1 u x 1 ⋯ x k z y k ⋯ y 1 v {\displaystyle S{\underset {d_{0}}{\stackrel {*}{\Rightarrow }}}uAv{\underset {d_{1}}{\stackrel {*}{\Rightarrow }}}ux_{1}Ay_{1}v{\underset {d_{2}}{\stackrel {*}{\Rightarrow }}}\cdots {\underset {d_{k}}{\stackrel {*}{\Rightarrow }}}ux_{1}\cdots x_{k}Ay_{k}\cdots y_{1}v{\underset {d_{k+1}}{\stackrel {*}{\Rightarrow }}}ux_{1}\cdots x_{k}zy_{k}\cdots y_{1}v}

where A ∈ U {\displaystyle A\in U} , 1 ≤ | x i y i | {\displaystyle 1\leq |x_{i}y_{i}|} , and | x 1 ⋯ x k z y k ⋯ y 1 | ≤ N k {\displaystyle |x_{1}\cdots x_{k}zy_{k}\cdots y_{1}|\leq N^{k}} .
Since there are only k − 1 {\displaystyle k-1} elements in U ∖ { A } {\displaystyle U\setminus \{A\}} , but there are k {\displaystyle k} sub-derivations d 1 , . . . , d k {\displaystyle d_{1},...,d_{k}} in the middle, we may delete one sub-derivation d i {\displaystyle d_{i}} , and obtain a shorter w ′ {\displaystyle w'} that is still in L U {\displaystyle L_{U}} , with

p ( w ) = p ( u z v ) + p ( x 1 y 1 ) + ⋯ + p ( x k y k ) = p ( w ′ ) + p ( x i y i ) {\displaystyle p(w)=p(uzv)+p(x_{1}y_{1})+\cdots +p(x_{k}y_{k})=p(w')+p(x_{i}y_{i})}

By induction, p ( w ′ ) ∈ p ( F ⋅ G ∗ ) {\displaystyle p(w')\in p(F\cdot G^{*})} , and by construction, x i y i ∈ G {\displaystyle x_{i}y_{i}\in G} , so p ( w ) ∈ p ( F ⋅ G ∗ ) {\displaystyle p(w)\in p(F\cdot G^{*})} .

To prove p ( L U ) ⊃ p ( F ⋅ G ∗ ) {\displaystyle p(L_{U})\supset p(F\cdot G^{*})} , consider an element w ∈ F ⋅ G ∗ {\displaystyle w\in F\cdot G^{*}} . We need to show that p ( w ) ∈ p ( L U ) {\displaystyle p(w)\in p(L_{U})} . We induct on the minimal number of factors from G {\displaystyle G} that is needed to identify w {\displaystyle w} as an element of F ⋅ G ∗ {\displaystyle F\cdot G^{*}} .

If no factor from G {\displaystyle G} is needed, then w ∈ F ⊂ L U {\displaystyle w\in F\subset L_{U}} .
Otherwise, w = w ′ x y {\displaystyle w=w'xy} for some w ′ ∈ F ⋅ G ∗ {\displaystyle w'\in F\cdot G^{*}} and x y ∈ G {\displaystyle xy\in G} , where w ′ {\displaystyle w'} requires less factors from G {\displaystyle G} than w {\displaystyle w} .
By induction, p ( w ′ ) = p ( w ″ ) {\displaystyle p(w')=p(w'')} for some w ″ ∈ L U {\displaystyle w''\in L_{U}} . By construction of G {\displaystyle G} , there exists some A ∈ U {\displaystyle A\in U} such that A ⇒ U ∗ x A y {\displaystyle A\Rightarrow _{U}^{*}xAy} .
By construction of L U {\displaystyle L_{U}} , the symbol A {\displaystyle A} appears in a derivation of w ″ {\displaystyle w''} using exactly all of U {\displaystyle U} . Then we can interpolate A ⇒ U ∗ x A y {\displaystyle A\Rightarrow _{U}^{*}xAy} into that derivation to obtain some w ‴ ∈ L U {\displaystyle w'''\in L_{U}} such that

p ( w ‴ ) = p ( w ″ ) + p ( x y ) = p ( w ′ ) + p ( x y ) = p ( w ) {\displaystyle p(w''')=p(w'')+p(xy)=p(w')+p(xy)=p(w)}

Strengthening for bounded languages

A language L {\displaystyle L} is bounded if L ⊂ w 1 ∗ … w k ∗ {\displaystyle L\subset w_{1}^{*}\ldots w_{k}^{*}} for some fixed words w 1 , … , w k {\displaystyle w_{1},\ldots ,w_{k}} . Ginsburg and Spanier [6] gave a necessary and sufficient condition, similar to Parikh's theorem, for bounded languages.

Call a linear set stratified, if in its definition for each i ≥ 1 {\displaystyle i\geq 1} the vector u i {\displaystyle u_{i}} has the property that it has at most two non-zero coordinates, and for each i , j ≥ 1 {\displaystyle i,j\geq 1} if each of the vectors u i , u j {\displaystyle u_{i},u_{j}} has two non-zero coordinates, i 1 < i 2 {\displaystyle i_{1}<i_{2}} and j 1 < j 2 {\displaystyle j_{1}<j_{2}} , respectively, then their order is not i 1 < j 1 < i 2 < j 2 {\displaystyle i_{1}<j_{1}<i_{2}<j_{2}} . A semi-linear set is stratified if it is a union of finitely many stratified linear subsets.

Ginsburg-Spanier — A bounded language L {\displaystyle L} is context-free if and only if { ( n 1 , … , n k ) ∣ w 1 n 1 … w k n k ∈ L } {\displaystyle \{(n_{1},\ldots ,n_{k})\mid w_{1}^{n_{1}}\ldots w_{k}^{n_{k}}\in L\}} is a stratified semi-linear set.

Significance

The theorem has multiple interpretations. It shows that a context-free language over a singleton alphabet must be a regular language and that some context-free languages can only have ambiguous grammars[further explanation needed]. Such languages are called inherently ambiguous languages. From a formal grammar perspective, this means that some ambiguous context-free grammars cannot be converted to equivalent unambiguous context-free grammars.

References

  1. ^ a b Kozen, Dexter (1997). Automata and Computability. New York: Springer-Verlag. ISBN 3-540-78105-6.
  2. ^ Håkan Lindqvist. "Parikh's theorem" (PDF). Umeå Universitet.
  3. ^ Parikh, Rohit (1961). "Language Generating Devices". Quarterly Progress Report, Research Laboratory of Electronics, MIT.
  4. ^ Parikh, Rohit (1966). "On Context-Free Languages". Journal of the Association for Computing Machinery. 13 (4): 570–581. doi:10.1145/321356.321364. S2CID 12263468.
  5. ^ Goldstine, J. (1977-01-01). "A simplified proof of parikh's theorem". Discrete Mathematics. 19 (3): 235–239. doi:10.1016/0012-365X(77)90103-0. ISSN 0012-365X.
  6. ^ Ginsburg, Seymour; Spanier, Edwin H. (1966). "Presburger formulas, and languages". Pacific Journal of Mathematics. 16 (2): 285–296. doi:10.2140/pjm.1966.16.285.