Download - Automatas de pila_no_det
![Page 1: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/1.jpg)
Autómatas de pila no deterministas.
Generalidades, relación con lenguajes independientes del contexto, ejemplos
y aplicaciones
Por: Oscar Eduardo Sánchez Garcia.
![Page 2: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/2.jpg)
1. Introducción
![Page 3: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/3.jpg)
Construcción de compiladores
Teoría de Lenguajes Formales y Autómatas
Matemáticas
![Page 4: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/4.jpg)
p u b l i c c l a s s A r r a y D e m o { p u b l i c s t a t i c v o i d m a i n ( S t r i n g [ ] a r g s ) { i n t [ ] a n A r r a y ; a n A r r a y = n e w i n t [ 1 0 ] ; f o r ( i n t i = 0 ; i < a n A r r a y . l e n g t h ; i + + ) { a n A r r a y [ i ] = i ; S y s t e m . o u t . p r i n t ( a n A r r a y [ i ] + " " ) ; } S y s t e m . o u t . p r i n t l n ( ) ; }}
L e n g u a j e d e a l t o n i v e l
C ó d i g o e j e c u t a b l e
C o m p i l a d o r
![Page 5: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/5.jpg)
Análisis Lexicográfico
Análisis Sintáctico
Análisis Semántico
OptimizaciónPreparación para la generación de código
Generación de código
Fas
es d
el
Com
pila
dor1
1 Fases del Compilador según Karen A. Lemone
Autómatas de pila no deterministas
![Page 6: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/6.jpg)
2. Pila
![Page 7: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/7.jpg)
La pila
• Estructura de datos• Permite las operaciones
– Quitar: pop()– Colocar: push()– Ver el elemento del tope:
stackTop()– Ver si la pila está vacía:
empty()
• Es una lista LIFOA
C
A
F
G
![Page 8: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/8.jpg)
3. Autómata de pila no determinista (ADPND)
![Page 9: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/9.jpg)
3.1 Generalidades
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H B
Q u i t a r C o l o c a r
z
Ejemplo
![Page 10: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/10.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H B z
¿Acepta aab?
3.1.1
![Page 11: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/11.jpg)
¿Acepta aab?
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H B z
![Page 12: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/12.jpg)
¿Acepta aab?
a / z / A H a / A / a b / b / bq 2q 1 q 2
q 1
z
a)
![Page 13: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/13.jpg)
¿Acepta aab?
a / z / A H a / A / a b / b / bq 2q 1 q 2
q 1
z
a)
H
A
![Page 14: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/14.jpg)
¿Acepta aab?
a / z / A H a / A / a b / b / bq 2q 1 q 2
q 1
z
a)
H
AH
a
![Page 15: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/15.jpg)
¿Acepta aab?
a / z / A H a / A / a b / b / bq 2q 1 q 2
q 1
z
a)
H
AH
a Falló
![Page 16: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/16.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H Bz
b)
¿Acepta aab?
![Page 17: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/17.jpg)
¿Acepta aab?
a / z / z a / z / z b / F / a H a Eq 3q 2 q 4q 1
z
b)
![Page 18: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/18.jpg)
¿Acepta aab?
a / z / z a / z / z b / F / a H a Eq 3q 2 q 4q 1
z
b)
z
![Page 19: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/19.jpg)
¿Acepta aab?
a / z / z a / z / z b / F / a H a Eq 3q 2 q 4q 1
z
b)
z z
![Page 20: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/20.jpg)
¿Acepta aab?
a / z / z a / z / z b / F / a H a Eq 3q 2 q 4q 1
z
b)
z z
Falló
![Page 21: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/21.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H B z
c)
¿Acepta aab?
![Page 22: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/22.jpg)
¿Acepta aab?
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
z
c)
![Page 23: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/23.jpg)
¿Acepta aab?
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
z
c)
B
H
A
![Page 24: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/24.jpg)
¿Acepta aab?
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
z
c)
B
H
A
B
H
b
F
![Page 25: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/25.jpg)
¿Acepta aab?
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
z
c)
B
H
A
B
H
b
F
B
H
b
E
a
H
a
![Page 26: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/26.jpg)
¿Acepta aab?
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
z
c)
B
H
A
B
H
b
F
B
H
b
E
a
H
a
El autómata acepta aab
![Page 27: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/27.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H B z
¿Acepta ab?
3.1.2
![Page 28: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/28.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H B z
¿Acepta ab? No
3.1.2
![Page 29: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/29.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H B z
¿Acepta aba?
3.1.3
![Page 30: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/30.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H B z
¿Acepta aba? No
3.1.3
![Page 31: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/31.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z)
![Page 32: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/32.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( , , )
![Page 33: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/33.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, , )
![Page 34: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/34.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, )
![Page 35: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/35.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, AHB)
![Page 36: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/36.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, AHB) ├── ( , , )
![Page 37: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/37.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, , )
![Page 38: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/38.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, )
![Page 39: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/39.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB)
![Page 40: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/40.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB) ├── ( , , )
![Page 41: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/41.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB) ├── ( q4, , )
![Page 42: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/42.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB) ├── ( q4, ε, )
![Page 43: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/43.jpg)
3.2 Descripción instantánea
z
B
H
A
B
H
b
F
B
H
b
E
a
H
a
a / z / A H B a / A / F b b / F / a H a Eq 3q 3 q 4q 1
( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB) ├── ( q4, ε, aHaEbHB)
![Page 44: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/44.jpg)
3.3 Especificación formal de un ADPND
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / z
a / z / A H B
M = ( Q, Σ, Γ, Δ, s, F, z)
Q = { q1, q2, q3, q4 }
Σ = { a, b }
Γ = { z, A, B, E, F, H, a, b}
s = q1
F = { q2, q4 }
![Page 45: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/45.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / za / z / A H B
Δ( q3, b, F ) = { ( q4, aHaE)}
![Page 46: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/46.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / za / z / A H B
Δ( , , ) = { ( , )}
Δ( q3, b, F ) = { ( q4, aHaE)}
![Page 47: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/47.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / za / z / A H B
Δ( q1, , ) = { ( , )}
Δ( q3, b, F ) = { ( q4, aHaE)}
![Page 48: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/48.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / za / z / A H B
Δ( q1, a, ) = { ( , )}
Δ( q3, b, F ) = { ( q4, aHaE)}
![Page 49: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/49.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / za / z / A H B
Δ( q1, a, z ) = { ( , )}
Δ( q3, b, F ) = { ( q4, aHaE)}
![Page 50: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/50.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / za / z / A H B
Δ( q1, a, z ) = { ( q3, )}
Δ( q3, b, F ) = { ( q4, aHaE)}
![Page 51: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/51.jpg)
q 1 q 2
q 3q 4
a / z / A H
a / A / ab / b / b
a / z / z
a / A / F bb / F / a H a E
a / z / za / z / A H B
Δ( q1, a, z ) = { ( q3, AHB)}
Δ( q3, b, F ) = { ( q4, aHaE)}
![Page 52: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/52.jpg)
Δ( q1, a, z ) = { ( q1, AH), ( q2, z), ( q3, AHB) }
Δ( q1, a, A ) = { ( q2, a)}
Δ( q2, b, b ) = { ( q2, b)}
Δ( q2, a, z ) = { ( q3, z)}
Δ( q3, a, A ) = { ( q3, Fb)}
Δ( q3, b, F ) = { ( q4, aHaE)}
La transiciones quedan:
![Page 53: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/53.jpg)
El autómata queda M = ( Q, Σ, Γ, Δ, s, F, z)
donde
Q = { q1, q2, q3, q4 }
Σ = { a, b }
Γ = { z, A, B, E, F, H, a, b}
s = q1
F = { q2, q4 }
y Δ, la regla de transición, está dada por
Δ( q1, a, z ) = { ( q1, AH), ( q2, z), ( q3, AHB) }
Δ( q1, a, A ) = { ( q2, a)}
Δ( q2, b, b ) = { ( q2, b)}
Δ( q2, a, z ) = { ( q3, z)}
Δ( q3, a, A ) = { ( q3, Fb)}
Δ( q3, b, F ) = { ( q4, aHaE)}
![Page 54: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/54.jpg)
3.4 Definición de autómata de pila no determinista1.
Un autómata de pila no determinista es una 7-tupla
M = ( Q, Σ, Γ, Δ, s, F, z ) donde
Q es un conjunto finito de estados
Σ es un alfabeto de entrada
Γ es un alfabeto llamado alfabeto de la pila
Δ es una regla de transición, Δ: Q × ( Σ ∪ {ε} ) × ΓP( Q × Γ *)
s ∈ Q es el estado inicial o de partida
F ⊆ Q es el conjunto de estados finales o de aceptación
z ∈ Γ es el símbolo inicial o de partida
___________________________1 Basada en la definición de Kelly y de Isasi-Martínez-Borrajo
![Page 55: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/55.jpg)
Δ : Q × ( Σ ∪ {ε} ) × Γ P( Q × Γ * )
Δ( q3, b, F ) = { ( q4, aHaE ) }
![Page 56: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/56.jpg)
3.5 Definición de lenguaje aceptado por un autómata de pila no determinista1.
Sea M = ( Q, Σ, Γ, Δ, s, F, z ) un autómata de pila no determinista. El lenguaje aceptado por M se denota por L(M) y es el conjunto
__________________________
1 Dean Kelly
*}ypara),,(),,(| * {)( Γ∈∈Σ∈= uFpupzwswML ε*
![Page 57: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/57.jpg)
3.6 Ejemplo 2
q 1 q 2 q 3
a / z / A z
a / A / A A
b / A / ε
b / A / ε ε / z / z
Acepta: ab, aabb, aaabbb, aaaabbbb, …
Es decir acepta el lenguaje {ab, aabb, aaabbb, aaaabbbb, …}
Formalmente acepta el lenguaje: { aibi | i ≥ 1}
![Page 58: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/58.jpg)
3.7 Método de construcción de un ADPND a partir de una Gramática independiente del contexto
Ejemplo: }0,0|{ ≥≥ jiabbaa jjii
![Page 59: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/59.jpg)
4.7 Método de construcción de un ADPND a partir de una Gramática independiente del contexto
Ejemplo: }0,0|{ ≥≥ jiabbaa jjii Gramática independiente del Contexto:
S AB
A aAa | b
B bBa | ε
![Page 60: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/60.jpg)
4.7 Método de construcción de un ADPND a partir de una Gramática independiente del contexto
Ejemplo: }0,0|{ ≥≥ jiabbaa jjiiGramática independiente del Contexto:
S AB
A aAa | b
B bBa | ε
q 1
q 2
q 3
ε / z / S z ε / A / b
ε / B / ε
ε / S / A B ε / A / a A a
ε / B / b B ab / b / ε
a / a / ε
ε / z / ε
![Page 61: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/61.jpg)
4.8 Método de construcción de una gramática independiente del contexto a partir de un ADPND
ADPND M con estado inicial q1, F = { q3 } y transiciones:
Δ( q1, a, z ) = { ( q1, Az) } Δ( q2, b, A ) = { ( q2, ε)}
Δ( q1, a, A ) = { ( q1, AA)} Δ( q2, ε, A ) = { ( q2, ε)}
Δ( q1, b, A ) = { ( q2, ε)} Δ( q2, ε, z ) = { ( q3, ε)}
Gramática independiente del contexto con símbolo inicial [q1zq3]
[q1Aq2] b
[q2Aq2] b | ε
[q2zq3] ε
[q1zq1] a[q1Aq1] [q1zq1] | a [q1Aq2] [q2zq1] | a[q1Aq3] [q3zq1]
[q1zq2] a[q1Aq1] [q1zq2] | a [q1Aq2] [q2zq2] | a[q1Aq3] [q3zq2]
[q1zq3] a[q1Aq1] [q1zq3] | a [q1Aq2] [q2zq3] | a[q1Aq3] [q3zq3]
[q1Aq1] a[q1Aq1] [q1Aq1] | a [q1Aq2] [q2Aq1] | a[q1Aq3] [q3Aq1]
[q1Aq2] a[q1Aq1] [q1Aq2] | a [q1Aq2] [q2Aq2] | a[q1Aq3] [q3Aq2]
[q1Aq3] a[q1Aq1] [q1Aq3] | a [q1Aq2] [q2Aq3] | a[q1Aq3] [q3Aq3]
![Page 62: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/62.jpg)
4.9 Aplicación
Ejemplo: Especificar la sintaxis de una expresión algebraica (problema simplificado)
Gramática independiente del Contexto:
S S+T | T
T T*F | F
F a | (S)
Palabras que el autómata debe aceptar
(a+a)*a+a*a
a*(a+(a+a))
(a+a*(a+a))*(a*a)
![Page 63: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/63.jpg)
ADPND para especificar la sintaxis de una expresión algebraica (problema simplificado)
q 1
q 2
q 3
ε / z / S z
ε / F / a
ε / F / ( S )
ε / S / S + Tε / S / T
ε / T / T * F
( / ( / ε
) / ) / ε
ε / z / ε
ε / T / F
* / * / ε
+ / + / εa / a / ε
El autómata es una guía para escribir el código del compilador
![Page 64: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/64.jpg)
{ aibici | i ≥ 0 }
4.10 Poder de representación
{ aibi | i≥1}
…
{ai | i≥0}
…
Autómata Finito no determinista
Lenguajes regulares
Autómata de pila no determinista
Lenguajes independientes del contexto
Todos los lenguajes
![Page 65: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/65.jpg)
Lenguaje independiente del contexto
S S+T | T
T T*F | F
F a | (S)
q 1
q 2
q 3
ε / z / S z
ε / F / a
ε / F / ( S )
ε / S / S + Tε / S / T
ε / T / T * F
( / ( / ε
) / ) / ε
ε / z / ε
ε / T / F
* / * / ε
+ / + / εa / a / ε
![Page 66: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/66.jpg)
For
If
While
Do while
expresiones
4.11 Autómatas y lenguajes de programación de computadores
Identificadores
Enteros
Reales
Operadores
Cadenas de caracteres
Autómata Finito no determinista
Autómata de pila no determinista
Análisis léxico
Análisis sintáctico
![Page 67: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/67.jpg)
5. Aplicaciones
![Page 68: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/68.jpg)
Aplicaciones que requieren análisis sintáctico
• Compilador para un computador de automatización industrial
• Herramienta de consulta de bases de datos distribuidas
• Creación de un motor de base de datos relacional
• Creación de un motor de base de datos OO (Base de objetos) y su lenguaje de consulta (OQL)
• Simulador robótico con lenguaje de programación para robots
• Generador de analizador sintáctico (YACC, JAVACC)
Investigación y desarrollo
![Page 69: Automatas de pila_no_det](https://reader034.vdocumento.com/reader034/viewer/2022052602/559adf6f1a28ab0a2c8b46b4/html5/thumbnails/69.jpg)
Bibliografía
• KELLY, Dean. Teoría de Autómatas y Lenguajes Formales. Prentice Hall.
• BRENA, Ramón. Autómatas y Lenguajes. Tec. Monterrey. 2003. Libro electrónico disponible en http://lizt.mty.itesm.mx/~rbrena/AyL.html
• ISASI VIÑUELA, Pedro ;MARTÍNEZ FERNANDEZ, Paloma; BORRAJO MILLÁN, Daniel. Lenguajes, Gramáticas y Autómatas; Un enfoque práctico. Editorial Addison-Wesley.
• HOPCROFT Y ULLMAN. Introducción a la Teoría de Autómatas, Lenguajes y Computación. Editorial Cecsa.