[Solved]: Parikh’s Theorem: CFL’s “contain” regular languages?

ignougroup
Problem Detail: The first sentence of the Wikipedia article for Parikh’s Theorem states:

“Parikh’s theorem in theoretical computer science says that if one looks only at the relative number of occurrences of terminal symbols in a context-free language, without regard to their order, then the language is indistinguishable from a regular language.”

I’m having some trouble understanding this sentence. I understand that unary CFL’s can be described as the union of finitely many arithmetic sequences. Does this mean that if we apply a morphism $h$ to some CFL $L$ which, say, maps $a longrightarrow a$ and $c longrightarrow epsilon$ for some $a in Sigma$ and for all $c in Sigma$ with $c neq a$, then $h(L)$ is a unary regular language? Could someone elaborate on this?

Asked By : David Smith

Answered By : Hendrik Jan

The Parikh image $Psi$ of a word is a vector counting the number of each of the letters in the alphabet: for example $Psi( abbabaaca ) = (5,3,1)$ assuming the alphabet is ${a,b,c}$. The Parikh image of a language is the set of Parikh images of the strings in the language: $Psi( {a^nb^nc^nmid nge 0 }) = {(n,n,n)mid nge 0 }$. The theorem states that the Parikh images of context-free languages are in fact Parikh images of regular languages, as example $Psi( {( ab)^n c^nmid nge 0 }) = Psi( (abc)^*) $. (In a previous edit I had the example $Psi( {a^nb^nc^nmid nge 0 }) = Psi( (abc)^*) $. Technically correct, but the reader will note that language is not context-free.)
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/34002