Gramática sensible al contexto para el lenguaje de palabras concatenadas consigo mismas

9

Estoy buscando una gramática sensible al contexto que describa el siguiente lenguaje: .L={www{una,si},El |wEl |1}

Tengo problemas con el hecho de que no se permiten reglas como y, por lo tanto, no puedo colocar ningún término que indique el "medio" de la palabra. ¿Hay algún truco para el problema?Xε

MrBolton
fuente
1
Respuesta aburrida: formule un LBA y aplique la simulación utilizada para demostrar que los LBA y las gramáticas sensibles al contexto son igualmente poderosas.
Raphael

Respuestas:

6

De hecho, hay un truco simple que le permite agregar información adicional en una posición determinada: simplemente reemplace una letra adyacente a la posición y márquela con la información y la letra original.

En su ejemplo, tenga una no terminal para el medio, pero como no se puede eliminar, también cuenta como una letra normal. Por lo tanto, tenemos dos copias y para indicar las letras reemplazadas. Al final de la derivación, los marcadores deben reemplazarse por el contenido de su letra, por producciones simples como .M a M b M aaMETROMETROunaMETROsiMETROunauna

En la mayoría de los casos, la aplicación de a debe realizarse al final del proceso de derivación. En algunas construcciones esto no necesita ser "cronometrado": cuando la desaparece demasiado pronto, la derivación no puede encontrar una posición adecuada y el proceso no se detendrá con éxito. En otros casos, uno necesita un tipo de control. Esto a veces se hace introduciendo un no terminal como señal que se mueve a lo largo de las letras. Una vez más, esta señal también debe llevar un terminal, de lo contrario, terminará en los mismos problemas.MMETROunaunaMETRO

Mover la información es fácil en las llamadas gramáticas monótonas ( con ) utilizando reglas como , que puede ser visto como que salta sobre . Para las gramáticas sensibles al contexto adecuadas, es necesario dividir esto en tres pasos: . en cada producción se cambia una letra en un contexto apropiado. Se necesita bastante imaginación para ver que este proceso no interactúa con otras partes de la derivación. Por ejemplo, ¿qué sucede cuando la en el último paso se involucra por primera vez en otro paso de derivación?| α | β | X A A X X A X A X A X , X A XA A X , A A XA X AαβEl |αEl |βEl |XUNAUNAXXUNAXUNAXUNAX,XUNAXUNAUNAX,UNAUNAXUNAXUNA

Esto podría no funcionar para palabras muy cortas, cuando hay más información que posiciones disponibles. La solución más simple para eso es ignorar cadenas cortas en su construcción y generarlas por separado.

Hendrik Jan
fuente
¿No requeriría que la producción se examinara en un cierto orden para que Ma → a no se usara antes de reorganizar los no terminales hasta el final? ¿O me estoy perdiendo algo?
MrBolton
Agregué una nota a eso en mi respuesta. En algunas soluciones, aplicar dicha producción demasiado pronto dará como resultado una forma de sentencia que no se puede terminar con éxito. En otros casos, las producciones tienen que sincronizarse cuidadosamente. Una cuestión de sentido común y prueba y error.
Hendrik Jan
1

Respuesta predeterminada corta: cree un LBA que acepte el idioma y utilice la simulación utilizada para demostrar que las gramáticas sensibles al contexto y el LBA definen el mismo conjunto de idiomas. Pero eso, por supuesto, no es lo que buscas.

En este caso específico, trate de pensar en usar una gramática lineal derecha para dos veces, una para la izquierda y otra para la mitad derecha. Todo lo que tiene que hacer es asegurarse de que ambas gramáticas deriven "en sincronía".Σ

Esto se puede hacer cambiando un token de control. Es decir, las gramáticas de la izquierda escogen una regla, generan el token de control de ajuste y lo pasan a la gramática correcta. La gramática correcta ve el token de control y ejecuta la regla de ajuste. Tenga en cuenta que también puede implementar la comunicación bidireccional de esta manera, pero no es necesario aquí.

