Gramáticas y Modelos Matemáticos - Clase 3

ING. JORGE BUABUD

GRAMÁTICAS Y MODELOS MATEMÁTICOS

U.T.N. – F.R.T. S. y S. de los L.

JERARQUÍA DE CHOMSKY:

Gramática Lenguaje Modelo Matemático

Tipo 0: IrrestrictaRecursivamente

enumerable

(Nivel Pragmático)

Máquina de Turing (MT)

Tipo 1: Dependiente del Contexto

Dependiente del Contexto

(Nivel Semántico)

Autómata Linealmente Limitado (ALL)

Tipo 2: Independiente del Contexto

Independiente del Contexto

(Nivel Sintáctico)Autómata de Pila (AP)

Tipo 3: RegularRegular

(Nivel Léxico)Autómata Finito (AF)

ING. JORGE BUABUD




Esta clasificación, realizada por Noam Chomsky a fines de la década de 1950, implica una jerarquía de los lenguajes generados por las gramáticas de cada tipo, ya que cada gramática de tipo X surge de aplicar ciertas restricciones al tipo X-1. De tal modo que el conjunto de lenguajes recursivamente enumerables contiene al conjunto de lenguajes dependientes del contexto, éste contiene a los lenguajes independientes del contexto y éstos a los regulares:

LLLL0 ⊃⊃⊃⊃ LLLL1 ⊃⊃⊃⊃ LLLL2 ⊃⊃⊃⊃ LLLL3

ING. JORGE BUABUD




TIPO 0 (Irrestricta o Sin Restricciones - GI): Gramática estructurada por frases sin ninguna restricción.

O sea que sus reglas de producción tienen, en la parte izquierda al menos un símbolo no terminal y en la parte derecha cualquier secuencia de terminales o no-terminales, inclusive vacía.

Todo lenguaje formal generado por una GI y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Irrestricto o Recursivamente Enumerable (LI).

ING. JORGE BUABUD




Ejemplo de Gramática Tipo 0:

G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S ⟩⟩⟩⟩ΣΣΣΣN = { S, U, V, X, Y, Z } ΣΣΣΣT = {a, b}P: S → → → → UVX bV→→→→ Vb

ZX →→→→ VbX YX →→→→ VaXYb →→→→ bY Ya →→→→ aYZb →→→→ bZ Za →→→→ aZX →→→→ λ aV →→→→ VaUV →→→→ bUZ | aUY | λ

El lenguaje generado por esta gramática es:

L(G) = {ww / w∈Σ∈Σ∈Σ∈ΣT* }

ING. JORGE BUABUD




Veamos la generación de algunas palabras:

S ⇒⇒⇒⇒ UVX ⇒⇒⇒⇒ X ⇒⇒⇒⇒ λ

S ⇒⇒⇒⇒ UVX ⇒⇒⇒⇒ aUYX ⇒⇒⇒⇒ aUVaX ⇒⇒⇒⇒ aaX⇒⇒⇒⇒ aa

S ⇒⇒⇒⇒ UVX ⇒⇒⇒⇒ bUZX ⇒⇒⇒⇒ bUVbX ⇒⇒⇒⇒ baUYbX ⇒⇒⇒⇒ baUbYX ⇒⇒⇒⇒ baUbVaX ⇒⇒⇒⇒ baUVbaX ⇒⇒⇒⇒ babaX⇒⇒⇒⇒ baba

ING. JORGE BUABUD




TIPO 1 (Dependiente del / Sensible al Contexto - GDC): Gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte derecha, la cual no puede ser menor que la longitud de la parte izquierda. O sea que no tienen reglas compresoras. Excepto la regla de borrado S → λ , siempre que S no figure a la derecha de ninguna regla, con el único objetivo de generar la palabra vacía.

Todo lenguaje formal generado por una GDC y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Dependiente del Contexto (LDC).

ING. JORGE BUABUD





G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S ⟩⟩⟩⟩ΣΣΣΣN = { S, T, B, D } ΣΣΣΣT = { a, b, c }P: S → → → → T

DB →→→→ BDD →→→→ cT →→→→ aTBD | abDbB →→→→ bb


L(G) = {an bn cn / n ≥ ≥ ≥ ≥ 1 }

ING. JORGE BUABUD





S ⇒⇒⇒⇒ T ⇒⇒⇒⇒ abD⇒⇒⇒⇒ abc

S ⇒⇒⇒⇒ T ⇒⇒⇒⇒ aTBD ⇒⇒⇒⇒ aabDBD⇒⇒⇒⇒ aabBDD⇒⇒⇒⇒ aabbDD⇒⇒⇒⇒ aabbcD⇒⇒⇒⇒ aabbcc

