¿Qué puedo decir sobre el mapa Parikh de un CSL?

Escriba como el mapa Parikh --es decir, , donde es el número de veces que aparece en . Es bien sabido que, para un CFL , es un conjunto semilineal (este es el teorema de Parikh). Se conocen otras cosas interesantes, pero no he encontrado nada sobre el mapa Parikh de un lenguaje sensible al contexto. En particular, $\Psi$ $\Psi(w) = \{(\#_\sigma(w))_{\sigma\in \Sigma}\vert w\in L\}$ $\#_\sigma(w)$ $\sigma$ $w$ $L$ $\Psi(L)$

¿Qué puedo decir sobre o si tienen contexto? Por ejemplo, si dejo , ¿es posible que haya una CFL tal que ? (o cualquier otra secuencia 'creciente' que converja en , para el caso). $\Psi(L_2 - L_1)$ $\Psi(\bar{L}_1)$ $L_1, L_2$ $\phi(L) = \{\sum_\sigma \#_\sigma(w)\vert w\in L\} = \{|w| \vert w\in L\}$ $L$ $\phi(\bar{L}) = \{n!\vert n\in \mathbb{N}\}$ $\hat{\mathbb{Z}}$

fl.formal-languages automata-theory alpoge
fuente

@alpoge: ¿Te importaría explicar las anotaciones que usaste? Por ejemplo, ¿qué es ? Y tal vez algunos enlaces a los términos como "Teorema de Parikh" también ayuden.

#_{σ} (w)

$\#_\sigma(w)$

Hsien-Chih Chang 張顯之

#_{σ} (w)

$\#_\sigma(w)$ es el número de veces que aparece como una letra en .

σ

$\sigma$

w

$w$

Michaël Cadilhac

FWIW, la segunda parte debe ser falsa, ya que las CFL están cerradas bajo morfismos y no es CF.

{1^{n!} | n \in N}

$\{1^{n!} \;|\; n \in N\}$

Michaël Cadilhac

Espere: probablemente debería haber elegido una mejor letra, pero esa es la imagen de un coCFL, . (Creo que probablemente me estoy perdiendo algo.)

\bar{L}

$\bar{L}$

Alpoge

Oh, lo siento, la fuente matemática es basura en mi computadora, y no vi el complemento.

Michaël Cadilhac

Respuestas:

Con respecto a la segunda parte de su pregunta: si elige que su CFL sea el conjunto de todos los cálculos no válidos de una máquina Turing (consulte, por ejemplo, el Capítulo 8.6 en la primera edición de "Introducción a la teoría, los idiomas y la computación de los autómatas" ), es el conjunto de todas las longitudes de codificaciones de la aceptación de los cálculos de . $L$ $M$ $\phi(\overline{L})$ $M$

Aunque esto no responde directamente a su pregunta, puede utilizar este enfoque para construir conjuntos bastante complicados.

Dominik D. Freydenberger
fuente

Sí! - Estaba pensando en eso también. De hecho, creo que puede ser donde surge un contraejemplo de lo que estoy tratando de demostrar, pero no he pensado lo suficiente (¡desafortunadamente!).

alpoge