En la teoría del lenguaje formal , se dice que una gramática libre de contexto , G , está en la forma normal de Chomsky (descrita por primera vez por Noam Chomsky ) [1] si todas sus reglas de producción son de la forma: [ cita requerida ]
- 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 sólo pueden aparecer si ε está en L ( G ), el lenguaje producido por la gramática libre de contexto G . [2] : 92–93,106
Cada gramática en forma normal Chomsky es libre de contexto , y por el contrario, cada gramática libre de contexto se puede transformar en un equivalente uno [nota 1] que está en forma normal de Chomsky y tiene un tamaño no mayor que el cuadrado del tamaño de la gramática originales .
Conversión de 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. [2] : 87–94 [3] [4] [5] La presentación aquí sigue a Hopcroft, Ullman (1979), pero está adaptada para usar los nombres de transformación de Lange, Leiß (2009). [6] [nota 2] Cada una de las siguientes transformaciones establece una de las propiedades requeridas para la forma normal de Chomsky.
INICIO: Elimina el símbolo de inicio de los lados derechos.
Introduzca un nuevo símbolo de inicio S 0 y una nueva regla
- S 0 → S ,
donde S es el símbolo de inicio anterior. Esto no cambia el lenguaje producido por la gramática y S 0 no ocurrirá en el lado derecho de ninguna regla.
PLAZO: Eliminar reglas con terminales no solitarias
Para eliminar cada regla
- A → X 1 ... a ... X n
con un símbolo de terminal a no siendo el único símbolo en el lado derecho, introduzca, para cada terminal de este tipo, un nuevo símbolo no terminal N a , y una nueva regla
- N a → a .
Cambia todas las reglas
- A → X 1 ... a ... X n
a
- A → X 1 ... N a ... X n .
Si aparecen varios símbolos de terminal 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. [2] : 92
BIN: Elimina los lados derechos con más de 2 no terminales
Reemplazar cada regla
- A → X 1 X 2 ... X n
con más de 2 no terminales X 1 , ..., X n por reglas
- A → X 1 A 1 ,
- A 1 → X 2 A 2 ,
- ...,
- Una norte -2 → X norte -1 X norte ,
donde A i son nuevos símbolos no terminales. Nuevamente, esto no cambia el lenguaje producido por la gramática. [2] : 93
DEL: Elimina las reglas ε
Una regla ε es una regla de la forma
- A → ε,
donde A no es S 0 , el símbolo de inicio de la gramática.
Para eliminar todas las reglas de esta forma, primero determine el conjunto de todos los no terminales que derivan ε. Hopcroft y Ullman (1979) llaman a estos no terminales anulables y los calculan de la siguiente manera:
- Si existe una regla A → ε, entonces A es anulable.
- Si existe una regla A → X 1 ... X n , y cada X i es anulable, entonces A también es anulable.
Obtenga una gramática intermedia reemplazando cada regla
- A → X 1 ... X n
por todas las versiones con alguna X i anulable omitida. Eliminando en esta gramática cada regla ε, a menos que su lado izquierdo sea el símbolo de inicio, se obtiene la gramática transformada. [2] : 90
Por ejemplo, en la siguiente gramática, con el símbolo de inicio S 0 ,
- S 0 → AbB | C
- B → AA | C.A.
- C → b | C
- A → a | ε
el no terminal A , y por tanto también B , es anulable, mientras que ni C ni S 0 lo son. De ahí se obtiene la siguiente gramática intermedia: [nota 3]
- S 0 → A b B | A b
B|Ab B |AbB| C - B → AA |
AA | AA|AεA| A C |AC - C → b | C
- A → a | ε
En esta gramática, todas las reglas ε han sido " alineadas en el sitio de llamada". [nota 4] En el siguiente paso, por lo tanto, se pueden eliminar, dando como resultado la gramática:
- S 0 → AbB | Ab | bB | b | C
- B → AA | A | AC | C
- C → b | C
- A → a
Esta gramática produce el mismo lenguaje que la gramática de ejemplo original, a saber. { ab , aba , abaa , abab , abac , abb , abc , b , bab , bac , bb , bc , c }, pero no tiene reglas ε.
UNIDAD: Elimina las reglas de la 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 → X 1 ... X n ,
donde X 1 ... X n es una cadena de no terminales y terminales, agregue la regla
- A → X 1 ... X n
a menos que se trate de una regla de unidad que ya ha sido (o está siendo) eliminada.
Orden de transformaciones
La transformación X siempre conserva ( ) resp. puede destruir ( ) el resultado de Y : | |||||
Y X | COMIENZO | TÉRMINO | COMPARTIMIENTO | DEL | UNIDAD |
---|---|---|---|---|---|
COMIENZO | |||||
TÉRMINO | |||||
COMPARTIMIENTO | |||||
DEL | |||||
UNIDAD | ( | ) *||||
* UNIT conserva el resultado de DEL si se ha llamado a START antes. |
A la hora de elegir el orden en el que se van a aplicar las transformaciones anteriores, hay que tener en cuenta que algunas transformaciones pueden destruir el resultado logrado por otras. Por ejemplo, START reintroducirá una regla de unidad si se aplica después de UNIT . La tabla muestra qué pedidos se admiten.
Además, la hinchazón en el peor de los casos en el tamaño de la gramática [nota 5] depende del orden de transformación. Usando | G | para denotar el tamaño de la gramática original G , el tamaño de la ampliación en el peor de los casos puede oscilar entre | G | 2 a 2 2 | G | , dependiendo del algoritmo de transformación utilizado. [6] : 7 La ampliación del tamaño de la gramática depende del orden entre DEL y BIN . Puede ser exponencial cuando se hace DEL primero, pero es lineal en caso contrario. UNIDAD puede incurrir en una explosión cuadrática en el tamaño de la gramática. [6] : 5 Los pedidos START , TERM , BIN , DEL , UNIT y START , BIN , DEL , UNIT , TERM conducen a la menor explosión (es decir, cuadrática).
Ejemplo
La siguiente gramática, con el símbolo de inicio Expr , describe una versión simplificada del conjunto de todas las expresiones aritméticas válidas sintácticamente en lenguajes de programación como C o Algol60 . Tanto el número como la variable se consideran aquí símbolos de terminal por simplicidad, ya que en el front-end de un compilador su estructura interna generalmente no es considerada por el analizador . El símbolo terminal "^" denota exponenciación en Algol60.
Expr → Término | Término AddOp Expr | Término AddOp Término → Factor | Término Factor de MulOp Factor → Primaria | Factor ^ Primario Primario → número | variable | ( Expr ) AddOp → + | - MulOp → * | /
En el paso "INICIO" del algoritmo de conversión anterior , solo se agrega una regla S 0 → Expr a la gramática. Después del paso "TERM", la gramática se ve así:
S 0 → Expr Expr → Término | Término AddOp Expr | Término AddOp Término → Factor | Término Factor de MulOp Factor → Primaria | Factor PowOp Primario Primario → número | variable | Abrir Expr Cerrar AddOp → + | - MulOp → * | / PowOp → ^ Abierto → ( Cerca →)
Después del paso "BIN", se obtiene la siguiente gramática:
S 0 → Expr Expr → Término | Expr AddOp_Term | Término AddOp Término → Factor | Término MulOp_Factor Factor → Primaria | Factor PowOp_Primary Primario → número | variable | Abrir Expr_Close AddOp → + | - MulOp → * | / PowOp → ^ Abierto → ( Cerca →) AddOp_Term → Término AddOp MulOp_Factor → Factor MulOp PowOp_Primary → Primario de PowOp Expr_Close → Expr Cerrar
Como no hay reglas ε, el paso "DEL" no cambia la gramática. Después del paso "UNIDAD", se obtiene la siguiente gramática, que está en la forma normal de Chomsky:
S 0 → número | variable | Abrir Expr_Close | Factor PowOp_Primary | Término MulOp_Factor | Expr AddOp_Term | Término AddOp Expr → número | variable | Abrir Expr_Close | Factor PowOp_Primary | Término MulOp_Factor | Expr AddOp_Term | Término AddOp Término → número | variable | Abrir Expr_Close | Factor PowOp_Primary | Término MulOp_Factor Factor → número | variable | Abrir Expr_Close | Factor PowOp_Primary Primario → número | variable | Abrir Expr_Close AddOp → + | - MulOp → * | / PowOp → ^ Abierto → ( Cerca →) AddOp_Term → Término AddOp MulOp_Factor → Factor MulOp PowOp_Primary → Primario de PowOp Expr_Close → Expr Cerrar
Los N a introducidos en el paso "TERM" son PowOp , Open y Close . Las A i introducidas en el paso "BIN" son AddOp_Term , MulOp_Factor , PowOp_Primary y Expr_Close .
Definición alternativa
Forma reducida de Chomsky
Otra forma [2] : 92 [7] 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:
- o
- ,
dónde , y son símbolos no terminales, y es un símbolo de terminal . Al usar esta definición, o puede ser el símbolo de inicio. Solo aquellas gramáticas libres de contexto que no generan la cadena vacía pueden transformarse a la forma reducida de Chomsky.
Forma normal de Floyd
En una carta en la que propuso un término forma Backus-Naur (BNF), Donald E. Knuth implicó una sintaxis BNF en la que todas las definiciones tienen tal forma se puede decir que están en 'Forma normal Floyd' ",
- o
- o
- ,
dónde , y son símbolos no terminales, y es un símbolo terminal , porque Robert W. Floyd descubrió que cualquier sintaxis BNF se puede convertir a la anterior en 1961. [8] Pero retiró este término, "ya que sin duda muchas personas han usado independientemente este simple hecho en su propio trabajo, y el punto es sólo incidental a las principales consideraciones de la nota de Floyd ". [9] Mientras que la nota de Floyd cita el artículo original de 1959 de Chomsky, la carta de Knuth no lo hace.
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 libres de contexto y su variante probabilística CKY. [10]
Ver también
- Forma Backus-Naur
- Algoritmo CYK
- Greibach forma normal
- Forma normal de Kuroda
- Bombeando lema para lenguajes libres de contexto : su prueba se basa en la forma normal de Chomsky
Notas
- ^ es decir, uno que produce el mismo idioma
- ^ Por ejemplo, Hopcroft, Ullman (1979) fusionó TERM y BIN en una sola transformación.
- ^ que indica un N no terminal guardado y omitidopor N y
N, respectivamente - ^ Si la gramática tuviera una regla S 0 → ε, no podría estar "en línea", ya que no tenía "sitios de llamada". Por lo tanto, no se pudo eliminar en el siguiente paso.
- ^ es decir, longitud escrita, medida en símbolos
Referencias
- ^ Chomsky, Noam (1959). "Sobre ciertas propiedades formales de las gramáticas" . Información y control . 2 (2): 137-167. doi : 10.1016 / S0019-9958 (59) 90362-6 . Aquí: Sección 6, p.152ff.
- ^ a b c d e f Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8.
- ^ Hopcroft, John E .; Motwani, Rajeev; Ullman, Jeffrey D. (2006). Introducción a la teoría, los lenguajes y la computación de los autómatas (3ª ed.). Addison-Wesley. ISBN 978-0-321-45536-9. Sección 7.1.5, p.272
- ^ Rich, Elaine (2007). Autómatas, computabilidad y complejidad: teoría y aplicaciones (1ª ed.). Prentice Hall. ISBN 978-0132288064.[ página necesaria ]
- ^ Wegener, Ingo (1993). Theoretische Informatik - Eine algorítmenorientierte Einführung . Leitfäden und Mongraphien der Informatik (en alemán). Stuttgart: BG Teubner. ISBN 978-3-519-02123-0.Sección 6.2 "Die Chomsky-Normalform für kontextfreie Grammatiken", p. 149-152
- ^ a b c Lange, Martin; Leiß, Hans (2009). "¿A CNF o no a CNF? Una versión eficiente pero presentable del algoritmo CYK" (PDF) . Informatica Didactica . 8 .
- ^ Hopcroft y col. (2006) [ página necesaria ]
- ^ Floyd, Robert W. (1961). "Nota sobre la inducción matemática en gramáticas de estructura sintagmática" (PDF) . Información y control . 4 (4): 353–358. doi : 10.1016 / S0019-9958 (61) 80052-1 . Aquí: p.354
- ^ Knuth, Donald E. (diciembre de 1964). "Forma normal de Backus frente a forma de Backus Naur". Comunicaciones de la ACM . 7 (12): 735–736. doi : 10.1145 / 355588.365140 . S2CID 47537431 .
- ^ Jurafsky, Daniel; Martin, James H. (2008). Procesamiento del habla y el lenguaje (2ª ed.). Pearson Prentice Hall. pag. 465. ISBN 978-0-13-187321-6.
Otras lecturas
- Cole, Richard. Conversión de CFG a CNF (forma normal de Chomsky) , 17 de octubre de 2007. (pdf) : utiliza la orden TERM, BIN, START, DEL, UNIT.
- John Martin (2003). Introducción a los lenguajes y la teoría de la computación . McGraw Hill. ISBN 978-0-07-232200-2. (Páginas 237–240 de la sección 6.6: formas simplificadas y formas normales).
- Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación de PWS. ISBN 978-0-534-94728-6. (Páginas 98-101 de la sección 2.1: gramáticas libres de contexto. Página 156.)
- Sipser, Michael. Introducción a la Teoría de la Computación, 2ª edición.
- Alexander Meduna (6 de diciembre de 2012). Autómatas y lenguajes: teoría y aplicaciones . Springer Science & Business Media. ISBN 978-1-4471-0501-5.