Tarea 6

Automatas y Lenguajes Formales

Andres Lopez MartınezFacultad de Ciencias, Universidad Nacional Autonoma de Mexico

Marzo 29, 2016

1. De las siguientes gramaticas, especifica su tipo (el mas restrictivo posible) y justifica tu eleccion.Da tres cadenas que sean generadas por cada gramatica y muestra el arbol de derivacion paracada una de ellas, en caso de que la gramatica lo permita. En caso contrario basta la derivacion.¿Alguna es ambigua? Justifica tu respuesta.

(a) G1: S → aT | aT → bT | a | aWW → a | aT

Solucion: Esta gramatica es Tipo 3 (Regular) pues sus producciones son lineales a laderecha. Se muestran a continuacion tres ejemplos de arboles de derivacion a partir deesta gramatica:

a:

S

a

aa:

S

a T

a

aba:

S

a T

b T

a

La gramatica no es ambigua pues ninguna cadena tiene arboles de derivacion con etiquetasdistintas en sus nodos interiores. Esto solo podrıa suceder con los sımbolos no terminalesT y W ; no obstante, se observa que los numeros pares de a’s corresponden “T → a” comoultima produccion, y numeros impares de a’s con “W → a”. Por lo tanto, en ningunmomento sus posiciones son intercambiables.

(b) G2: S → ε | AbCAb→ Aab | AbbAa→ aa | εbC → bCc | bc

1

Solucion: Esta gramatica es Tipo 0 (General) pues es contraible en la produccion“Aa → ε”. Dado que los arboles de derivacion no estan propiamente definidos paragramaticas tanto generales como dependientes del contexto, a continuacion se muestranunicamente tres ejemplos de derivaciones a partir de esta gramatica:

• ε : S ⇒ ε

• bc : S ⇒ AbC ⇒ AabC ⇒ bC ⇒ bc

• aabc : S ⇒ AbC ⇒ AabC ⇒ aabC ⇒ aabc

Las gramaticas tipo 0 y 1 no entran dentro de la definicion de ambiguedad estudiada (estase restringe a los tipos 2 y 3). Por lo tanto no hace sentido preguntarse si una gramaticaTipo 0 o Tipo 1 es ambigua.

(c) G3: S → ε | AC | A | CA→ hAee | hee | BB → gB | bC → dddC | ddd

Solucion: Esta gramatica es Tipo 2 (Libre del contexto) pues las producciones tienenunicamente un solo sımbolo terminal a la izquierda y solamente existe ε en la produccion“S → ε”. Ası mismo, no se trata de una gramatica Tipo 3 pues no es ni lineal a la derechani a la izquierda. Se muestran a continuacion tres ejemplos de arboles de derivacion apartir de esta gramatica:

hee:

S

A

hee

ddd:

S

C

ddd

gb:

S

A

B

g B

b

La gramatica no es ambigua pues no hay dos derivaciones por la izquierda que vayan a lamisma forma sentencial.

(d) G4: S → AA→ aABC | abCCB → BCbB → bbbC → bc

2

cC → cc

Solucion: Esta gramatica es Tipo 1 (Dependiente del contexto) pues es de la forma“αAβ → w” con w 6= ε y |αAβ| ≤ |w|. No es Tipo 2 ya que del lado izquierdo de lasproducciones no se tiene un solo sımbolo no terminal y, por ende, tampoco es Tipo 3. Acontinuacion se muestran tres ejemplos de derivaciones a partir de esta gramatica:

• abc : S ⇒ A⇒ abC ⇒ abc

• aabbcc : S ⇒ aABC ⇒ aabCBC ⇒ aabBCC ⇒ aabbCC ⇒ aabbcC ⇒ aabbcc

• aaabbbccc : S ⇒ aABC ⇒ aaABCBC ⇒ aaabCBCBC ⇒ aaabBCCBC ⇒aaabbCCBC ⇒ aaabbCBCC ⇒ aaabbBCCC ⇒ aaabbbCCC ⇒aaabbbcCC ⇒ aaabbbccC ⇒ aaabbbccc

