Idiomas sin contexto cerrados bajo inversión

En la clase de esta semana hemos estado aprendiendo sobre las CFL y sus propiedades de cierre. He visto pruebas de unión, intersección y cumplido, pero para la reversión, mi profesor acaba de decir que está cerrado. Quería ver la prueba, así que he estado buscando durante los últimos días, pero todo lo que he encontrado es que la mayoría de la gente dice que revertir las producciones es suficiente para demostrarlo. Aquellos que se vuelven un poco más formales solo afirman que hay una prueba inductiva fácil que pueden dar. ¿Alguien puede proporcionarme más información / sugerencias sobre la prueba inductiva? Por más que lo intente, no se me ocurre.

Sus fuentes son correctas y me temo que solo hay poco que agregar, excepto el formalismo. I denotar la inversa (espejo) de cadena por .$w$$w^R$

Si es una gramática, dejar que sea su invertido, por lo que para la producción de en tenemos en .$G$$H$$A\to w$$G$$A\to w^R$$H$

Entonces por inducción se demuestra que si y sólo si .$A\Rightarrow_G^*w$$A\Rightarrow_H^*w^R$

• ( Base ) En cero pasos que tiene si y sólo si .$A\Rightarrow_G^0 A$$A\Rightarrow_H^0 A$
• ( inducción ) Suponiendo que iff podemos aplicar cualquier producción en (y en en reversa) y obtener y respectivamente, donde de hecho es el reverso de .$A\Rightarrow_G^*w_1Bw_2$$A\Rightarrow_H^*w_2^RBw_1^R$$B\to u$$G$$H$$A\Rightarrow_G^*w_1uw_2$$A\Rightarrow_H^*w_2^Ru^Rw_1^R$$w_2^Ru^Rw_1^R$$w_1uw_2$

Esta es una prueba muy condensada, pero contiene todos los ingredientes necesarios. Nuevamente, una derivación de la gramática inversa es la inversa de la original. Esto es especialmente claro cuando se observan los dos árboles de derivación.

Hay otra forma de ver este problema.

Considere que la Lengua es una CFL. Esto significa que hay una gramática que satisface la CFL. Podemos suponer que esto está en forma normal de Chomsky.$L$$G=\{N,\sum,P,S\}$

Si es parte del lenguaje, trivialmente también es parte del lenguaje. Ahora, para cada producción de la forma , reemplácela con, y para las producciones de la forma , donde , déjelo igual.$\epsilon$$\epsilon^R$$P_1 \longrightarrow AB$$P_1 \longrightarrow BA$$P_1 \longrightarrow a$$a \in \sum$

Desde el árbol de análisis de la cadena derivada, es fácil ver que el lenguaje derivado será exactamente el reverso del idioma inicial, ya que la construcción refleja el árbol de análisis original.

Antes que nada. Las CFL no están cerradas bajo intersección o complemento (o diferencia para el caso). Están cerrados bajo Unión, Concatenación, cierre de estrella de Kleene, sustitución, homomorfismo, homomorfismo inverso e inversión. NOTA: Los dos homomorfismos generalmente no están cubiertos en un curso de introducción a la teoría de computadoras.

Para probar la inversión, Sea L un CFL, con gramática G = (V, T, P, S). Sea L ^R el reverso de L, de modo que la gramática sea G ^R = (V, T, P ^R , S). Es decir, revertir cada producción.

Ex. P -> AB se convertiría en P -> BA

Como G ^R es un CFG, entonces L (G ^R ) es un CFL.