Comprovando o fechamento com reversão de idiomas aceitos pelos autômatos de min-heap

16

Esta é uma questão de acompanhamento deste .

Em uma pergunta anterior sobre máquinas de estado exóticas , Alex ten Brink e Raphael abordaram os recursos computacionais de um tipo peculiar de máquina de estado: autômatos de min-heap. Eles foram capazes de mostrar que o conjunto de idiomas aceitos por essas máquinas ( ) não é um subconjunto nem um superconjunto do conjunto de idiomas sem contexto. Dada a resolução bem-sucedida e o aparente interesse por essa pergunta, faço várias perguntas de acompanhamento.HAL

Sabe-se que os idiomas regulares são fechados sob uma variedade de operações (podemos nos limitar a operações básicas como união, interseção, complemento, diferença, concatenação, estrela Kleene e reversão), enquanto as linguagens sem contexto têm fechamento diferente propriedades (fechadas sob união, concatenação, estrela Kleene e reversão).

O HAL está fechado sob reversão?

Patrick87
fonte
Quais são os usos dessas máquinas? Ou isso é um exercício acadêmico?
21812 Dave Clarke
@DaveClark Bem, eles são principalmente um exercício acadêmico (tanto quanto eu sei, acabei de inventar na questão vinculada). No entanto, eles podem fazer cálculos da mesma maneira que outras máquinas (DFAs, TMs etc.), portanto, talvez possa haver um uso para eles.
Patrick87
Esta pergunta ilustra por que você deseja que as gramáticas acompanhem seus autômatos. Arr, meu cérebro!
Raphael
4
Eu estava tentando provar isso usando uma linguagem do formato , mas levou muito tempo e eu desisti. Talvez essa idéia ajude alguém. {xyy is a lexicographically sorted copy of x}
Ran G.
@RanG .: Eu acho que isso deve funcionar. Fico feliz em conceder a recompensa a uma resposta que prove que o idioma está em e dê um raciocínio decente de que a reversão não está. HAL
Raphael

Respostas:

4

