O que posso dizer sobre o mapa Parikh de uma CSL?

Escreva como o mapa de Parikh --ie, , onde é o número de vezes que aparece em . É sabido que, para um CFL , é um conjunto semilinear (esse é o teorema de Parikh). Outras coisas interessantes são conhecidas, mas não encontrei nada sobre o mapa de Parikh de uma linguagem sensível ao contexto. Em particular, $\Psi$ $\Psi(w) = \{(\#_\sigma(w))_{\sigma\in \Sigma}\vert w\in L\}$ $\#_\sigma(w)$ $\sigma$ $w$ $L$ $\Psi(L)$

o que posso dizer sobre ou se forem livres de contexto? Por exemplo, se eu deixar , é possível que exista uma CFL tal que ? (ou qualquer outra sequência 'crescente' convergindo para , nesse 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
fonte

@alpoge: Você se importaria de explicar as anotações que usou? Por exemplo, o que é

#_{σ} (w)

$\#_\sigma(w)$ ? E talvez alguns links para termos como "teorema de Parikh" também ajudem.

Hsien-Chih Chang

#_{σ} (w)

$\#_\sigma(w)$ é o número de vezes que

σ

$\sigma$ aparece como uma letra em

w

$w$ .

Michaël Cadilhac

FWIW, a segunda parte deve ser falsa, pois as CFLs são fechadas sob morfismos e

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

$\{1^{n!} \;|\; n \in N\}$ não é CF.

Michaël Cadilhac

Espere - eu provavelmente deveria ter escolhido uma letra melhor, mas essa é a imagem de um coCFL, . (Eu acho que provavelmente estou faltando alguma coisa embora.)

\bar{L}

$\bar{L}$

alpoge

Ah, desculpe, a fonte matemática é lixo no meu computador e eu não vi o complemento.

Michaël Cadilhac

Respostas:

Em relação à segunda parte da sua pergunta: Se você escolher sua CFL como o conjunto de todos os cálculos inválidos de uma máquina de Turing (consulte, por exemplo, o capítulo 8.6 da primeira edição de "Introdução à teoria, linguagens e computação de autômatos"). ), é o conjunto de todos os comprimentos de codificações de aceitar computações de . $L$ $M$ $\phi(\overline{L})$ $M$

Embora isso não responda diretamente à sua pergunta, você pode usar essa abordagem para construir conjuntos bastante complicados.

Dominik D. Freydenberger
fonte

Sim! - Eu estava pensando sobre isso também. Na verdade, acho que pode ser aqui que surge um contra-exemplo do que estou tentando provar, mas ainda não pensei o suficiente sobre isso (infelizmente!).

alpoge