Tema 3: Lenguajes independientes del contexto

Gramáticas independientes del contexto

Gramáticas independientes de contexto (GIC)

•

Conceptos básicos Ambigüedad Ejemplos de GICs

Elementos:

C om ponentes

C om ponentes form ales

C ategorias

N

conju nto de no term inales

Fu ente de entrada

Σ

alfabeto de term inales

•

Elementos distinguidos: S∈N símbolo inicial

•

Definición formal: G = (N, Σ, S, P)

Autómatas con pila (AP) Definición de autómata con pila Determinismo y no determinismo. Ejemplos. Formas normales •

Simplificación Forma normal de Greibach Equivalencia entre APs y GICs

•

con Α → β ∈P , Α∈N , β∈(N ∪ Σ)*

Paso de derivación: δ1, δ2, σ1, σ2, β ∈ (N ∪ Σ)* Α∈N δ1 ⇒ δ2 si y solo si δ1 = σ1Ασ2, δ2 = σ1βσ2 y Α → β ∈ P * w} Lenguaje generado: L(G) = { w∈Σ*: S ⇒

Propiedades y aplicaciones 1

Tema 3: Leng. Indep. del Contexto

Derivaciones •

Paso de derivación a la izquierda: δ1 ⇒ δ2 si y solo si δ1 = wΑα, δ2 = wβα y Α → β ∈ P ∈Σ * con α, β ∈ (N ∪ Σ )* , Α∈N, w∈

•

Derivación a la izquierda: * w con cada paso de derivación a la izquierda S ⇒

•

Ejemplo: Dada la G.I.C:

Árbol de derivación •

S → ASB | ε A → aAb | ε B → bBa | ba

Árbol de derivación (o de análisis) de G: Es un árbol etiquetado y ordenado tal que: - Todo nodo está etiquetado con un símbolo de N ∪ Σ ∪ {ε} - La raíz es el símbolo inicial. - Los nodos internos están etiquetados con símbolos no terminales - Si un nodo está etiquetado con A y sus k hijos están etiquetados X1 X2 … Xk (leídos de izquierda a derecha), entonces A → X1X2…Xk es una regla de la gramática. - Si un nodo está etiquetado con ε entonces es el único hijo de un nodo. Si todas las hojas son símbolos terminales ó ε entonces el árbol es completo y la frontera es una palabra de L(G).

Derivación a la izquierda de la palabra aabbba:

S ⇒ ASB ⇒ aAbSB ⇒ aaAbbSB ⇒ aabbSB ⇒ aabbB ⇒ aabbba Tema 3: Leng. Indep. del Contexto

2

3

Tema 3: Leng. Indep. del Contexto

4

Derivaciones y árboles (I) •

Ejemplo:

Derivaciones y árboles (II)

La derivación

Ejemplo:

•

Dos derivaciones a la izquierda: S ⇒ ScS ⇒ SbScS ⇒ abScS ⇒ abacS ⇒ abaca S ⇒ SbS ⇒ abS ⇒ abScS ⇒ abacS ⇒ abaca

•

Árboles de derivación:

S ⇒ ASB ⇒ aAbSB ⇒ aaAbbSB ⇒ aabbSB ⇒ aabbB ⇒ aabbba tiene como árbol de derivación S A a a

A A

S b

ε

B b

a

S → ASB | ε A → aAb | ε B → bBa | ba

S → SbS | ScS | a

•

b

S

ε Es un árbol completo con frontera: aabbba

b

a

Tema 3: Leng. Indep. del Contexto

5

1.

a

a

a

S b

S S

c

a

S a 6

Gramática G que genera el lenguaje L(G) = { w.c.wR : w ∈ {a,b}* } G = (N, Σ, S, P) con N = {S}, Σ = {a,b,c} y P formado por las siguientes reglas de producción:

•

Equivalentemente, una gramática G es ambigua si existe x∈L(G) con al menos dos derivaciones a la izquierda.

•

Un lenguaje L es inherentemente ambiguo si todas las gramáticas para dicho lenguaje son ambiguas.

S → aSa | bSb | c 2.

Gramática G que genera el lenguaje L(G) = { w.wR : w ∈ {a,b}* } G = (N, Σ, S, P) con N = {S}, Σ = {a,b} y P formado por las siguientes reglas de producción:

El lenguaje siguiente es inherentemente ambiguo: L = { aibjck | i=j ó j=k }

Tema 3: Leng. Indep. del Contexto

S

Ejemplos de GICs (I)

Una gramática G es ambigua si existe x∈L(G) con al menos dos árboles de derivación diferentes. Ej: La gramática S → SbS | ScS | a es ambigua

Ej:

S

S

Tema 3: Leng. Indep. del Contexto

Ambigüedad •

S c

S

S → aSa | bSb | ε

7

Tema 3: Leng. Indep. del Contexto

8

Ejemplos de GICs (II) 3.

Ejemplos de GICs (III)

Gramática G que genera el lenguaje L(G) = { anbn : n≥0 }

5.

G = (N, Σ, S, P) con N = {S}, Σ = {a,b} y P formado por las siguientes reglas de producción:

Primero observamos que k e i son independientes entre ellos. Usamos un nuevo no-terminal B que genere la subpalabra bk (k≥1)

S → aSb | ε 4.

Gramática G que genera el lenguaje L(G) = { aibkci : i≥0, k≥1 }

G = (N, Σ, S, P) con N = {S,B}, Σ = {a,b,c} y P formado por las siguientes reglas de producción:

Gramática G que genera el lenguaje L(G) = { anb2n : n≥0 }

S → aSc | Β B → bB | b

G = (N, Σ, S, P) con N = {S}, Σ = {a,b} y P formado por las siguientes reglas de producción: S → aSbb | ε

6.

Tema 3: Leng. Indep. del Contexto

9

¿ Gramática G que genera el lenguaje L(G) = { aibkci : i≥1, k≥0 } ?

Tema 3: Leng. Indep. del Contexto

Autómatas con pila (AP) - Elementos:

C o m p on en tes físicos

Autómatas con pila (AP) - Definición formal:

C o m p on en tes lógicos

U nidad de P roceso

Q

conjunto de estados

F uente d e entrad a

Σ

alfabeto de entrad a

P ila

Γ

alfabeto de pila

M = (Q, Σ, Γ, δ, q0, F) con (q, w, α) ∈ Q × Σ* × Γ*

q0 ∈Q: estado inicial F ⊆ Q: conjunto de estados finales pila (representada mediante Г*), la cima de la pila vacía (ε) se denota por ⊥

-Movimiento:

- Ciclo-máquina: Acciones:

•

estado actual

•

avance en la entrada

•

símbolo de entrada

•

cambio de estado

•

cima de la pila

Tema 3: Leng. Indep. del Contexto

δ : Q × Σ × (Γ ∪ {⊥}) → ℘(Q × Γ*)

-Configuración:

- Elementos distinguidos para la inicialización y aceptación:

Consultas:

10

- estado actual, palabra a leer, estado pila -

(p∈Q, s∈Σ, w∈Σ*, A∈Γ, α∈Γ*)

(p, s.w, Aα) ├── (q, w, βα)

si y solo si

(q, β) ∈ δ(p, s, A)

(p, s.w, ε) ├── (q, w, β)

si y solo si

(q, β) ∈ δ(p, s, ⊥)

- Lenguaje aceptado:

• modificación de la pila: desapilar un elemento ó desapilar un elemento y apilar uno o más

L(M) = { w∈Σ*: ∃ p∈F (q0, w, ε) ├── * (p, ε, ε) } 11

Tema 3: Leng. Indep. del Contexto

12

Ejemplo de AP

Ejemplo de AP

M = (Q, Σ, Γ, δ, q0, F) con Q = {q0 , qf } F = {qf } Γ = { A } Σ = {a,b} y δ como sigue:

M = (Q, Σ, Γ, δ, q0, F) con Q = {q0 , qf } F = {qf } Γ = { A } Σ = {a,b} y δ como sigue:

δ (q0,a,⊥) = {(q0, A), (qf, ε) }

δ (qf, a, ⊥ ) = ∅

δ (q0,a,⊥) = {(q0, A), (qf, ε) }

δ (qf, a, ⊥ ) = ∅

δ (q0, a, A) = { (q0, AA) , (qf, A) }

δ (qf, a, A) = { (qf, ε) }

δ (q0, a, A) = { (q0, AA) , (qf, A) }

δ (qf, a, A) = { (qf, ε) }

δ (q0, b, ⊥) = { (q0, A) }

δ (qf, b, ⊥ ) = ∅

δ (q0, b, ⊥) = { (q0, A) }

δ (qf, b, ⊥ ) = ∅

δ (q0, b, A) = { (q0, AA) }

δ (qf, b, A) = { (qf, ε) }

δ (q0, b, A) = { (q0, AA) }

δ (qf, b, A) = { (qf, ε) }

Cómputos posibles de M para la palabra aba:

Cómputos posibles de M para la palabra baa:

(q0, aba, ⊥) |-- (q0, ba, A) |-- (q0, a, AA) |-- (q0, ε, AAA)

(q0, baa, ⊥) |-- (q0, aa, A) |-- (q0, a, AA) |-- (q0, ε, AAA)

|-- (qf, ε, AA) |-- (qf, ba, ⊥) |-- ∅

|-- (qf, ε, AA) |-- (qf, a, A)

por tanto aba ∉ L(M)

Tema 3: Leng. Indep. del Contexto

por tanto baa ∈ L(M) 13

Determinismo y no determinismo

M = (Q, Σ, Γ, δ, q0, F) con Q = {q0 , qf } F = {qf } Γ = { A,B } Σ = {a,b,c} y δ como sigue:

- Diseñar un autómata con pila que reconozca el siguiente lenguaje:

δ (q0, a, ⊥ ) = {(q0, A)}

: w ∈ {a,b}* }