Considere o idioma (onde # 0 ( x ) indica o número de zeros em x ).

L×2={xyzx,y,z{0,1},#0(x)=#0(y) and |x|+|y|=z}
#0(x)x

É fácil decidir usando uma máquina HAL - observe que a máquina precisa acompanhar duas propriedades: o número de zeros em x vs y e o comprimento de x , y (vs z ). Ele pode inserir um na pilha para cada zero que vê em x (e depois aparecer para qualquer zero visto em y ); além disso, pressiona qualquer bit em x , y (e depois aparece para qualquer bit de z ). Como todos os s são empurrados para baixo, eles não interferem na contagem. O L×2xyx,yz0x0y1x,y1z10 serve como delimitador e pode ser praticamente ignorado.

Agora, vamos , ser a língua inversa. Isto é, L = { z y x | x , y , z { 0 , 1 } , # 0 ( x ) = # 0 ( y )  e  | x | + | y | = Z } Vamos mostrar que nenhuma máquina HAL pode decidir L .L=L×2R

L={zyxx,y,z{0,1},#0(x)=#0(y) and |x|+|y|=z}
L

A intuição é o seguinte. Como acima, a máquina deve acompanhar o comprimento de e o número de zeros em x , y . No entanto, neste caso, ele precisa rastreá-los simultaneamente . Isso não pode ser feito através de um heap. Em mais detalhes, depois de ler z , o heap contém informações sobre o comprimento de | x | + | y | . enquanto lê y, a máquina também deve manter na pilha o número de zeros em y . No entanto, essas informações não podem interferir nas informações que o heap já possui sobre o tamanho que esperamos xzx,yz|x|+|y|yyxser estar. Muito intuitivamente, ou as informações sobre o número de zeros estarão "abaixo" das informações sobre o comprimento de , e não poderemos acessá-las durante a leitura de x , ou estarão "acima" dessas informações, tornando o último inacessível ou o duas informações serão "misturadas" e se tornarão sem sentido.xx

Mais formalmente, vamos usar algum tipo de argumento de "bombeamento". Ou seja, pegaremos uma entrada muito longa e mostraremos que o "estado" da máquina deve se repetir durante o processamento dessa entrada, o que nos permitirá "substituir" a entrada quando a máquina repetir seu "estado".

Para a prova formal, exigimos uma simplificação da estrutura da máquina HAL, a saber, que ela não contém um "loop" de transições 1 . Com essa suposição, podemos ver que, para cada símbolo de entrada que a máquina processa, o conteúdo do heap pode aumentar / diminuir em no máximo c (para alguma constante suficientemente grande c ).ε1cc

Prova.
Suponha que decida L e considere uma entrada longa o suficiente (por exemplo, comprimento 4 nHL4n , portanto , | z | = 2 n , ignorando os here a seguir). Para ser concreto, corrija z , y e assuma que # 0 ( y ) = n / 2 . Observe que existem ( n|x|=|y|=n|z|=2nz,y#0(y)=n/2diferentesx's tais quezyxL.(nn/2)xzyxL

Considere o conteúdo da pilha imediatamente após o processamento . Ele contém no máximo 3 n c símbolos (onde cada símbolo é de um alfabeto fixo Γ ), por nossa suposição. No entanto, existem ( nzy3ncΓdiferentesx'sque devem ser aceites (que é substancialmente maior do que a quantidade de conteúdo possíveis diferentes para a pilha, pois isso aumenta exponencialmente, ao passo que o número diferente de montões de aumentos polinomialmente, ver abaixo). Tome duas entradasx1,x2que devem ser aceitas, para que o seguinte seja válido:(nn/2)xsx1,x2

  1. O prefixo de comprimento de x 1 tem um número diferente de zeros que o prefixo de x 2 do mesmo comprimento.n/2x1x2
  2. No momento em que a máquina lê um prefixo de comprimento da parte x , a pilha fica igual para x 1 en/2xx1 e também, a máquina está no mesmo estado (isso deve ocorrer para x 1 , x 2 , para n grande o suficiente, pois existem mais de 2 0,8 n opções diferentes 2 para x 1 , x 2 e no máximo ( 3,5 c n ) | Γ | | Qx2x1,x2n20.8n2x1,x2opções diferentes para o conteúdo da pilha e o estado 3 ).(3.5cn)|Γ||Q|3

É claro que a máquina deve aceitar a palavra , onde x p 1 é um prefixo de x de comprimento n / 2 e x s 2 é um sufixo de x 2 do mesmo comprimento. Observe que o número de zeros em x p 1 x s 2 difere do número de zeros em x 1 e x 2 (ou seja, de # 0 ( yzyx1px2sx1pxn/2x2sx2x1px2sx1x2 ), devido à maneira como escolhemos x 1 e x 2 , chegamos a uma contradição.#0(y)x1x2

Essa suposição prejudica a generalidade? Acho que não, mas isso realmente exige uma prova. Se alguém vê como contornar essa suposição extra, eu adoraria saber. 2 Vamos corrigir x 1 para que seja seu prefixo (de comprimento n / 2 com exatamente n / 4 zeros). Lembre-se de que, usandoa aproximação de Stirling, sabemos que log ( n1
2 x1n/2n/4ondeH()é ofunciton entropia binário. DesdeH(1/4)0,81temos ( nlog(nk)nH(k/n)H()H(1/4)0.81para tamanho suficienten. (nn/4)>20.8nn3Assumindo o alfabetoΓ, existem| y-| nstrings diferentes de comprimenton, então, se essa fosse uma pilha, estaríamos ferrados. No entanto, inserir "01" em um heap equivale a "10" - o heap armazena apenas a versão classificada do conteúdo. O número de diferentessequênciasordenadasde tamanhoné (n+1
3 Γ|Γ|nnn, para uma constante| y-| .(n+1|Γ|1)n|Γ||Γ|

Tocou.
fonte
Agradável! Terá que ler a parte formal novamente mais tarde. 1) Anúncio See: Veja também aqui . 2) O argumento quebra se permitirmos a escolha não determinística do símbolo de pilha retornado (entre todos os símbolos da mesma prioridade).
Raphael