Calcular la intersección de dos NPDA donde es posible

A propósito de la sugerencia de Raphael sobre la intersección de dos NPDA :

Deje y NPDA para lenguajes libres de contexto y , respectivamente. Suponiendo que sabemos que tiene contexto, ¿podemos (efectivamente) construir NPDA para ? $A_1$ $A_2$ $L_1$ $L_2$ $L = L_1 \cap L_2$ $A$ $L$

Cualquier tipo de algoritmo sería aceptable, pero cuanto más práctico, mejor.

computability automata pushdown-automata soandos
fuente

un ejemplo de tal L donde ni L1 / L2 son regulares y la intersección no está vacía podría ser útil, ¿existe tal L? problemas algo similares wrt NPDAs (prueba de vacío de intersección, prueba de igualdad) son indecidibles. sugiera migrar / promocionar a tcs.se si no se materializa una respuesta

vzn

@vzn Creo que tengo un ejemplo de ~ 50 estados, intentaré encontrar a alguien que sea más minimalista

soandos

{0, 1}

$\{0,1\}$

@sjmc, ¿puedes dibujar una prueba? No es obvio para mí.

votará positivamente si lo publicas

actualizar esto parece ser respondido como indecidible en tcs.se basado en que el cálculo arbitrario de TM puede expresarse como la intersección de dos CFL.

vzn

Respuestas:

Creo que esto es posible para la subclase de CFL que son invariantes de permutación con un alfabeto binario.

$\langle 1,1\rangle$

El conjunto semilineal que es su intersección puede ser un poco difícil de calcular ... pero, si tiene eso, [3] (pgs.11-12) proporcione un algoritmo para crear un NPDA que acepte el lenguaje basado en los generadores de la conjunto semilineal correspondiente.

[1] Makoto Kanazawa. Cuantiers monádicos reconocidos por autómatas deterministas . En Actas del XIX Coloquio de Amsterdam, páginas 139-146, 2013.

[2] Johann van Benthem. Ensayos de semántica lógica . Estudios en Lingüística y Filosofía Volumen 29, 1986, pp 151-176.

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

sjmc
fuente