• Author / Uploaded
• danque

Citation preview

Práctica 2.4: Formas Normales o Canónicas 1 Introducción Las producciones de una gramática de contexto libre, según su definición, tienen una estructura sencilla. El antecedente es un símbolo no terminal, y la única restricción para el consecuente es que no sea la palabra vacía. En múltiples ocasiones es conveniente que la parte derecha de las producciones, que, en principio puede ser una palabra cualquiera, no vacía, con símbolos terminales y no terminales en cualquier orden y número, tenga una estructura más rígida o que responda a una determinada forma. Por ello, se definen diferentes estructuras de los consecuentes de las producciones de una gramática de contexto libre, denominándose a las gramáticas cuyas producciones responden a un determinado tipo de estructura, gramática en forma normal o estándar. Puede ser el caso de demostrar determinadas propiedades de los lenguajes independientes del contexto, para lo cual puede ser útil que la gramática de contexto libre que genera un determinado lenguaje se suponga esté en forma normal de Chomsky, o en problemas de análisis sintáctico, en los que interesa que las gramáticas que se utilizan no sean recursivas por la izquierda, para lo que es conveniente utilizar gramáticas en forma normal de Greibach. Estos dos tipos de formas normales, la forma normal de Chomsky y la forma normal de Greibach son las más utilizadas, y sobre ellas trata esta práctica.

2 Forma Normal de Chomsky Definición: Una gramática de contexto libre (o gramática independiente del contexto, o gramática tipo 2) se dice que está en forma normal de Chomsky cuando sus producciones son de la forma

ó ó (eventualmente)

A ::= BC, A ::= a, S ::= λ

Algoritmo: Para obtener una gramática en forma normal de Chomsky equivalente a una gramática de contexto libre : • Se parte de una gramática independiente del contexto bien formada. • Paso 1 : Para aquellas producciones A ::= x, |x| ≥ 2, que no responden a la forma normal de Chomsky, en conjunto, se cambian los símbolos terminales bi que

aparezcan por símbolos no terminales nuevos Xi y se añaden las producciones Xi ::= bi. • Paso 2 : Cada producción de la forma A ::= B1 B2… Bk, k > 2, se reemplaza por: A ::= B1 Y1 Y1 ::= B2 Y2 ............ Yk-2 ::= Bk-1 Bk donde Y1, Y2, …, Yk-2 son nuevos símbolos no terminales.

Se ve de forma bastante intuitiva que la gramática obtenida con este proceso es equivalente a la gramática de la que se parte.

1 Ejercicio 1: Obtener una gramática en FN Chomsky equivalente a la siguiente gramática: S ::= 1A | 1B A ::= 0 | 0S | 1AA B ::= 1 | 1S | 0BB

2

Ejercicio 2:

Sea la gramática

S ::= A | λ A ::= ABBA | a B ::= bCb C ::= c

1,- Obtener una gramática bien formada equivalente. 2.- Obtener una gramática en FN Chomsky equivalente. Examen junio 2003

3 En el ejercicio anterior sería posible obtener otra gramática, también en FN Chomsky con menos producciones, si se hace alguna pequeña transformación previa. Sugerir y formalizar alguna condición y las correspondientes transformaciones para obtener gramáticas en FN Chomsky más reducidas.

3 Forma Normal de Greibach Definición: Una gramática de contexto libre se dice que está en forma normal de Greibach si sus producciones son de la forma A ::= ax a ∈ ΣT x ∈ ΣN* S ::= λ es decir, salvo la producción S ::= λ, el consecuente de todas las producciones es un símbolo terminal seguido de una palabra formada solamente por símbolos no terminales que puede ser vacía ( A ::= aBCDN ó A ::= a).

4 Para la siguiente gramática indicar qué producciones no están en forma normal de Greibach: S ::= SBA ⏐ABaB A ::= Sb ⏐ b B ::= aBa ⏐b 5 a) Obtener una gramática G1 que genere el lenguaje L = { x ∈ {a,b}* ⏐ x es capicúa} b) Obtener una gramática G2 equivalente en forma normal de Greibach. c) Obtener una gramática G3 equivalente en forma normal de Chomsky. (Examen febrero 2008)