lenguas celtas
Las lenguas celtas o célticas son un grupo de lenguas relacionadas descendientes del protocelta. Forman una rama de la familia de lenguas indoeuropeas. El... (leer más)
Forma normal de Chomsky
Ajustar Imprimir Citar
En la teoría del lenguaje formal, se dice que una gramática independiente del contexto, G, está en la forma normal de Chomsky (descrita por primera vez por Noam Chomsky) si toda su producción las reglas son de la forma:
- A → BC, o
- A → a, o
- S → ε,
donde A, B y C son símbolos no terminales, la letra a es un símbolo terminal (un símbolo que representa un valor constante), S es el símbolo de inicio y ε denota la cadena vacía. Además, ni B ni C pueden ser el símbolo de inicio, y la tercera regla de producción solo puede aparecer si ε está en L( G), el lenguaje producido por la gramática libre de contexto G.
Cada gramática en la forma normal de Chomsky es independiente del contexto y, a la inversa, toda gramática independiente del contexto se puede transformar en una equivalente que está en la forma normal de Chomsky y tiene un tamaño no mayor que el cuadrado de la gramática original.;s tamaño.
Convertir una gramática a la forma normal de Chomsky
Para convertir una gramática a la forma normal de Chomsky, se aplica una secuencia de transformaciones simples en un cierto orden; esto se describe en la mayoría de los libros de texto sobre teoría de autómatas. La presentación aquí sigue a Hopcroft, Ullman (1979), pero está adaptada para usar los nombres de transformación de Lange, Leiß (2009). Cada una de las siguientes transformaciones establece una de las propiedades requeridas para la forma normal de Chomsky.
INICIO: Eliminar el símbolo de inicio de los lados derechos
Introducir un nuevo símbolo de inicio S0, y una nueva regla
- S0 → S,
donde S es el símbolo de inicio anterior. Esto no cambia el lenguaje producido por la gramática, y S0 no aparecerá en el lado derecho de ninguna regla.
TÉRMINO: Eliminar reglas con terminales no solitarios
Para eliminar cada regla
- A → X1... a... Xn
con un símbolo terminal a que no es el único símbolo en el lado derecho, introduzca, para cada terminal, un nuevo símbolo no terminal Na, y una nueva regla
- Na → a.
Cambiar todas las reglas
- A → X1... a... Xn
a
- A → X1... Na... Xn.
Si aparecen varios símbolos terminales en el lado derecho, reemplace simultáneamente cada uno de ellos por su símbolo no terminal asociado. Esto no cambia el lenguaje producido por la gramática.
BIN: Elimina los lados derechos con más de 2 no terminales
Reemplazar cada regla
- A → X1 X2... Xn
con más de 2 no terminales X1,...,Xn por reglas
- A → X1 A1,
- A1 → X2 A2,
- ...
- An-2 → Xn-1 Xn,
donde Ai son nuevos símbolos no terminales. Nuevamente, esto no cambia el lenguaje producido por la gramática.
DEL: eliminar las reglas ε
Una regla ε es una regla de la forma
- A → ε,
donde A no es S0, el símbolo de inicio de la gramática.
Para eliminar todas las reglas de esta forma, primero determina el conjunto de todos los no terminales que derivan de ε. Hopcroft y Ullman (1979) llaman a tales no terminales anulables, y los calculan de la siguiente manera:
- Si una regla A → ε existe, entonces A es nulo.
- Si una regla A → X1... Xn existe, y cada uno Xi es nula, entonces A también es nulo.
Obtenga una gramática intermedia reemplazando cada regla
- A → X1... Xn
por todas las versiones con alguna Xi anulable omitida. Al eliminar en esta gramática cada regla ε, a menos que su lado izquierdo sea el símbolo de inicio, se obtiene la gramática transformada.
Por ejemplo, en la siguiente gramática, con el símbolo de inicio S0,
- S0 → AbB Silencio C
- B → AA Silencio AC
- C → b Silencio c
- A → a ε
el no terminal A, y por lo tanto también B, es anulable, mientras que ni C ni S0 es. Por tanto, se obtiene la siguiente gramática intermedia:
- S0 → AbB Silencio Ab
BSilencioAbB SilencioAbBSilencio C - B → AA Silencio
AA Silencio AASilencioAεASilencio AC SilencioAC - C → b Silencio c
- A → a ε
En esta gramática, todas las reglas ε se han "en línea en el sitio de llamada". En el siguiente paso, por lo tanto, se pueden eliminar, lo que da como resultado la gramática:
- S0 → AbB Silencio Ab Silencio bB Silencio b Silencio C
- B → AA Silencio A Silencio AC Silencio C
- C → b Silencio c
- A → a
Esta gramática produce el mismo lenguaje que la gramática del ejemplo original, a saber. {ab,aba,abaa,abab,abac,abb ,abc,b,bab,bac,bb, bc,c}, pero no tiene reglas ε.
UNIDAD: Eliminar reglas de unidad
Una regla de unidad es una regla de la forma
- A → B,
donde A, B son símbolos no terminales. Para eliminarlo, para cada regla
- B → X1... Xn,
donde X1... Xn es una cadena de no terminales y terminales, añadir regla
- A → X1... Xn
a menos que se trate de una regla de unidad que ya se eliminó (o se eliminará). La omisión del símbolo no terminal B en la gramática resultante es posible debido a que B es miembro del cierre de unidad del símbolo no terminal A.
Orden de las transformaciones
Transformación X siempre conserva () Y)Resp. puede destruir ()  N) el resultado de Y:
| |||||
Y X | START | TERM | BIN | DEL | UNIT |
|---|---|---|---|---|---|
| START |  | |  | | |
| TERM | | | | | |
| BIN | | | | | |
| DEL | | | | | |
| UNIT | | | | ()Y)* | |
| *UNIT preserva el resultado de DEL si START había sido llamado antes. | |||||
Al elegir el orden en el que se aplicarán las transformaciones anteriores, se debe tener en cuenta que algunas transformaciones pueden destruir el resultado logrado por otras. Por ejemplo, START volverá a introducir una regla de unidad si se aplica después de UNIT. La tabla muestra qué pedidos se admiten.
Además, el tamaño de la gramática en el peor de los casos depende del orden de transformación. Usando |G| para indicar el tamaño de la gramática original G, el tamaño ampliado en el peor de los casos puede oscilar entre |G|2 a 22 |G|, dependiendo del algoritmo de transformación utilizado. La ampliación del tamaño de la gramática depende del orden entre DEL y BIN. Puede ser exponencial cuando DEL se hace primero, pero es lineal en caso contrario. UNIT puede incurrir en una ampliación cuadrática en el tamaño de la gramática. Los pedidos START, TERM, BIN, DEL, UNIT y START, BIN, DEL, UNIT, TERM conducen al golpe mínimo (es decir, cuadrático) -hasta.
Ejemplo
Árbol de sintaxis abstracto de la expresión aritmética "a^2+4*b" wrt. la gramática de ejemplo (arriba) y su forma normal Chomsky (inferior)
La siguiente gramática, con el símbolo de inicio Expr, describe una versión simplificada del conjunto de todas las expresiones aritméticas sintácticas válidas en lenguajes de programación como C o Algol60. Tanto number como variable se consideran aquí símbolos de terminal por simplicidad, ya que en una interfaz de compilación el analizador no suele tener en cuenta su estructura interna. El símbolo de terminal "^" exponenciación denotada en Algol60.
Gastos → Término Silencio Gastos AddOp Término Silencio AddOp Término Término → Factor Silencio Término MulOp Factor Factor → Primaria Silencio Factor ^ Primaria Primaria → Número Silencio variable SilencioGastos) AddOp → + Silencio MulOp → * Silencio
En el paso "INICIAR" del algoritmo de conversión anterior, solo se agrega una regla S0→Expr a la gramática. Después del paso "TERM", la gramática se ve así:
S0 → Gastos Gastos → Término Silencio Gastos AddOp Término Silencio AddOp Término Término → Factor Silencio Término MulOp Factor Factor → Primaria Silencio Factor PowOp Primaria Primaria → Número Silencio variable Silencio Abierto Gastos Cerca AddOp → + Silencio MulOp → * Silencio PowOp → ^ Abierto → Cerca →)
Después del paso "BIN", se obtiene la siguiente gramática:
S0 → Gastos Gastos → Término Silencio Gastos AddOp_Term Silencio AddOp Término Término → Factor Silencio Término MulOp_Factor Factor → Primaria Silencio Factor PowOp_Primary Primaria → Número Silencio variable Silencio Abierto Expr_Close AddOp → + Silencio MulOp → * Silencio PowOp → ^ Abierto → Cerca →) AddOp_Term → AddOp Término MulOp_Factor → MulOp Factor PowOp_Primary → PowOp Primaria Expr_Close → Gastos Cerca
Dado que no hay reglas ε, el paso "DEL" no cambia la gramática. Después del paso "UNIT", se obtiene la siguiente gramática, que está en la forma normal de Chomsky:
S0 → Número Silencio variable Silencio Abierto Expr_Close Silencio Factor PowOp_Primary Silencio Término MulOp_Factor Silencio Gastos AddOp_Term Silencio AddOp Término Gastos → Número Silencio variable Silencio Abierto Expr_Close Silencio Factor PowOp_Primary Silencio Término MulOp_Factor Silencio Gastos AddOp_Term Silencio AddOp Término Término → Número Silencio variable Silencio Abierto Expr_Close Silencio Factor PowOp_Primary Silencio Término MulOp_Factor Factor → Número Silencio variable Silencio Abierto Expr_Close Silencio Factor PowOp_Primary Primaria → Número Silencio variable Silencio Abierto Expr_Close AddOp → + Silencio MulOp → * Silencio PowOp → ^ Abierto → Cerca →) AddOp_Term → AddOp Término MulOp_Factor → MulOp Factor PowOp_Primary → PowOp Primaria Expr_Close → Gastos Cerca
La Na introducida en el paso "TERM" son PowOp, Abrir y Cerrar. El Ai introducido en el paso "BIN" son AddOp_Term, MulOp_Factor, PowOp_Primary y Expr_Close.
Definición alternativa
Forma reducida de Chomsky
Otra manera de definir la forma normal de Chomsky es:
Una gramática formal está en forma reducida de Chomsky si todas sus reglas de producción son de la forma:
- A→ → BC{displaystyle Arightarrow ,BC} o
- A→ → a{displaystyle Arightarrow ,a},
Donde A{displaystyle A}, B{displaystyle B} y C{displaystyle C} son símbolos no finales, y a{displaystyle a} es un símbolo terminal. Al utilizar esta definición, B{displaystyle B} o C{displaystyle C} puede ser el símbolo de inicio. Sólo esas gramáticas sin contexto que no generan la cadena vacía pueden transformarse en forma reducida Chomsky.
Forma normal de Floyd
En una carta en la que proponía un término forma Backus-Naur (BNF), Donald E. Knuth insinuaba una sintaxis BNF en la que todas las definiciones tienen tal forma y se puede decir que está en 'Floyd Forma normal'",
- .. A.. ::=.. B.. ▪ ▪ .. C.. {displaystyle langle Arangle:=,langle Brangle mid langle Crangle } o
- .. A.. ::=.. B.. .. C.. {displaystyle langle Arangle:=,langle Brangle langle Crangle } o
- .. A.. ::=a{displaystyle langle Arangle:=,a},
Donde .. A.. {displaystyle langle Arangle }, .. B.. {displaystyle langle Brangle } y .. C.. {displaystyle langle Crangle } son símbolos no finales, y a{displaystyle a} es un símbolo terminal, porque Robert W. Floyd encontró cualquier sintaxis BNF se puede convertir a la anterior en 1961. Pero retiró este término, "ya que sin duda muchas personas han utilizado independientemente este simple hecho en su propio trabajo, y el punto es sólo incidental a las principales consideraciones de la nota de Floyd." Mientras que la nota de Floyd cita el artículo original de Chomsky en 1959, la carta de Knuth no.
Solicitud
Además de su importancia teórica, la conversión CNF se usa en algunos algoritmos como un paso de preprocesamiento, por ejemplo, el algoritmo CYK, un análisis de abajo hacia arriba para gramáticas sin contexto y su variante CKY probabilística.