Comprovando o fechamento com a complementação de idiomas aceitos pelos autômatos de min-heap

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 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.$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 complementação?

Reivindicação : não está fechado contra complemento.$\mathrm{HAL}$

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.$\mathrm{EPAL}$$\mathrm{HAL}$$\overline{\mathrm{EPAL}} \in \mathrm{HAL}$
$\mathrm{EPAL}$

Prova : Observe que

$\qquad \displaystyle \begin{align*} \overline{\mathrm{EPAL}} &= \{vw : |v|=|w|, v\neq w^R\} \\ &\cup\ \,\{w : |w| \in 2\mathbb{N}\!+\!1\} \end{align*}$

Construímos um autômato min-heap com dois símbolos de heap que funcionam assim:$b < a$

• 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: $$\underbrace{v_1\ \dots\ \mathbf{v_{i}}}_{+a}\ \underbrace{v_{i+1}\ \dots\ v_n}_{+b}\ \underbrace{w_n\ \dots\ w_{i+1}}_{-b}\ \underbrace{\mathbf{w_i}\ \dots\ w_1}_{-a}$$
  • Comece adicionando um à pilha para cada símbolo de leitura.$a$
  • 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.$b$$a$
  • Em uma posição não determinística, pare de adicionar símbolos e consuma um por símbolo de entrada.$b$
  • 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.$b$
  • 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.$a$

O autômato min-heap descrito aceita . Como seu complemento, , não está em , comprovamos a reivindicação.$\overline{\mathrm{EPAL}}$$\mathrm{EPAL}$$\mathrm{HAL}$

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.$\{ww \mid w \in \{a,b\}^*\}$$\mathrm{CSL} \setminus \mathrm{HAL}$