# What can I say about the Parikh map of a CSL?

Write $\Psi$ as the Parikh map--i.e., $\Psi(w) = \{(\#_\sigma(w))_{\sigma\in \Sigma}\vert w\in L\}$, where $\#_\sigma(w)$ is the number of times $\sigma$ appears in $w$. It's well-known that, for a CFL $L$, $\Psi(L)$ is a semilinear set (this is Parikh's theorem). Some other interesting things are known, but I have found nothing about the Parikh map of a context-sensitive language. In particular,

what can I say about $\Psi(L_2 - L_1)$ or $\Psi(\bar{L}_1)$ if $L_1, L_2$ are context-free? For instance, if I let $\phi(L) = \{\sum_\sigma \#_\sigma(w)\vert w\in L\} = \{|w| \vert w\in L\}$, is it possible that there is a CFL $L$ such that $\phi(\bar{L}) = \{n!\vert n\in \mathbb{N}\}$? (or any other 'increasing' sequence converging in $\hat{\mathbb{Z}}$, for that matter.)

• @alpoge: Would you mind to explain the notations you used? For example, what is $\#_\sigma(w)$? And maybe some links to the terms like "Parikh's theorem" will help, too. – Hsien-Chih Chang 張顯之 Jan 20 '11 at 16:27
• $\#_\sigma(w)$ is the number of times $\sigma$ appears as a letter in $w$. – Michaël Cadilhac Jan 20 '11 at 16:59
• FWIW, the second part should be false, as CFLs are closed under morphisms and $\{1^{n!} \;|\; n \in N\}$ is not CF. – Michaël Cadilhac Jan 20 '11 at 17:15
• Wait--I should probably have chosen a better letter, but that's the image of a coCFL, $\bar{L}$. (I think I'm probably missing something though.) – alpoge Jan 20 '11 at 19:46
• Oh, sorry, the math font is rubbish on my computer, and I didn't see the complementing. – Michaël Cadilhac Jan 20 '11 at 20:19

## 1 Answer

Regarding the second part of your question: If you choose your CFL $L$ to be the set of all invalid computations of a Turing machine $M$ (see, e.g., Chapter 8.6 in the first edition of "Introduction to Automata Theory, Languages, and Computation"), $\phi(\overline{L})$ is the set of all lengths of encodings of accepting computations of $M$.

Although this does not directly answer your question, you can use this approach to construct quite complicated sets.

• Yep!--I was thinking about that as well. I actually think this may be where a counterexample to what I'm trying to prove arises, but I haven't quite thought enough about it (unfortunately!). – alpoge Jan 21 '11 at 16:38