TeoriaComputacion

División Multidisciplinaria de Ciudad Universitaria

Teoría de la Computación
Unidad II. Teoría del Autómata de Pila

Dr. Vicente García Jiménez
vicente.jimenez@uacj.mx

29 de septiembre de 2015

2.2 CFG
Árboles

1

El proceso de derivación de una cadena se puede representar
graficamente por medio de un árbol (grafo)
Raíz (padre)

Nodo Interior

Hoja

Nodo Interior

Hoja Hoja

Dr. Vicente GarcíaJiménez | Teoría de la Computación

Hoja

2.2 CFG
Árboles

Sea G = (V , Σ, R, S) una gramática. Los árboles de derivación
para G son aquellos árboles que cumplen con las condiciones
siguientes:
El nodo raíz está etiquetado con símbolo inicial de la
gramática (S)
Los nodos hojas están etiquetados con símbolos
terminales o ε
Los nodos interiores están etiquetados con no-terminales
Si un nodointerior está etiquetado como S y S → 1P1,
entonces se crean 3 nodos hijos ordenados de izquierda a
derecha, cuya etiquetas son 1, P y 1

Dr. Vicente García Jiménez | Teoría de la Computación

2

2.2 CFG
Árboles

3

S→ε
S → aSb

S

S⇒ε

ε

Dr. Vicente García Jiménez | Teoría de la Computación

2.2 CFG
Árboles

4

S

S→ε
S → aSb
S ⇒ aSb ⇒ aaSbb ⇒
aaaSbbb ⇒ aaaεbbb

a

S

b

a

S

b

a

S

b

ε

Dr.Vicente García Jiménez | Teoría de la Computación

2.2 CFG
Árboles

Dibuja el árbol para cada una de las siguientes derivaciones
1. E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ a + T ⇒ a + F ⇒ a + a
2. E ⇒ EOE ⇒ (E)OE ⇒ (EOE)OE ⇒ ( a OE)OE ⇒
( a −E)OE ⇒ ( a − a )OE ⇒ ( a − a )∗E ⇒ ( a − a )∗ a

Dr. Vicente García Jiménez | Teoría de la Computación

5

2.2 CFG
Ambigüedad

Si una gramática G, puede generar unacadena w con dos
o más derivaciones por la izquierda diferentes,
entonces, G es ambigüa
Una cadena w tiene diferentes árboles y por tanto
diferentes significados

Dr. Vicente García Jiménez | Teoría de la Computación

6

2.2 CFG
Ambigüedad

Sea G = ({S, A}, {a, b}, {S → aSA, S → ε, A → bA, A → ε}, S).
Encuentra para la cadena aab, dos derivaciones por la
izquierda diferentes. Dibuja el árbol

Dr.Vicente García Jiménez | Teoría de la Computación

7

2.2 CFG
Ambigüedad

Sea G = ({S, A}, {a, b}, {S → aSA, S → ε, A → bA, A → ε}, S).
Encuentra para la cadena aab, dos derivaciones por la
izquierda diferentes. Dibuja el árbol
S ⇒ aSA ⇒ aaSAA ⇒ aaεAA ⇒ aaεεA ⇒ aaεεbA ⇒
aaεεbε

Dr. Vicente García Jiménez | Teoría de la Computación

7

2.2 CFG
Ambigüedad

Sea G = ({S, A}, {a, b}, {S → aSA, S → ε, A →bA, A → ε}, S).
Encuentra para la cadena aab, dos derivaciones por la
izquierda diferentes. Dibuja el árbol
S ⇒ aSA ⇒ aaSAA ⇒ aaεAA ⇒ aaεεA ⇒ aaεεbA ⇒
aaεεbε
S ⇒ aSA ⇒ aaSAA ⇒ aaεAA ⇒ aaεbAA ⇒ aaεbεA ⇒
aaεbεε

Dr. Vicente García Jiménez | Teoría de la Computación

7

2.2 CFG
Gramáticas Regulares

Los lenguajes regulares pueden ser descritos/definidos
por ER, AF y GT.
Las gramáticas libres decontexto (CFG) pueden generar
lenguajes regulares y no regulares
Una gramática libre de contexto genera exactamente el mismo
lenguaje que acepta un AFD

Dr. Vicente García Jiménez | Teoría de la Computación

8

2.2 CFG
Gramáticas Regulares

Sea D = (Q, ΣD , δ, q0 , F ) un AFD; lenguaje L(D) puede ser
generado por G(D) = (V , Σ, R, S), donde:
V =Q
Σ = ΣD
S = q0
R = {qi → aqj |δ(qi , a) = qj } ∪ {qi →ε|qi ∈ F }, donde
qi , qj ∈ Q y a ∈ ΣD

Dr. Vicente García Jiménez | Teoría de la Computación

9

2.2 CFG
Gramáticas Regulares

10

1

0

0
q0

1

q1

q2
0,1

Dr. Vicente García Jiménez | Teoría de la Computación

2.2 CFG
Gramáticas Regulares

10

1

0

0
q0

1

q1

q2
0,1

q0 → 0q0 |1q1
q1 → 1q1 |0q2 |ε
q2 → 1q1 |0q1
Evalua la cadena w = 001100 con Hopcroft y generar la
cadena utilizando laderivación por la izquierda. Dibuja el árbol

Dr. Vicente García Jiménez | Teoría de la Computación

2.2 CFG
Gramáticas Regulares

11

1
q0

q1
1

0

0

0

0

1
q2

q3
1

Convierte el AFD en una CFG, evalua la cadena w = 110101
con Hopcroft y genera la misma utilizando la derivación por la
izquierda. Dibuja el árbol

Dr. Vicente García Jiménez | Teoría de la Computación

2.2 CFG
Gramáticas...