8
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ @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. $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 20 '11 at 16:27
  • $\begingroup$ $\#_\sigma(w)$ is the number of times $\sigma$ appears as a letter in $w$. $\endgroup$ – Michaël Cadilhac Jan 20 '11 at 16:59
  • 1
    $\begingroup$ FWIW, the second part should be false, as CFLs are closed under morphisms and $\{1^{n!} \;|\; n \in N\}$ is not CF. $\endgroup$ – Michaël Cadilhac Jan 20 '11 at 17:15
  • $\begingroup$ 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.) $\endgroup$ – alpoge Jan 20 '11 at 19:46
  • $\begingroup$ Oh, sorry, the math font is rubbish on my computer, and I didn't see the complementing. $\endgroup$ – Michaël Cadilhac Jan 20 '11 at 20:19
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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!). $\endgroup$ – alpoge Jan 21 '11 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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