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 conseguiram 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.HA LHUMAeu
O HAL está fechado sob complementação?
Reivindicação : não está fechado contra complemento.H A LHUMAeu
Ideia de prova : concordamos que (o idioma dos palíndromos pares sobre um alfabeto não unário) não está em . Mostramos que . Isso funciona apenas para o tipo 1 (como o tipo 2 pode aceitar ); a prova pode ser adaptada para se adequar ao tipo 2, veja abaixo.EP A LEPUMAeuHA LHUMAeuE P A L¯¯¯¯¯¯¯¯¯¯¯¯¯¯∈ H A GEPUMAeu¯∈HUMAeu
E P A LEPUMAeu
Prova : Observe que
E P A L¯¯¯¯¯¯¯¯¯¯¯¯¯¯= { v w : | v | = | w | , v ≠WR}∪ { w : | w | ∈ 2 N+1 }EPUMAeu¯={vW:|v|=|W|,v≠WR}∪ {W:|W|∈2N+1}
Construímos um autômato min-heap com dois símbolos de heap que funcionam assim:b < ab<uma
No estado inicial, decida não-deterministicamente se o comprimento da entrada é uniforme.
No caminho irregular, use o controle finito para aceitar a entrada se e somente se seu comprimento for ímpar.
No caminho par, proceda da seguinte maneira:
v1 … vEu+ a vi + 1 … vn+ b Wn … Wi + 1- b WEu … W1- umv1 … vEu⏟+uma vEu+1 … vn⏟+b Wn … WEu+1⏟-b WEu … W1⏟-uma
Comece adicionando um à pilha para cada símbolo de leitura.umauma
Em uma posição não determinística, armazene o símbolo atual no controle finito e comece a adicionar um (e não ) à pilha para cada símbolo lido.bbumauma
Em uma posição não determinística, pare de adicionar símbolos e consuma um por símbolo de entrada.bb
Quando todos os forem consumidos, compare o símbolo atual com o símbolo armazenado no controle. Se eles são desiguais, continue; caso contrário, rejeite a entrada.bb
Consuma um por símbolo de entrada. Se o heap estiver vazio ao mesmo tempo em que a entrada termina, aceite a palavra; rejeitar o contrário.umauma
O autômato min-heap descrito aceita . Como seu complemento, , não está em , comprovamos a reivindicação.E P A L¯¯¯¯¯¯¯¯¯¯¯¯¯¯EPUMAeu¯E P A LEPUMAeuH A LHUMAeu
Nota: A prova pode ser executada da mesma maneira com (que está em ) e seu complemento. Isso se estende acima do resultado para o tipo 2.{ w w ∣ w ∈ { a , b}∗}{WW∣W∈{uma,b}∗}C S L ∖ H A LCSeu∖HUMAeu
+1 Resposta muito boa, para os autômatos de pilha mínima do tipo 1 (definição original). Com isso, dado o argumento relativamente simples que acho que mostra que os idiomas aceitos pelos autômatos de pilha mínima tipo 1 são fechados por união, também sabemos que o conjunto de idiomas aceitos pelos autômatos de pilha mínima 1 não está fechado sob interseção ou diferença, a partir de argumentos igualmente simples. Eu darei isso por um dia mais ou menos e depois aceito, apenas para dar a outras pessoas a chance de visitar e, possivelmente, fornecer outras respostas ... Além disso, o que acontece com os autômatos do tipo 2 min-heap (ou seja, a versão mais natural que você sugerido)?