S ⇒⇒⇒⇒ T ⇒⇒⇒⇒ aTBD ⇒⇒⇒⇒ aaTBDBD⇒⇒⇒⇒ aaabDBDBD⇒⇒⇒⇒aaabBDDBD⇒⇒⇒⇒ aaabbDDBD⇒⇒⇒⇒ aaabbDBDD⇒⇒⇒⇒aaabbBDDD⇒⇒⇒⇒ aaabbbDDD⇒⇒⇒⇒* aaabbbccc

ING. JORGE BUABUD




TIPO 2 (Independiente / Libre del Contexto - GIC): Gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte izquierda, que debe ser igual a 1. O sea que la parte izquierda es un no-terminal y la parte derecha puede ser cualquier secuencia de terminales o no-terminales.

Todo lenguaje formal generado por una GIC y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Independiente del Contexto (LIC).

ING. JORGE BUABUD





G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S ⟩⟩⟩⟩

ΣΣΣΣN = { S } ΣΣΣΣT = { a, b }

P: S → → → → aSb | ab


L(G) = {an bn / n ≥ ≥ ≥ ≥ 1 }

ING. JORGE BUABUD





S ⇒⇒⇒⇒ ab

S ⇒⇒⇒⇒ aSb⇒⇒⇒⇒ aabb

S ⇒⇒⇒⇒ aSb⇒⇒⇒⇒ aaSbb⇒⇒⇒⇒ aaabbb

ING. JORGE BUABUD




TIPO 3 (Lineal / Regular - GR): Gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte izquierda, que debe ser igual a 1. O sea que la parte izquierda es un no-terminal y la parte derecha puede ser una secuencia de terminales con un no-terminal como sufijo (GR por la derecha) o con un no-terminal como prefijo (GR por la izquierda) o simplemente una secuencia de terminales.

Existe una equivalencia entre ambas formas.

Todo lenguaje formal generado por una GR por la derecha o por laizquierda, se llama Lenguaje Regular (LR).

ING. JORGE BUABUD




Ejemplo de Gramática Tipo 3 (regular por derecha):

G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S ⟩⟩⟩⟩

ΣΣΣΣN = { S, A } ΣΣΣΣT = { a, b }

P: S → → → → bbS | aaAA →→→→ aaA | bb


L(G) = {(bb)n (aa)k bb / n≥≥≥≥0, k≥≥≥≥1}

ING. JORGE BUABUD





S ⇒⇒⇒⇒ aaA⇒⇒⇒⇒ aabb

S ⇒⇒⇒⇒ aaA⇒⇒⇒⇒ aaaaA⇒⇒⇒⇒ aaaabb

S ⇒⇒⇒⇒ bbS⇒⇒⇒⇒ bbaaA⇒⇒⇒⇒ bbaabb

S ⇒⇒⇒⇒ bbS⇒⇒⇒⇒ bbaaA⇒⇒⇒⇒ bbaaaaA⇒⇒⇒⇒ bbaaaabb

ING. JORGE BUABUD




Ejemplo de Gramática Tipo 3 (regular por izquierda):

G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S ⟩⟩⟩⟩

ΣΣΣΣN = { S } ΣΣΣΣT = { a, b }

P: S → → → → Sab | Sba | aaa | bbb


L(G) = {aaa, bbb}.{ab,ba}*

ING. JORGE BUABUD





S ⇒⇒⇒⇒ Sab⇒⇒⇒⇒ aaaab

S ⇒⇒⇒⇒ Sba⇒⇒⇒⇒ Sabba⇒⇒⇒⇒ bbbabba

S ⇒⇒⇒⇒ Sba⇒⇒⇒⇒ Sbaba⇒⇒⇒⇒ Sabbaba⇒⇒⇒⇒ aaaabbaba

S ⇒⇒⇒⇒ Sab⇒⇒⇒⇒ Sabab⇒⇒⇒⇒ Sbaabab⇒⇒⇒⇒ bbbbaabab

ING. JORGE BUABUD



FORMATOS ESTÁNDARES:

Para todas las gramáticas se puede definir un formato estándar, de tal modo que las reglas de producción adopten formas más comprensibles o más fáciles de implementar con un computador. Como veremos en algunos casos el formato de las reglas puede poner en evidencia características del lenguaje generado por las mismas. Por ejemplo en las de Tipo 1 se puede apreciar la dependencia del contexto en la derivación de las palabras.En otros casos las reglas de borrado (N→→→→λ) pueden traer como consecuencia la posibilidad de derivaciones arbitrariamentelargas. Por ejemplo la siguiente gramática de Tipo 2 que genera paréntesis bien balanceados (damos sólo las reglas):

