[Solved]: Parikh's Theorem: CFL's "contain" regular languages?

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^n\mid n\ge 0 \}) = \{(n,n,n)\mid n\ge 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^n\mid n\ge 0 \}) = \Psi( (abc)^*) $.

(In a previous edit I had the example $\Psi( \{a^nb^nc^n\mid n\ge 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