is called the Parikh mapping (over the alphabet ). Here, is the set of non-negative integers.
Two languages and over some are called letter-equivalent if .
Theorem 1 (Parikh).
Every context-free language is letter-equivalent to a regular language.
Like the pumping lemma, Parikh’s theorem can be used to show that certain languages are not context-free. But in order to apply Parikh’s theorem above, one needs to know more about the structure of the set for a given context-free language .
the submonoid generated by .
A subset of is said to be linear if it has the form
for some . It is not hard to see that every linear set is the image of some regular language under . For example,
The example can be easily generalized.
A subset of is said to be semilinear if it is the union of finitely many linear sets. Since regular languages are closed under union, every semilinear set is the image of a regular language under . As a result, Parikh’s theorem can be restated as
Theorem 2 (Theorem 1 restated).
If is context-free, then is semilinear.
Using this theorem, one easily sees that the language is not context-free, and neither is the language
which can not be proved by the pumping lemma in a straightforward manner.
The converse of Theorem 2 above is false. For example, let . Then is not context-free by the pumping lemma. However, , which is clearly linear.
In the literature, a lanugage such that is semilinear is often called a slip-language. It can be shown that for a slip-language over an alphabet consisting of two symbols, the language is context-free.
- 1 H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
- 2 D. C. Kozen, Automata and Computability, Springer, New York (1997).
- 3 R.J. Parikh, On Context-Free Languages, Journal of the Association for Computing Machinery, 4 (1966), 570-581.
- 4 M. Latteux, Cônes rationnels commutatifs, J. Comput. Systems Sci. 18 (1979), 307-333.
|Date of creation||2013-03-22 18:55:49|
|Last modified on||2013-03-22 18:55:49|
|Last modified by||CWoo (3771)|