7
$\begingroup$

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?

$\endgroup$

2 Answers 2

12
$\begingroup$

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.)

$\endgroup$
5
$\begingroup$

I agree the wording on Wikipedia isn't very clear, but I believe it refers to the following relationship:

Call two words letter equivalent iff they are equal when disregarding the order of the characters. That is to say: lexicographically sorting their characters (preserving duplicates) produces the same word. (In other words: their Parikh images are the same.)

Call two languages letter equivalent iff their words are, that is to say: lexicographically sorting their words produces the same language. (In other words: their Parikh images are the same.)

The theorem implies that every context-free language is letter equivalent to a regular language. For instance, $\{ a^nb^n \mid n \geq 0\}$ is letter equivalent to $(ab)^*$.

(The notion letter equivalent can be found in e.g. A simplified proof of Parikh's theorem, by J. Goldstine (1977).)

$\endgroup$
5
  • $\begingroup$ It would be even better if you can add a reference to your answer. $\endgroup$
    – John L.
    Oct 29, 2018 at 18:00
  • $\begingroup$ By the way, I believe your addition of "(preserving duplicates)" add more confusion than clarification, because preserving duplicates is universally the norm. No sorting implies removing duplicates unless explicitly required. In short, default behavior should not be mentioned explicitly (except in exceptional cases). Just my 2 cents. I am nitpicking since this is small matter here anyway (what I am concerned is, of course, if you apply your habit everywhere) and since it does not really change anything here anyway. $\endgroup$
    – John L.
    Oct 29, 2018 at 18:05
  • $\begingroup$ I'm wondering about that, too; but their characters is ambiguous, one might take it to mean: each different character that occurs. $\endgroup$ Oct 29, 2018 at 18:07
  • $\begingroup$ OK, I see your concern. Reasonable. $\endgroup$
    – John L.
    Oct 29, 2018 at 18:08
  • 1
    $\begingroup$ I've added the reference, but it bloats the answer. I didn't want to duplicate Hendrik Jan's answer. $\endgroup$ Oct 29, 2018 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.