1. S→→→→ SS 2. S →→→→ (S) 3. S →→→→ λ

ING. JORGE BUABUD



FORMATOS ESTÁNDARES:

Con esta gramática es posible hacer derivaciones arbitrariamente largas de una palabra tan sencilla como “( )” (el subíndice de las flechas indica la regla utilizada):

S ⇒⇒⇒⇒1 SS ⇒⇒⇒⇒1 SSS ⇒⇒⇒⇒1 . . . ⇒⇒⇒⇒3 SSS ⇒⇒⇒⇒3 SS ⇒⇒⇒⇒3 S ⇒⇒⇒⇒2 (S) ⇒⇒⇒⇒3 ( )

Si pudiéramos tener una gramática equivalente, pero sin reglas que produzcan la cadena vacía, ya no sería posible hacer derivaciones arbitrariamente largas. Esto puede ser una ventaja a la hora de determinar si una palabra se deriva o no de una gramática, o sea en el proceso de análisis del lenguaje generado por la gramática.

ING. JORGE BUABUD



FORMATO ESTÁNDAR DE TIPO 0:

En el caso de las gramáticas de tipo 0 o irrestrictas, se puede transformar las reglas para obtener una gramática equivalente de la forma:

N1N2....Ni →→→→ M1M2....Mj | λ

N →→→→ t

La transformación consiste en reemplazar todos los terminales de las reglas que no cumplen con este formato, por nuevos símbolos no-terminales y agregar reglas de la forma “nuevo no-terminal deriva a terminal correspondiente”.

F.E.T.0 donde “t” es un terminal y los “N” y “M” son no-terminales.

ING. JORGE BUABUD



FORMATO ESTÁNDAR TIPO 0:

Por ejemplo, la GI vista anteriormente quedaría:

G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S ⟩⟩⟩⟩ ΣΣΣΣN = { S, A, B, U, V, X, Y, Z } ΣΣΣΣT = {a, b}

P: S → → → → UVX BV →→→→ VBZX →→→→ VBX YX →→→→ VAX

YB →→→→ BY YA →→→→ AYZB →→→→ BZ ZA →→→→ AZ

X →→→→ λ AV →→→→ VA

UV →→→→ BUZ | AUY | λ A →→→→ aB →→→→ b

ING. JORGE BUABUD




En el caso de las gramáticas de tipo 1 o dependientes del contexto, se puede transformar las reglas para obtener una gramática equivalente de la forma:

αααα1 N αααα2 →→→→ αααα1 β β β β αααα2

S →→→→ λ

Podemos decir que N puede reemplazarse por ββββ siempre que N estéen el contexto (αααα1 , αααα2). En este formato se pone de manifiesto la dependencia del contexto de este tipo de gramática.Recordemos que la excepción “S →→→→ λ” solo sirve para generar la palabra vacía, cuando así lo requiera el lenguaje.

F.E.T.1N ∈∈∈∈ ΣΣΣΣN , ββββ ∈∈∈∈ ΣΣΣΣ+ , ααααi ∈∈∈∈ ΣΣΣΣ*

Pero S no figura a la derecha de ninguna regla de producción.

ING. JORGE BUABUD




La transformación de las reglas que no cumplen con el formato estándar, se puede formalizar mediante los siguientes pasos:

1) Obtener el “F.E.T. 0” de las reglas en cuestión.

2) Para cada regla de la forma:

X1X2...XL →→→→ Z1Z2...ZK

donde los (Xi , Zj) son no-terminales, se debe agregar los no-terminales nuevos Y1, Y2, ... , YL y reemplazarla por las siguientes producciones:

ING. JORGE BUABUD




X1X2...XL →→→→ Y1X2...XL

Y1X2X3...XL →→→→ Y1Y2X3...XL..............................

Y1Y2...YL-1 XL →→→→ Y1Y2...YL-1YLZL+1...ZK

Y1Y2...YL-1YLZL+1...ZK →→→→ Z1Y2...YLZL+1...ZK..............................

Z1Z2...ZL-1YLZL+1...ZK →→→→ Z1Z2...ZK

Se puede verificar que estas reglas cumplen con el formato estándar de tipo 1 y que son equivalentes a la regla de partida.

ING. JORGE BUABUD




Apliquemos estos pasos al ejemplo de GDC visto anteriormente:

1) La única regla que no cumple con el formato estándar es:DB →→→→ BD, y ya está en el “F.E.T. 0”.

2) Agregamos los nuevos no-terminales: E, Fy reemplazamos la regla en cuestión por las siguientes producciones:

DB →→→→ EBEB →→→→ EFEF →→→→ BFBF →→→→ BD

ING. JORGE BUABUD