En general, a diferencia de lo que pasa entre L(AFD) y L(AFND), los lenguajes reconocidos por autómatas con pila deterministas (APD) no coinciden con los lenguajes reconocidos por autómatas con pila NO deterministas (AP): L(APD) ≠ L(AP) Tema 3: Leng. Indep. del Contexto

14

Diseñar un autómata con pila (determinista) que reconozca L = { w.c.wR : w ∈ {a,b}* }

L = { w.c.wR : w ∈ {a,b}* }

L={

Tema 3: Leng. Indep. del Contexto

Ejemplo de AP determinista

- Diseñar un autómata con pila (determinista) que reconozca el siguiente lenguaje:

w.wR

|-- (qf, ε, ε)

δ (q0, a, Β ) = {(q0, AB)}

δ (q0, b, B) = {(q0, ΒΒ)}

δ (q0, a, A) = {(q0, AA)}

δ (q0, b, A) = {(q0, BA)}

δ (q0, c, ⊥) = {(qf, ε)} δ (qf, a, A) = { (qf, ε) } 15

δ (q0, b, ⊥) = {(q0, B)}

Tema 3: Leng. Indep. del Contexto

δ (q0, c, A) = {(qf, A)}

δ (q0, c, B) = {(qf, B)}

δ (qf, b, B) = { (qf, ε) } 16

Ejemplo de AP no determinista

Formas Normales. Simplificación

Diseñar un autómata con pila que reconozca L = { w.wR : w ∈ {a,b}* }

Simplificación de GIC’s:

M = (Q, Σ, Γ, δ, q0, F) con Q = {q0 , qf } F= {q0, qf } Γ= { A,B } Σ= {a,b} y δ como sigue: δ (q0, a, ⊥ ) = {(q0, A)}

δ (q0, b, ⊥) = {(q0, B)}

δ (q0, a, Β ) = {(q0, AB)}

δ (q0, b, B) = {(q0, ΒΒ), (qf, ε)}

δ (q0, a, A) = {(q0, AA), (qf, ε)}

δ (q0, b, A) = {(q0, BA)}







δ (qf, a, A) = {(qf, ε)}

δ (qf, b, B) = {(qf, ε)}

Tema 3: Leng. Indep. del Contexto

17

Consiste en eliminar: símbolos inútiles, producciones nulas y producciones unitarias de una gramática G, con el objetivo de obtener una gramática G’, equivalente a G y tal que cada paso de derivación α ⇒ β (en G’) verifica | α | ≤ | β |

Tema 3: Leng. Indep. del Contexto

Símbolo inútil





Definiciones:

*

Símbolo accesible X

si

S

⇒

•

Símbolo fecundo X

si

X

⇒

•

Símbolo inútil = no accesible ó no fecundo

Ejemplo:

Eliminar símbolos inútiles (I)

(para símbolos no terminales: X∈N)

•

S → AB | A A → Aa | ε B → bC C → cB D→a

*

entrada: G = (N, ∑, P, S) gramática independiente de contexto salida: G2 = (N2, ∑, P2, S) equivalente a G sin símbolos inútiles

αXβ w

18

proceso:

(con w∈Σ*)

primer paso: -- Objetivo: eliminar de G los símbolos no fecundos -- Método: buscar inductivamente los símbolos fecundos, N1 • Si A → w ∈ P con w∈Σ* entonces A∈N1

¿No fecundos? B , C ¿No accesibles? D

• Si A → α ∈ P con α ∈(N1 ∪Σ)*, entonces A∈N1 -- Resultado: G1 = (N1, ∑, P1, S) con P1 = { A → α ∈ P : α∈(Σ ∪ N1)*}

Tema 3: Leng. Indep. del Contexto

19

Tema 3: Leng. Indep. del Contexto

20

Eliminar símbolos inútiles (II)

Eliminar producciones nulas (I) entrada: G = (N, Σ, P, S) independiente de contexto con S no recursivo salida: G2 = (N, Σ, P2, S) equivalente a G y tal que la única producción nula (A → ε) ∈ P2, si existe alguna, es con el símbolo inicial de la gramática: S → ε

segundo paso: -- Objetivo: eliminar de G1=(N1, ∑, P1, S) los símbolos no accesibles -- Método: buscar inductivamente los símbolos accesibles, N2 • S ∈ N2 • Si A∈N2, A → αBβ ∈P1 y B∈N1 entonces B∈N2

proceso: primer paso: -- Objetivo: construcción del conjunto de símbolos anulables

-- Resultado: G2 = (N2, ∑, P2, S) con P2 = { A → α ∈P1 : A∈N2 }

ANUL = {A ∈ N: A

*

⇒ε

}

-- Método: aplicar la definición inductiva de símbolo anulable • Si A → ε ∈ P entonces A ∈ ANUL • Si A → α ∈ P con α ∈ ANUL*, entonces A ∈ ANUL

IMPORTANTE: El orden de los pasos no es conmutativo. Tema 3: Leng. Indep. del Contexto

21

Eliminar producciones nulas (II)

22

Eliminar producciones unitarias (I)

segundo paso: -- Eliminar las producciones nulas y modificar P

entrada: G = (N, Σ, P, S) independiente de contexto sin producciones nulas salida: G1 = (N, Σ, P1, S) equivalente a G sin producciones unitarias (A → Β)

P1 := P - {A → ε : A ∈ N}; P2:= ∅; for regla in P1 loop if regla = A → X1X2…Xn then P2 := P2 ∪ { A → Y1 Y2…Yn | Yi es Xi si Xi ∉ANUL Yi es Xi ó es ε si Xi ∈ANUL Yi no es ε para todo i }; end if; end loop; if S ∈ ANUL then P2 := P2 ∪ { S → ε } end if; Tema 3: Leng. Indep. del Contexto

Tema 3: Leng. Indep. del Contexto

proceso: primer paso: -- Objetivo: construir para cada A ∈ N el conjunto UA = {B ∈ N : A -- Método: aplicar la definición inductiva:

*

⇒

B}

• A ∈ UA • Si B ∈ UA y B → C ∈ P entonces C ∈ UA 23

Tema 3: Leng. Indep. del Contexto

24

Forma Normal

Eliminar producciones unitarias (II) segundo paso: -- Construir P1 eliminando las producciones unitarias

Transformación de una GIC a forma normal:

P1 := Ø; for A in N loop for B in UA loop for regla in P loop if regla = B → α and α ∉ N then P1 := P1 ∪ {A → α }; end if; end loop; end loop; end loop; Tema 3: Leng. Indep. del Contexto

25




Estudiaremos procedimientos para: eliminar recursión a izquierdas, reemplazamientos y otros ....




con el objetivo de transformar cualquier G.I.C. G en G’, tal que G’ es equivalente a G y G’ en forma normal (de Greibach)




y obtener un AP equivalente a partir de G’ (en F.N. Greibach)

Tema 3: Leng. Indep. del Contexto

26

Recursividad

Recursividad

Producción o regla recursiva: A → αAβ * Recursividad no inmediata A ⇒ αAβ Producción o regla recursiva a la izquierda: A → Aβ * Recursividad a la izquierda A ⇒ Aβ

Las cambiamos por A → β1 A’ |...| βm A’|β1|...|βm A’ → α1 A’|...|αn A’|α1|...|αn donde A’ es un nuevo no terminal.

Eliminación de la recursividad inmediata a la izquierda de un símbolo no terminal A

La nueva gramática es equivalente y sin recursión inmediata a la izquierda para A.

Sean todas las reglas con A en el lado izquierdo (A-reglas): A → Aα1 |...| Aαn| β1|...|βm

A

donde las reglas A → βi no son recursivas a la izquierda.

Tema 3: Leng. Indep. del Contexto

27

Tema 3: Leng. Indep. del Contexto

*

⇒

(β1∪...∪βm )(α1 ∪ ... ∪ αn)∗

28

Otras transformaciones

Otras transformaciones

Reemplazamiento

Introducción de nuevos símbolos no terminales

Sea A → αBβ ∈ P una regla tal que A, B ∈N

Sea A → αβγ ∈ P una regla tal que A∈N, α,β,γ ∈ (N∪ Σ) ∗ y Z un nuevo no terminal

y sean B → β1 |...| βn todas las B-reglas ,

si eliminamos la regla A → αβγ y añadimos las reglas

si eliminamos la regla A → αBβ y añadimos las reglas

Z→β A → αZγ

A → αβ1β|...|αβnβ la nueva gramática es equivalente.

Tema 3: Leng. Indep. del Contexto

la nueva gramática es equivalente.

29

Forma normal de Greibach

30

Forma normal de Greibach (I)

Definición: Una gramática independiente del contexto G = (N, Σ, P, S) está en Forma Normal de Greibach (FNG) si todas las reglas de producción (de P) son de la forma:

entrada: G = (N, Σ, P, S) independiente de contexto simplificada salida: G3 = (N3, Σ, P3, S) en FNG equivalente a G preparación: Numeración de los no terminales y de las reglas. Elegimos una ordenación de N: A1 < A2 ]>

4560 1000€ Intel Pentium 800Mhz 256 Maxtor Diamond 30.5Gb 32x .....

Tema 3: Leng. Indep. del Contexto

43

Tema 3: Leng. Indep. del Contexto

44

GICs y Gramáticas DTD 1)

Formato DTD: Formato GIC:

2)

Procesador → Fabricante Modelo Velocidad

Formato DTD: Formato GIC: Disco → Discoduro | Cd |Dvd

3)

Formato DTD: Formato GIC:

Tema 3: Leng. Indep. del Contexto

PC → Modelo Precio Procesador Ram Discos Discos → Disco | Disco Discos 45