<p>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$.</p>

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

CC BY-SA 2.5
2011-01-21T16:38:40.760Z
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
CC BY-SA 2.5
2011-01-21T12:34:14.770Z
2011-01-21T12:34:14.770Z
Dominik D. Freydenberger
<p>Write $\Psi$ as the <a href="http://www.csd.uwo.ca/courses/CS9620b/parikh.pdf" rel="nofollow">Parikh map</a>--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, </p>

<blockquote>
  <p>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.)</p>
</blockquote>

CC BY-SA 2.5
2011-01-20T16:27:04.473Z
@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 張顯之
CC BY-SA 2.5
2011-01-20T16:59:36.827Z
$\#_\sigma(w)$ is the number of times $\sigma$ appears as a letter in $w$.
Michaël Cadilhac
CC BY-SA 2.5
2011-01-20T17:15:04.633Z
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
CC BY-SA 2.5
2011-01-20T19:46:32.593Z
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
CC BY-SA 2.5
2011-01-20T20:19:50.917Z
Oh, sorry, the math font is rubbish on my computer, and I didn't see the complementing.
Michaël Cadilhac
CC BY-SA 2.5
2011-01-20T22:04:48.103Z
But as every CFL over a unary alphabet is regular (and, hence, every coCFL over a unary alphabet), that's not a problem.
Dominik D. Freydenberger
CC BY-SA 2.5
2011-01-20T22:23:30.683Z
Sure--in that case, anyway, $L_2 - L_1$ would be regular anyway, so $\Psi(L_2 - L_1)$ would be semilinear, which indeed gives the contradiction. However, if we're working with $|\Sigma|\geq 2$, I don't see why the homomorphism taking everything to $1$ should take coCFLs to coCFLs.
alpoge
CC BY-SA 2.5
2011-01-21T12:17:40.347Z
Of course, you are right. My mistake.
Dominik D. Freydenberger
<fl.formal-languages><automata-theory>
What can I say about the Parikh map of a CSL?
alpoge
# What can I say about the Parikh map of a CSL?

(Asked by: username_0 on 2011-01-20)

Write $\Psi$ as the [Parikh map](http://www.csd.uwo.ca/courses/CS9620b/parikh.pdf)--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.)

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: @username_0: 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.  
> **username_2**: $\#_\sigma(w)$ is the number of times $\sigma$ appears as a letter in $w$.  
> **username_2**: FWIW, the second part should be false, as CFLs are closed under morphisms and $\{1^{n!} \;|\; n \in N\}$ is not CF.  
> **username_0**: 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.)  
> **username_2**: Oh, sorry, the math font is rubbish on my computer, and I didn't see the complementing.  
> **username_3**: But as every CFL over a unary alphabet is regular (and, hence, every coCFL over a unary alphabet), that's not a problem.  
> **username_0**: Sure--in that case, anyway, $L_2 - L_1$ would be regular anyway, so $\Psi(L_2 - L_1)$ would be semilinear, which indeed gives the contradiction. However, if we're working with $|\Sigma|\geq 2$, I don't see why the homomorphism taking everything to $1$ should take coCFLs to coCFLs.  
> **username_3**: Of course, you are right. My mistake.  

---

## 1 answers

### Answer by username_3 on 2011-01-21. Score: 3

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.

> **Comments:**
> **username_0**: 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!).  

---