De tal modo que la GDC equivalente resulta ser:

G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S ⟩⟩⟩⟩ ΣΣΣΣN = { S, T, B, D, E, F } ΣΣΣΣT = { a, b, c }

P: S → → → → T DB →→→→ EB

EB →→→→ EFEF →→→→ BF

BF →→→→ BDD →→→→ c

T →→→→ aTBD | abD

bB →→→→ bb

ING. JORGE BUABUD




Veamos ahora un ejemplo arbitrario de una regla de tipo 1, que no cumple con el formato estándar: aXb→→→→ YcZde

1) Agregamos los nuevos no-terminales: A, B, C, D, Ey reemplazamos la regla por las siguientes producciones:

AXB →→→→ YCZDEA →→→→ aB →→→→ bC →→→→ cD →→→→ dE →→→→ e

ING. JORGE BUABUD




2) Agregamos los nuevos no-terminales: F, G, Hy reemplazamos la regla : AXB →→→→ YCZDE por las siguientes producciones:

AXB →→→→ FXBFXB →→→→ FGBFGB →→→→ FGHDE

FGHDE →→→→ YGHDEYGHDE →→→→ YCHDEYCHDE →→→→ YCZDE

ING. JORGE BUABUD




De tal modo que la regla de partida se sustituye por las siguientes producciones:

AXB →→→→ FXB A →→→→ aFXB →→→→ FGB B →→→→ bFGB →→→→ FGHDE C →→→→ c

FGHDE →→→→ YGHDE D →→→→ dYGHDE →→→→ YCHDE E →→→→ eYCHDE →→→→ YCZDE

Como vemos todas las reglas cumplen con el formato dependiente del contexto.

ING. JORGE BUABUD




Analicemos ahora el problema de agregar la generación de lapalabra vacía a una GDC que originalmente no la genera.

Se presentan dos casos:

1) Si ninguna de las producciones de la GDC contiene el axioma en su parte derecha, se agrega la regla de borrado: S →→→→ λ

como excepción de regla compresora, que tendrá como único efecto permitir la derivación de la palabra vacía.

2) Si el axioma aparece en la derecha de alguna producción, entonces se realiza el siguiente artificio: a) se introduce un nuevo símbolo inicial S1b) se agrega a las producciones originales las reglas: S1 →→→→ S | λ

ING. JORGE BUABUD




En el ejemplo de GDC que hemos visto, se presenta el primer caso.De tal modo que si deseamos agregar la generación de la palabra vacía, la gramática resultante sería:

G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S ⟩⟩⟩⟩

ΣΣΣΣN = { S, T, B, D } ΣΣΣΣT = { a, b, c }P: S → → → → T | λ

DB →→→→ BDD →→→→ c

T →→→→ aTBD | abDbB →→→→ bb


L(G) = {an bn cn / n ≥ ≥ ≥ ≥ 0 }

ING. JORGE BUABUD




Veamos por último un ejemplo del segundo caso:

G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S ⟩⟩⟩⟩ΣΣΣΣN = { S, A } ΣΣΣΣT = { a, b }

P: S →→→→ bSbb | SAS

Sb →→→→ aaAA →→→→ bb

SA →→→→ aa¿ Qué lenguaje genera esta gramática ?

ING. JORGE BUABUD




La GDC equivalente que genera la palabra vacía es:

G = ⟨⟨⟨⟨ ΣΣΣΣN , ΣΣΣΣT , P, S1 ⟩⟩⟩⟩

ΣΣΣΣN = { S1, S, A } ΣΣΣΣT = { a, b }

P: S1 →→→→ S | λ

S →→→→ bSbb | SASSb →→→→ aaA

A →→→→ bb

SA →→→→ aa ¿ Qué lenguaje genera esta gramática ?

ING. JORGE BUABUD



FORMATOS ESTÁNDARES TIPO 2 y 3:

Los siguientes son los formatos estándares de tipo 2 y tipo 3, cuya obtención veremos cuando profundicemos el estudio de los lenguajes independientes del contexto y regulares respectivamente:

FNC 2 N1 →→→→ N2N3N →→→→ t S →→→→ λ

Forma Normal de Chomsky

FNG 2

Forma Normal de Greibach

Forma Normal de Chomsky

N →→→→ tW

S →→→→ λ

FNC 3 N1 →→→→ tN2

N →→→→ t S →→→→ λ

N∈Σ∈Σ∈Σ∈ΣN , t∈Σ∈Σ∈Σ∈ΣT , W∈∈∈∈ΣΣΣΣN* y

si tiene la regla S→→→→λ , entonces

S no figura a la derecha de ninguna regla de producción.

Documents

Gramáticas y Modelos Matemáticos - Clase 3