Hay un problema con las gramáticas sensibles al contexto: nunca pueden eliminar no terminales (excepto si la palabra vacía está en el idioma). Por lo tanto, tenemos que crear solo los no terminales que necesitemos; ninguno puede ser redundante.Sε

Una forma de lograr esto es usar el mismo truco que para ciertas pruebas sobre LBA: generar todos los no terminales que va a necesitar primero , es decir, preparar la "cinta". Más tarde, "muévete" en esa cinta. Solo "al final", reemplace todos los no terminales por terminales.

Deje que con (la construcción se extiende fácilmente a alfabetos más grandes) y , dada por las siguientes reglas. son las reglas para generar la "cinta". Tenga en cuenta que el sombrero denota la "posición de la cabeza" e índicessol=(norte,Σ,δ,S)N δΣ={una,si}norteδ

l,rSX^lSXrunaunaunaunaunasiunasisiunasiunasisisisiunaunasisiεSXlSXrXlX^r

l,rdenotar a qué mitad de la palabra pertenece un no terminal. Las palabras cortas se generan así para salvaguardar algunas reglas a continuación. Ahora necesitamos reglas para derivar un símbolo en la parte izquierda: para todos . Observe cómo usamos el índice superior para llevar el símbolo generado a la derecha. y son no terminales "finales" que solo se utilizarán para mover el token de control y derivar terminales más tarde. Tenga en cuenta además que la segunda regla se usa (solo) para el último símbolo de la mitad derecha. Para mover el carry a la mitad derecha, tenemos que pasar los dos restantes

(α,γ)Σ2XaXbXlXαX^lXlXγX^lγX^lXαXγXαγ

(α,γ)Σ2XunaXsi

Xl y ya generado : para todos . Ahora, una vez que el carry llega al token de control derecho, tenemos que imitar la regla utilizada a la izquierda: para todosXα

X^lγXlX^lXlγX^lγXαX^lXαγXlγXlXlXlγXlγXαXlXαγXαγXβXαXβγ

(α,β,γ)Σ3

XlγX^rXlX^rγXαγX^rXαX^rγX^rγXrXγX^rX^rγXγ

(α,γ)Σ2 . Tenga en cuenta que la primera regla se usa para el primer símbolo de la mitad derecha, y que la última regla solo se puede usar para el último símbolo; de lo contrario, la derivación nunca termina. Ahora solo necesitamos las reglas de terminación para todos y ya hemos terminado. Estas reglas, también, solo pueden aplicarse después de que todo (a la izquierda) esté hecho, de lo contrario la derivación no terminará. Tenga en cuenta que esta gramática es ambigua. No solo se puede (de forma segura) en cualquier lugar a la izquierda de la "cabeza" izquierda en cualquier momento, sino que también se pueden realizar múltiples acarreos al mismo tiempo. Como nunca pueden adelantarse entre sí, se mantiene el orden correcto.

Xαα

αΣ

Xαα

Todavía hay que hacer una observación: la gramática anterior no es sensible al contexto, ya que muchas reglas cambian ambos símbolos en el lado izquierdo. Esto no está permitido para las gramáticas sensibles al contexto. Afortunadamente, podemos simular cualquier regla de la forma por para que seamos buenos y podamos trabajar con la gramática más pequeña. Mostrar que la interferencia entre múltiples simulaciones de este tipo no duele se deja como un ejercicio.R

UNAsiCre



UNAsiUNAYRUNAYRXRYRXRYRXRreXRreCre

¿Ves cómo extender esto a ? ¿ también para ? ¿Puedes usar la misma construcción para cualquier para normal ?Lk={wkwΣ}L=yo1LkLkL

Rafael
fuente
0

Aunque no sé cómo se verá la gramática sensible al contexto, puede eludir su problema con el símbolo siguiente manera.X

wEl |wEl |1ε

unaXunaunauna,  unaXsiunasi,  siXunasiuna,  siXsisisi

w

Rmn
fuente
Sin embargo, usar el enfoque de @ hendrik-jan le ahorra dos reglas.
Rmn