Home

Formas Normales

Chomsky A ® BC

A ® a

Teorema (FNC)

Sea G=<Vn, Vt, P, S>, gramática libre de contexto, existe una G’ equivalente tal que sus producciones son de la forma:

A ® BC

A ® a

Pasos

1- Eliminar producciones de la forma A ® B

2- Si existen producciones de la forma

A ® B1 B2 ...... Bm con m ³ 2 (Bi Î Vn U Vt)

hacer:

Para cada 1 £ i £ m, definir un no terminal nuevo Ci, si Bi ÎVt tal que Ci ® Bi

Por ejemplo:

Si existe:

A ® B1 B2 B3 ..... Bm donde B2 ....... Bm son no terminales

Hacer:

A ® B1 C1

C1 ® B2 ... Bm

3- Repetir 2 hasta que todas las producciones estén en FNC.

Ejemplo:

S ® bA | aB

A ® a | aS | bAA

B ® b | bS | aBB

1- No existen producciones de la forma A ® B

2- Para S ® b A hacer S ® C1 A

C1 ® b

Para S ® a B hacer S ® C2 B

C2 ® a

Para A ® a S hacer A ® C3 S

C3 ® a repite a C2

Nos queda A ® C2 S

Para A ® b A A hacer A ® C1 A A

Para B ® b S hacer B ® C1 S

Para B ® a B B hacer B ® C2 B B

Quedando

S ® C1 A | C2 B

A ® C2 S | C1 A A | a

B ® C1 S | C2 B B | b

C1 ® b

C2 ® a

Nuevamente:

Para A ® C1 A A hacer A ® C1 D1

D1 ® A A

Para B ® C2 B B hacer B ® C2 D2

D2 ® B B

Y queda:

S ® C1 A | C2 B

A ® C2 S | C1 D1 | a

B ® C1 S | C2 D2 | b

C1 ® b

C2 ® a

D1 ® A A

D2 ® B B

FORMA NORMAL DE CHOMSKY

Teorema: Forma Normal de Greibach

Toda gramática de tipo 2 tiene una gramática equivalente cuyas producciones son de la forma A ® a a ( A Î Vn, a Î Vt, a Î Vn*)

1º) Dada G = < Vn, Vt, P, S >, encontrar G1 = < Vn1, Vt1, P, S1 > en Forma normal de Chomsky equivalente.

2º) Si llamamos { A1, ...... , Am } a los no terminales de G1, deberá pasar que si

Ai ® Aj a Þ entonces i < j

Sino

Si Ai ® Aj g con i > j

entonces aplicar Lema 2 hasta que i £ j

Si Ak ® Ak g

entonces aplicar Lema 3

Al cabo del paso 2, tenemos 3 tipos de producciones

1) Ak ® Aj g con k < j

2) Ak ®a g con a Î Vt

3) Zk ® g con g Î Vn

Consideremos el mayor Am tal que

3º) Para cada producción A m-1 ® Am g

aplicar Lema 2 repetidamente para que

A m-1, A m-2, ...... A1

4º) Aplicar Lema 2 a las producciones de la forma 3 (Zk ® Ai g) hasta que

Zk ® a a

Ejemplo

S ® A B

A ® B S | b

B ® S A | a

1º paso: Encontrar Forma Normal de Chomsky Þ OK

2º paso: A1 ® A2 A3

A2 ® A3 A1 | b

A3 ® A1 A2 | a

A1 y A2 cumplen

A3 ® A1 A2 por Lema 2 A3 ® A2 A3 A2

Por Lema 2 A3 ® A3 A1 A3 A2

A3 ® b A3 A2

Ya existente A3 ® a

A3 ® A3 A1 A3 A2 tiene recursion a izquierda, por lo tanto aplico Lema 3

Por Lema 3 A3 ® a | b A3 A2

b1 b2

A3 ® A3 A1 A3 A2

a

entonces:

A3 ® a | b A3 A2 | a Z3 | b A3 A2 Z3

Z3 ® A1 A3 A2 Z3 | A1 A3 A2

Entonces G1 queda:

A1 ® A2 A3

A2 ® A3 A1 | b

A3 ® a | b A3 A2 | a Z3 | b A3 A2 Z3

Z3 ® A1 A3 A2 Z3 | A1 A3 A2