La gramatica no es ambigua pues las gramaticas de Tipo 1 no entran en la definicion deambiguedad estudiada.

(e) G5: S → A | CA→ aAc | aBcB → bBc | bcC → aCbb | abb

Solucion: Esta gramatica es Tipo 2 (Libre del contexto) pues las producciones tienenunicamente un solo sımbolo terminal a la izquierda; y no se trata de una gramatica Tipo 3pues no es ni lineal a la derecha ni a la izquierda. Se muestran a continuacion tres ejemplosde arboles de derivacion a partir de esta gramatica:

abcc:

S

A

a B

b b

c

abb:

S

C

a b c

aabcc:

S

A

a A

a B

b b

c

c

La gramatica no es ambigua pues no hay dos derivaciones por la izquierda que vayan a lamisma forma sentencial.

2. Sean:L1 = (a+ b)∗a(a+ b)2,L2 = {w ∈ {a, b}∗ | cada a en w esta seguida inmediatamente por una b} y

3

L3 = {w ∈ {a, b}∗ | w no tiene una subcadena aab}

(a) Muestra los automatas que reconozcan cada uno de los lenguajes anteriores y obten, apartir de ellos, las gramaticas tipo 3.Solucion:

• L1 : (a+ b)∗a(a+ b)2

Sstart A B

Φ

a,b

a a,b

a,b

G1:

S → aS | bS | aAA→ aB | bBB → a | b

• L2 : (ab+ b)∗

Sstart W

a

b

b

G2:

S′ → ε | aW | bS | bS → aW | bS | bW → bS | b

• L3 : (ab+ b)∗(a)∗

Sstart

WAa

a

b

b

a

G3:

S′ → ε | aW | bS | b | aAS → aW | bS | b | aAW → bS | bA→ aA | a

(b) Muestra tanto el automata como la gramatica tipo 3 correspondientes a los siguientesincisos. Justifica cada modificacion en las gramaticas (quitar ε, agregar nuevo sımboloinicial, etc).

(i) L1 ∪ L2

Solucion: Sean las gramaticas:

G(L1) = (N1, T1, P1, S1):

S1 → aS1 | bS1 | aAA→ aB | bBB → a | b

G(L2) = (N2, T2, P2, S2):

S2 → ε | aW | bZ | bZ → aW | bZ | bW → bZ | b

4

Donde se renombraron los sımbolos no terminales de tal forma que N1 ∪N2 = ∅. Lagramatica G = (N,T, P, S) que describe la union de los lenguajes L1 y L2 se construyecomo:

• N = N1 ∪N2 ∪ {S1, S2} = {A,B,Z,W, S1, S2}• T = T1 ∪ T2 = {a, b}• P = P1 ∪ P2 ∪ {S → α | S1 → α ∈ P1 ∨ S2 → α ∈ P2}\{S1 → ε, S2 → ε} =

S → ε | aS1 | bS1 | aA | aW | bZ | bS1 → aS1 | bS1 | aAA→ aB | bBB → a | bS2 → aW | bZ | bZ → aW | bZ | bW → bZ | b

• S es un sımbolo nuevo tal que S /∈ N1 y S /∈ N2

Notemos que las producciones de los sımbolos S2 y Z son identicas, y que no existeproduccion en la gramatica que tenga a S2 del lado derecho, por lo que se puedeneliminar las producciones de S2 sin afectar el lenguaje producido por la gramatica.El AFN correspondiente a esta gramatica es:

Sstart

S1

Z

A

W

B

Φ

a,ba

ba

b

a,ba

ba

b

a,b

b

b

a,b

(ii) L1 • L21

Solucion: Sean las gramaticas:

G(L1) = (N1, T1, P1, S1):

S1 → aS1 | bS1 | aAA→ aB | bBB → a | b

G(L2) = (N2, T2, P2, S2):

