Las gramáticas son objetos inherentemente recursivos, por lo que la respuesta parece obvia: por inducción. Dicho esto, los detalles a menudo son difíciles de entender. En la secuela describiré una técnica que permite reducir muchas pruebas de corrección gramatical a pasos mecánicos, siempre que se realice un preprocesamiento creativo.
La idea básica es no restringirse a las palabras de gramática y lenguaje; Es difícil comprender la estructura de la gramática de esta manera. En cambio, discutiremos sobre el conjunto de oraciones que la gramática puede crear. Además, dividiremos un objetivo de prueba desalentador en muchos objetivos pequeños que son más manejables.
Deje que una gramática formal con los no terminales de , los terminales , las reglas y a partir símbolo . Denotamos por el conjunto de oraciones que se pueden derivar de dado , es decir, . El lenguaje generado por es . Supongamos que queremos mostrar que para algunos .N T δ S ∈ N ϑ ( G ) S δ α ∈ ϑ ( G )G=(N,T,δ,S)NTδS∈Nϑ(G)SδG L ( G ) = ϑ ( G ) ∩ T ∗ L = L ( G ) L ⊆ T ∗α∈ϑ(G)⟺S⇒∗αGL(G)=ϑ(G)∩T∗L = L ( G )L ⊆ T∗
El ansatz
Así es como lo hacemos. Definimos para queMETRO1, ... , Mk⊆ ( N∪ T)∗
- ϑ ( G ) = ⋃i = 1kMETROyo y
- T∗∩ ⋃i = 1kMETROyo= L .
Mientras que 2. generalmente es claro por definición de , 1. requiere un trabajo serio. Los dos elementos juntos implican claramente como se desee.L ( G ) = LMETROyoL (G)=L
Para facilitar la notación, denotemos .METRO= ⋃ki = 1METROyo
El camino rocoso
Hay dos pasos principales para realizar tal prueba.
¿Cómo encontrar (bueno) ? METROyo
Una estrategia es investigar las fases por las que funciona la gramática. No toda gramática es susceptible a esta idea; En general, este es un paso creativo. Ayuda si podemos definir la gramática nosotros mismos; Con cierta experiencia, podremos definir gramáticas más manejables con este enfoque.
¿Cómo probar 1.?
Como con cualquier conjunto de igualdad, hay dos direcciones.
- Gϑ ( G ) ⊆ M : (estructural) de inducción sobre las producciones de .sol
- M i SMETRO⊆ ϑ ( G ) : Por lo general, una inducción por , a partir de la que contiene .METROyoS
Esto es tan específico como se pone; los detalles dependen de la gramática y el idioma en cuestión.
Ejemplo
Considera el idioma
L = { anortesinortedometro∣ n , m ∈ N }
y la gramática con dada porδG = ( { S, A } , { a , b , c } , δ, S)δ
SUNA→ Sc ∣ A→ a A b ∣ ε
para lo cual queremos mostrar que . ¿Cuáles son las fases por las que funciona esta gramática? Bueno, primero genera luego . Esto informa inmediatamente nuestra elección de , a saberc m a n b n M iL=L(G)cmanbnMi
M0M1M2={Scm∣m∈N},={anAbncm∣m,n∈N},={anbncm∣m,n∈N}.
Como y , el elemento 2. ya se ha . Hacia 1., dividimos la prueba en dos partes como se anunció.M 0 ∩ T ∗ = M 1 ∩ T ∗ = ∅M2=LM0∩T∗=M1∩T∗=∅
ϑ(G)⊆M
Realizamos inducción estructural a lo largo de las reglas de .G
IA: Dado que anclamos con éxito.S=Sc0∈M0
IH: Supongamos por un conjunto de frases que también sabemos .X ⊆ MX⊆ϑ(G)X⊆M
IS: Deje arbitrario. Tenemos que demostrar que cualquiera de sus formas tiene y lo que se aplica la regla siguiente, que no deje . Hacemos esto por distinción de caso completo. Por hipótesis de inducción, sabemos que (exactamente) se aplica uno de los siguientes casos:α Mα∈X⊆ϑ(G)∩MαM
- w = S c m m ∈ N Mw∈M0 , es decir para algunos .
Se pueden aplicar dos reglas, las cuales derivan una oración en :
w=Scmetrom ∈ N
METRO
- Sdometro⇒ Sdom + 1∈ M0 0 y
- Sdometro⇒ A cmetro= a0 0A b0 0dometro∈ M1 .
- w = a n A b n c m m , n ∈ Nw ∈ M1 , es decir, para algunos :
w = anorteA bnortedometrom , n ∈ N
- w ⇒ an + 1A bn + 1dometro∈ M1 y
- w ⇒ anortesinortedometro∈ M2 .
- w ∈ T ∗w ∈ M3 : dado que , no son posibles más derivaciones.w ∈ T∗
Como hemos cubierto con éxito todos los casos, la inducción se ha completado.
ϑ ( G ) ⊇ M
Realizamos una prueba (simple) por . Observe cómo encadenamos las pruebas para que "posterior" pueda anclar utilizando el "anterior" .M i M iMETROyoMETROyoMETROyo
- m S c 0 = S S → S cMETRO1 : Realizamos una inducción sobre , anclando en y usando en el paso.metroSdo0 0= SS→ Sdo
- m n A c m S ⇒ ∗ S c m ⇒ A c m A → a A bMETRO2 : fijamos en un valor arbitrario e inducimos sobre . en , usando esa por la prueba anterior. El paso avanza a través de .metronorteA cmetroS⇒∗Sdometro⇒ A cmetroA → a A b
- METRO3 : Para arbitrario usamos la prueba anterior para .m , n ∈ NS⇒∗unanorteA bnortedometro⇒ unanortesinortedometro
Esto concluye la segunda dirección de la prueba de 1., y hemos terminado.
Podemos ver que explotamos mucho que la gramática es lineal . Para gramáticas no lineales, necesitamos con más de un parámetro variable (en la (s) prueba (s)), que puede volverse feo. Si tenemos control sobre la gramática, esto nos enseña a mantenerlo simple. Considere como ejemplo disuasorio esta gramática que es equivalente a :METROyosol
SUNAdo→ a A b C∣ ε→ a A b ∣ ε→ c C∣ ε
Ejercicio
Dar una gramática para
L = { bkunal( b c )metrounanortesio∣ k , l , m , n , o ∈ N , k ≠ o , 2 l = n , m ≥ 2 }
y probar su corrección.
Si tienes problemas, una gramática:
Considere con produccionesG = ( { S, Br, Bl, A , C},{a,b,c},δ,S)
SBlBrAC→bSb∣Bl∣Br→bBl∣bA→Brb∣Ab→aAaa∣C→bcC∣bcbc
y :Mi
M0M1M2M3M4M5={biSbi∣i∈N}={biBlbo∣o∈N,i≥o}={bkBrbi∣k∈N,i≥k}={bkaiAa2ibo∣k,o,i∈N,k≠o}={bkal(bc)iCa2lbo∣k,o,l,i∈N,k≠o}=L
¿Qué pasa con las gramáticas no lineales?
La característica que caracteriza la clase de lenguajes sin contexto es el lenguaje Dyck : esencialmente, cada lenguaje sin contexto puede expresarse como la intersección de un lenguaje Dyck y un lenguaje regular. Desafortunadamente, el lenguaje Dyck no es lineal, es decir, no podemos dar una gramática que sea inherentemente adecuada para este enfoque.
Mi
- ϑ(G)⊇L
- |L(G)∩Tn|=|L∩Tn|n∈N
G n∈N
Para las gramáticas ambiguas y sin contexto, me temo que volvemos a ansatz one y pensamos en mayúsculas.
- Cuando usamos ese método particular para contar, obtenemos como bonificación que la gramática es inequívoca. A su vez, esto también significa que la técnica tiene que fallar para las gramáticas ambiguas, ya que nunca podemos probar 2.