en>BG19bot: WP:CHECKWIKI error fix. Section heading problem. Violates WP:MOSHEAD.

2014-02-01T05:35:02Z

WP:CHECKWIKI error fix. Section heading problem. Violates WP:MOSHEAD.

New page

'''Parikh's theorem''' in [[theoretical computer science]] says that if we look only at the relative number of occurrences of [[Context-free grammar#Formal_definitions|terminal symbols]] in a [[context-free language]], without regard to their order, then the language is indistinguishable from a [[regular language]].<ref name="kozen">{{cite book |title=Automata and Computability|last=Kozen |first=Dexter|year=1997 |publisher=Springer-Verlag|location=New York|isbn=3-540-78105-6}}</ref> It is useful for deciding whether or not a string with given number of some terminals is accepted by a context-free grammar.<ref>{{cite web|url=http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf|title=Parikh's theorem|author=Håkan Lindqvist|publisher=Umeå Universitet}}</ref> It was first proved by [[Rohit Jivanlal Parikh|Rohit Parikh]] in 1961<ref>{{cite journal |last1=Parikh |first1=Rohit|authorlink=Rohit Jivanlal Parikh|year=1961 |title=Language Generating Devices|journal=Quartly Progress Report, Research Laboratory of Electronics, MIT}}</ref> and republished in 1966.<ref>{{cite journal |last1=Parikh |first1=Rohit|authorlink=Rohit Jivanlal Parikh|year=1966 |title=On Context-Free Languages|journal=Journal of the [[Association for Computing Machinery]]|volume=13|issue=4|url=http://portal.acm.org/citation.cfm?id=321364&dl=}}</ref>

==Definitions and Formal Statement==
Let <math>\Sigma=\{a_1,a_2,\ldots,a_k\}</math> be an [[alphabet]]. The ''Parikh vector'' of a word is defined as the function <math>p:\Sigma^*\to\mathbb{N}^k</math>, given by<ref name="kozen"/>

<math>p(w)=(|w|_{a_1}, |w|_{a_2}, \ldots, |w|_{a_k})</math>, where <math>|w|_{a_i}</math> denotes the number of occurrences of the letter <math>a_i</math> in the word <math>w</math>.

A subset of <math>\mathbb{N}^k</math> is said to be ''linear'' if it is of the form

<math>u_0+\langle u_1,\ldots,u_m\rangle=\{u_0+t_1u_1+\ldots+t_mu_m \mid t_1,\ldots,t_m\in\mathbb{N}\}</math> for some vectors <math>u_0,\ldots,u_m</math>.

A subset of <math>\mathbb{N}^k</math> is said to be ''semi-linear'' if it is a union of finitely many linear subsets.

The formal statement of Parikh's Theorem is as follows. Let <math>L</math> be a context-free language. Let <math>P(L)</math> be the set of Parikh vectors of words
in <math>L</math>, that is, <math>P(L) = \{p(w) \mid w \in L\}</math>. Then <math>P(L)</math> is a semi-linear set.

If <math>S</math> is any semi-linear set, the language of words whose Parikh vectors are in <math>S</math> is a regular language. Thus, if we
consider two languages to be ''commutatively equivalent'' if they have the same set of Parikh vectors, every context-free language is commutatively equivalent to some regular language.

==Significance==

Parikh's theorem proves that some context-free languages can only have [[ambiguous grammar]]s. Such languages are called ''[[inherently ambiguous language]]s''. From a [[formal grammar]] perspective this means that some ambiguous [[context-free grammar]]s cannot be converted to an equivalent unambiguous context-free grammar.

==References==
<references/>

[[Category:Formal languages]]

Membrane - Revision history

en>BG19bot: WP:CHECKWIKI error fix. Section heading problem. Violates WP:MOSHEAD.