S2 → ε | aW | bZ | bZ → aW | bZ | bW → bZ | b

La gramatica G = (N,T, P, S) que describe la concatenacion de los lenguajes L1 y L2

se construye, suponiendo inicialmente que ε /∈ L1 ∪ L2, como:

• N = N1 ∪N2 ∪ {S2} = {A,B,Z,W, S2}1• = concatenacion

5

• T = T1 ∪ T2 = {a, b}• P = {A → aB | A,B ∈ N1 ∪ {S1} ∧ a ∈ T1} ∪ {A → aS2 | A → a ∈ P1, A ∈N1 ∪ {S1} ∧ a ∈ T1} ∪ P2

• S = S1

Ahora bien, dado que en este caso ε en efecto es un elemento de L1 ∪ L2, dada laproduccion S2 → ε en G(L2), se incluye en las producciones el caso en el que L1 seconcatena con ε. Por lo tanto, se hace la siguiente adecuacion a las producciones dela gramatica:

• P = {A → aB | A,B ∈ N1 ∪ {S1} ∧ a ∈ T} ∪ {A → aS2 | A → a ∈ P1, A ∈N1 ∪ {S1} ∧ a ∈ T1} ∪ P2 ∪ {A→ a | A→ a ∈ P1, A ∈ N1 ∪ {S1} ∧ a ∈ T1} =

S → aS | bS | aAA→ aB | bBB → a | b | aS2 | bS2S2 → aW | bZ | bZ → aW | bZ | bW → bZ | b

El AFN correspondiente a esta gramatica es:

Sstart

A B

S2

Z W

Φ

a,b

a

a,b a,b

a,b

ab

b

b

b

a

b

b

(iii) L2 • L31

Solucion: Sean las gramaticas:

G(L2) = (N1, T1, P1, S1):

S1 → ε | aW | bZ | bZ → aW | bZ | bW → bZ | b

G(L3) = (N2, T2, P2, S2):

S2 → ε | aU | bT | b | aVT → aU | bT | b | aVU → bT | bV → aV | a

La gramatica G = (N,T, P, S) que describe la concatenacion de los lenguajes L2 y L3

se construye, suponiendo inicialmente que ε /∈ L2 ∪ L3, como:

• N = N1 ∪N2 ∪ {S2} = {Z,W, T, U, V, S2}

6

• T = T1 ∪ T2 = {a, b}• P = {A → aB | A,B ∈ N1 ∪ {S1} ∧ a ∈ T1} ∪ {A → aS2 | A → a ∈ P1, A ∈N1 ∪ {S1} ∧ a ∈ T1} ∪ P2

• S = S1

Ahora bien, dado que en este caso ε en efecto es un elemento de L2 ∪ L3, dadas lasproducciones S1 → ε y S2 → ε en G(L2) y G(L3) respectivamente; se incluyen en lasproducciones el caso en el que L2 se concatena con ε, el caso en el que ε se concatenacon L3 y el caso en el que ε se concatena con ε. Por lo tanto, se hace la siguienteadecuacion a las producciones de la gramatica:

• P = {A → aB | A,B ∈ N1 ∪ {S1} ∧ a ∈ T1} ∪ {A → aS2 | A → a ∈ P1, A ∈N1 ∪{S1}∧ a ∈ T1}∪P2 ∪{A→ a | A→ a ∈ P1, A ∈ N1 ∪{S1}∧ a ∈ T1}∪ {S →α| S2 → α ∈ P2} ∪ {S → ε} =

S → ε | aW | bZ | bS2 | b | aU | bT | b | aVZ → aW | bZ | bS2 | bW → bZ | bS2 | bS2 → aU | bT | b | aVT → aU | bT | b | aVU → bT | bV → aV | a

El AFN correspondiente a esta gramatica es:

Sstart

W Z

S2

U

T

V

Φ

ab

b

b

a

b

a

bb

b

a

b

b

b

a

b

b

a

b

b

a

b

b

a

a

a

7