Computando a interseção de dois NPDA onde é possível

Apropois à sugestão de Raphael sobre a interseção de dois NPDAs :

Deixe e NPDA para linguagens sem contexto e , respectivamente. Supondo que sabemos que é livre de contexto, podemos (efetivamente) construir o NPDA para ? $A_1$ $A_2$ $L_1$ $L_2$ $L = L_1 \cap L_2$ $A$ $L$

Qualquer tipo de algoritmo seria aceitável, mas quanto mais prático, melhor.

computability automata pushdown-automata soandos
fonte

um exemplo desse L em que nem L1 / L2 são regulares e a interseção não está vazia pode ser útil, existe um L? problemas um tanto semelhantes nos NPDAs (testar o vazio da interseção, testar a igualdade) são indecidíveis. sugerem migrar / promover a tcs.se se nenhuma resposta materializa

vzn

@ vzn Eu acredito que tenho um exemplo de ~ 50 estados, vou tentar encontrar alguém que seja mais mínimo

soandos

O conjunto de cadeias de caracteres "pelo menos 1/3 de 1" e "menos de 2/3 de 1" no alfabeto

são ambos DCFLs, e sua interseção é uma CFL (e não uma DCFL)

{0, 1}

$\{0,1\}$

sjmc

@sjmc você pode esboçar uma prova? não é óbvio para mim. vai upvote se você postá-lo como resposta, mesmo que a resposta não está completa, a sua algum progresso

vzn

atualizar, isso parece ser respondido como indecidível em tcs.se, com base no cálculo arbitrário da TM que pode ser expresso como a interseção de duas CFLs.

vzn

Respostas:

Eu acho que isso é possível para a subclasse de CFLs que são invariantes à permutação com um alfabeto binário.

$\langle 1,1\rangle$ linguagens quantificadoras comparando as cardinalidades de dois conjuntos. [1] caracteriza esses idiomas aceitos pelo DPDA pelos conjuntos semilineares equivalentes e afirma no final que os idiomas quantificadores aceitos pelo NPDA são combinações booleanas finitas desses idiomas aceitos pelo DPDA.

Um teorema de van Benthem (2) diz que os autômatos de empilhamento aceitam o tipo $\langle 1,1\rangle$ quantificadores definíveis na aritmética de Presburger (isto é, definidos por conjuntos semilineares). Portanto, se você obtiver duas linguagens que não são deterministas nas CFLs (usando o primeiro artigo para saber que você tem exemplos), a interseção delas também deve ser uma CFL nesse teorema.

O conjunto semilinear, que é sua interseção, pode ser um pouco difícil de calcular ... mas, se você tiver, [3] (págs. 11-12) fornecem um algoritmo para criar um NPDA que aceita a linguagem com base nos geradores do conjunto semilinear correspondente.

[1] Makoto Kanazawa. Quantiers monádicos reconhecidos por autômatos determinísticos de push-down . Em Anais do 19º Colóquio de Amsterdã, páginas 139-146, 2013.

[2] Johann van Benthem. Ensaios em Semântica Lógica . Estudos em Linguística e Filosofia Volume 29, 1986, pp 151-176.

[3] Marcin Mostowski. Semântica computacional para quantiers monádicos . Journal of Applied Non-Classical Logics, 8 (1-2): 107-121, 1998.

sjmc
fonte