Forma normal de Chomsky

Notación para gramáticas formales libres de contexto

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: ^{[2] [3]}

A → antes de Cristo , 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 inicial y ε denota la cadena vacía . Además, ni B ni C pueden ser el símbolo inicial , y la tercera regla de producción sólo puede aparecer si ε está en L ( G ), el lenguaje producido por la gramática libre de contexto G. ^{[4] : 92–93, 106}

Cada gramática en forma normal de Chomsky está libre de contexto y, a la inversa, cada gramática libre de contexto se puede transformar en una equivalente [ ^{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 original. .

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 orden determinado; esto se describe en la mayoría de los libros de texto sobre teoría de autómatas . ^{[4] : 87–94  [5] [6] [7]} La ​​presentación aquí sigue a Hopcroft, Ullman (1979), pero está adaptada para usar los nombres de transformación de Lange, Leiß (2009). ^{[8] [nota 2]} 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 del lado derecho

Introducir un nuevo símbolo de inicio S ₀ y una nueva regla

S ₀ → S ,

donde S es el símbolo de inicio anterior. Esto no cambia el lenguaje producido por la gramática y S ₀ no aparecerá en el lado derecho de ninguna regla.

PLAZO: Eliminar reglas con terminales no solitarias

Para eliminar cada regla

A → X ₁ ... a ... X _n

Dado que el símbolo terminal a no es el único símbolo en el lado derecho, introduzca, para cada terminal, un nuevo símbolo no terminal N _a y una nueva regla.

norte _un → un .

Cambia cada regla

A → X ₁ ... a ... X _n

a

A → X ₁ ... N _un ... X _norte .

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. ^{[4] : 92}

BIN: Eliminar los lados derechos con más de 2 no terminales

Reemplazar cada regla

A → X ₁ X ₂ ... X _n

con más de 2 no terminales X ₁ ,..., X _n por reglas

UN → X ₁ UN ₁ ,

Un ₁ → X ₂ Un ₂ ,

... ,

Un _{norte -2} → X _{norte -1} X _norte ,

donde Ai son nuevos símbolos no terminales _. Nuevamente, esto no cambia el lenguaje producido por la gramática. ^{[4] : 93}

DEL: Eliminar reglas ε

Una regla ε es una regla de la forma

A → ε,

donde A no es S ₀ , el símbolo inicial 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 ₁ ... X _n , y cada X _i es anulable, entonces A también es anulable.

Obtener una gramática intermedia reemplazando cada regla

A → X ₁ ... X _norte

por todas las versiones con alguna X anulable _{que se} omite. Al eliminar en esta gramática cada regla ε, a menos que su lado izquierdo sea el símbolo inicial, se obtiene la gramática transformada. ^{[4] : 90}

Por ejemplo, en la siguiente gramática, con el símbolo inicial S ₀ ,

S ₀ → AbB | C

B → AA | C.A.

C → segundo | C

Un → un | ε

el no terminal A , y por tanto también B , es anulable, mientras que ni C ni S ₀ lo son. De ahí se obtiene la siguiente gramática intermedia: ^{[nota 3]}

S ₀ → A segundo segundo | A b B | A b B | A b B   |   C

B → AA | Una Una | Una Una | A ε A   |   A C | A C

C → segundo | C

Un → un | ε

En esta gramática, todas las reglas ε se han " integrado en el sitio de llamada". ^{[nota 4]} En el siguiente paso, se pueden eliminar, lo que da como resultado la gramática:

S ₀ → AbB | abdominales | bB | segundo   |   C

B → AA | Un   |   Aire acondicionado | C

C → segundo | C

Un → un

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: Eliminar reglas de unidad

Una regla unitaria es una regla de la forma

A → B ,

donde A , B son símbolos no terminales. Para eliminarlo, para cada regla.

segundo → X ₁ ... X _norte ,

donde X ₁ ... X _n es una cadena de terminales y no terminales, agregue la regla

A → X ₁ ... X _norte

a menos que se trate de una regla de unidad que ya haya sido (o esté siendo) eliminada. La omisión del símbolo no terminal B en la gramática resultante es posible debido a que B es miembro del cierre unitario del símbolo no terminal A. ^[9]

Orden de transformaciones

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 reintroducirá una regla de unidad si se aplica después de UNIT . La tabla muestra qué pedidos se admiten.

Además, el aumento en el tamaño de la gramática en el peor de los casos ^{[nota 5]} depende del orden de transformación. Usando | GRAMO | para denotar el tamaño de la gramática original G , el tamaño ampliado en el peor de los casos puede oscilar entre | GRAMO | ² a 2 ^{2 |G|} , dependiendo del algoritmo de transformación utilizado. ^{[8] : 7} La ampliación del tamaño gramatical depende del orden entre DEL y BIN . Puede ser exponencial cuando DEL se realiza primero, pero es lineal en caso contrario. UNIT puede incurrir en una explosión cuadrática en el tamaño de la gramática. ^{[8] : 5} Los ordenamientos INICIO , TERM , BIN , DEL , UNIT y START , BIN , DEL , UNIT , TERM conducen a la mínima explosión (es decir, cuadrática).

Ejemplo

Árbol de sintaxis abstracta de la expresión aritmética " a ^2+4* b " wrt. el ejemplo de gramática ( arriba ) y su forma normal de Chomsky ( abajo )

La siguiente gramática, con el símbolo inicial 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 el número como la variable se consideran símbolos terminales aquí por simplicidad, ya que en la interfaz del compilador su estructura interna generalmente no es considerada por el analizador . El símbolo terminal "^" denota exponenciación en Algol60.

En el paso "INICIO" del algoritmo de conversión anterior, solo se agrega una regla S ₀ → Expr a la gramática. Después del paso "TERM", la gramática tiene este aspecto:

Después del paso "BIN", se obtiene la siguiente gramática:

Como no existen reglas ε, el paso "DEL" no cambia la gramática. Después del paso "UNIDAD", se obtiene la siguiente gramática, que está en forma normal de Chomsky:

Los Na _introducidos en el paso "TERM" son PowOp , Open y Close . Los Ai _introducidos en el paso "BIN" son AddOp_Term , MulOp_Factor , PowOp_Primary y Expr_Close .

Definición alternativa

Forma reducida de Chomsky

Otra forma ^{[4] : 92  [10]} 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:

${\displaystyle A\rightarrow \,BC}$o

${\displaystyle A\rightarrow \,a}$,

donde , y son símbolos no terminales, y es un símbolo terminal . Cuando se utiliza esta definición, o puede ser el símbolo de inicio. Sólo aquellas gramáticas libres de contexto que no generan la cadena vacía pueden transformarse a la forma reducida de Chomsky. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle a}$ ${\displaystyle B}$ ${\displaystyle C}$

forma normal de floyd

En una carta en la que proponía un término forma Backus-Naur (BNF), Donald E. Knuth implicaba una "sintaxis BNF en la que todas las definiciones tienen esa forma, se puede decir que está en 'forma normal Floyd'",

${\displaystyle \langle A\rangle ::=\,\langle B\rangle \mid \langle C\rangle }$o

${\displaystyle \langle A\rangle ::=\,\langle B\rangle \langle C\rangle }$o

${\displaystyle \langle A\rangle ::=\,a}$,

donde , 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. ^[11] Pero retiró este término, "ya que sin duda muchas personas han usado este término de forma independiente". Es un hecho simple en su propio trabajo, y el punto es sólo incidental respecto de las consideraciones principales de la nota de Floyd". ^[12] Mientras que la nota de Floyd cita el artículo original de Chomsky de 1959, la carta de Knuth no lo hace. ${\displaystyle \langle A\rangle }$ ${\displaystyle \langle B\rangle }$ ${\displaystyle \langle C\rangle }$ ${\displaystyle a}$

Solicitud

Además de su importancia teórica, la conversión CNF se utiliza en algunos algoritmos como paso de preprocesamiento, por ejemplo, el algoritmo CYK , un análisis ascendente para gramáticas libres de contexto, y su variante probabilística CKY. ^[13]

Ver también

• Forma Backus-Naur
• algoritmo CYK
• Forma normal de Greibach
• Forma normal de Kuroda
• Lema de bombeo para lenguajes libres de contexto : su prueba se basa en la forma normal de Chomsky

Notas

1. es decir, uno que produce el mismo idioma
2. Por ejemplo, Hopcroft, Ullman (1979) fusionó TERM y BIN en una sola transformación.
3. indicando un N no terminal mantenido y omitido por N y N , respectivamente
4. Si la gramática tuviera una regla S ₀ → ε, no podría estar "incorporada", ya que no tenía "sitios de llamada". Por lo tanto, no se pudo eliminar en el siguiente paso.
5. es decir, longitud escrita, medida en símbolos

Referencias

1. 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.152 y siguientes.
2. D'Antoni, Loris. "Página 7, Conferencia 9: Algoritmos de análisis ascendente" (PDF) . CS536-S21 Introducción a lenguajes de programación y compiladores . Universidad de Wisconsin-Madison. Archivado (PDF) desde el original el 19 de julio de 2021.
3. Sipser, Michael (2006). Introducción a la teoría de la computación (2ª ed.). Boston: Tecnología del curso Thomson. Definición 2.8. ISBN 0-534-95097-3. OCLC  58544333.
4. Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a la teoría de los autómatas, los lenguajes y la computación. Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8.
5. 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
6. Rico, Elaine (2007). "11.8 Formas normales". Autómatas, computabilidad y complejidad: teoría y aplicaciones (PDF) (1ª ed.). Prentice Hall. pag. 169.ISBN​ 978-0132288064. Archivado desde el original (PDF) el 17 de enero de 2023.
7. Wegener, Ingo (1993). Theoretische Informatik: un algoritmo orientado a la configuración . 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
8. Lange, Martín; Leiß, Hans (2009). "¿A CNF o no a CNF? Una versión eficiente pero presentable del algoritmo CYK" (PDF) . Informática Didáctica . 8 . Archivado (PDF) desde el original el 19 de julio de 2011.
9. Allison, Charles D. (2022). Fundamentos de la informática: una introducción accesible a los autómatas y los lenguajes formales . Fuentes frescas, Inc. pág. 176.ISBN​ 9780578944173.
10. Hopcroft y col. (2006) ^{[ página necesaria ]}
11. Floyd, Robert W. (1961). "Nota sobre la inducción matemática en gramáticas de estructura de frases" (PDF) . Información y Control . 4 (4): 353–358. doi : 10.1016/S0019-9958(61)80052-1 . Archivado (PDF) desde el original el 5 de marzo de 2021.Aquí: p.354
12. 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.
13. Jurafsky, Daniel; Martín, 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, Ricardo. Conversión de CFG a CNF (forma normal de Chomsky) , 17 de octubre de 2007. (pdf): utiliza el orden TERM, BIN, START, DEL, UNIT.
• Juan Martín (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 a 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 PWS. ISBN 978-0-534-94728-6. (Páginas 98 a 101 de la sección 2.1: gramáticas libres de contexto. Página 156.)
• Charles D. Allison (2021) (20 de agosto de 2021). Fundamentos de la informática: una introducción accesible al lenguaje formal . Fuentes frescas, Inc. ISBN 9780578944173.{{cite book}}: Mantenimiento CS1: nombres numéricos: lista de autores ( enlace ) (páginas 171-183 de la sección 7.1: Forma normal de Chomsky)
• 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. Medios de ciencia y negocios de Springer. ISBN 978-1-4471-0501-5.