3º paso: (Mayor Am = A3)

A2 ® A3 A1 por lema 2 A2 ® a A1

A2 ® b A3 A2 A1

A2 ® a Z3 A1

A2 ® b A3 A2 Z3 A1

Ya existente A2 ® b

A1 ® A2 A3 por lema 2 A1 ® a A1 A3

A1 ® b A3 A2 A1 A3

A1 ® a Z3 A1 A3

A1 ® b A3 A2 Z3 A1 A3

A1 ® b A3

Entonces G’’ queda:

A1 ® a A1 A3 | b A3 A2 A1 A3 | a Z3 A1 A3

A1 ® b A3 A2 Z3 A1 A3 | b A3

A2 ® a A1 | b A3 A2 A1 | a Z3 A1 | b A3 A2 Z3 A1 | b

A3 ® a | b A3 A2 | a Z3 | b A3 A2 Z3

Z3 ® A1 A3 A2 Z3 | A1 A3 A2

4º paso:

Z3 ® A1 A3 A2

Z3 ® A1 A3 A2 Z3

Por lema 2 Z3 ® a A1 A3 A3 A2

Z3 ® b A3 A2 A1 A3 A3 A2

Z3 ® a Z3 A1 A3 A3 A2

Z3 ® b A3 A2 Z3 Z1 A3 A3 A2

Z3 ® b A3 A3 A2

Por lema 2

Z3 ® a A1 A3 A3 A2 Z3

Z3 ® b A3 A2 A1 A3 A3 A2 Z3

Z3 ® a Z3 A1 A3 A3 A2 Z3

Z3 ® b A3 A2 Z3 A1 A3 A3 A2 Z3

Z3 ® b A3 A3 A2 Z3

Finalmente queda:

A1 ® a A1 A3 | b A3 A2 A1 A3 | a Z3 A1 A3

A1 ® b A3 A2 Z3 A1 A3 | b A3

A2 ® a A1 | b A3 A2 A1 | a Z3 A1 | b A3 A2 Z3 A1 | b

A3 ® a | b A3 A2 | a Z3 | b A3 A2 Z3

Z3 ® a A1 A3 A3 A2 | b A3 A2 A1 A3 A3 A2 | a Z3 A1 A3 A3 A2

Z3 ® b A3 A2 Z3 Z1 A3 A3 A2 | b A3 A3 A2 | a A1 A3 A3 A2 Z3

Z3 ® b A3 A2 A1 A3 A3 A2 Z3 | a Z3 A1 A3 A3 A2 Z3

Z3 ® b A3 A2 Z3 A1 A3 A3 A2 Z3 | b A3 A3 A2 Z3

Apéndice - Lemas adicionales

Lema 2

Sea G una gramática libre de contexto <Vn, Vt, P, S>, llamaremos A a una producción que tenga A a la izquierda. Por ejemplo:

A à α1 B α2 Î P B Î Vn A ¹ B

y sea B el conjunto de todas las producciones de B

B = {B à β1, B à β2,..... B à βn } β1..βn Î Vn È Vt

Si construimos una G1, cambiando P por P1 donde P1 se obtiene de P al borrar

A à α1 B α2

y agregar

{A à α1 β1 α2, A à α1 β2 α2,..... A à α1 βn α2}

entonces G1 es equivalente a G

Lema 3: de eliminación de recursión a izquierda.

Sea G una gramática libre de contexto <Vn, Vt, P, S>.

Sea A el conjunto de producciones de A particionadas de la siguiente manera:

A1 = { A à A α1, A à A α2, ...... , A à A αn }

A2 = { A à β1, A à β2, ...... , A à βs } con βi ¹ Ag

Es decir, divido las producciones A en dos conjuntos: las que en su lado derecho tienen a A como primer elemento, y aquellas cuyo lado derecho comienza con cualquier cosa que no sea A.

Si construimos G1 <Vn È {Z}, Vt, P1, S > donde P1 se obtiene de P al reemplazar A por A’:

A’ = { A à β1, A à β2, ...... , A à βs } È

{ A à β1 Z, A à β2 Z, ...... , A à βs Z } È

{ Z à α1 Z, Z à α2 Z, ...... , Z à αn Z } È

{ Z à α1, Z à α2, ...... , Z à αn }

entonces G1 es equivalente a G.