Compiladores

Gramaticas

Tipo 3 o Regulares (AF: Automatas Finitos)

G = (VT, VN, P, S)

VT: Conjunto de Simbolos Terminales
VN: Conjunto de Simbolos No Terminales
S(VN: Simbolo Inicial
P: Conjunto de Reglas de Produccion

Regular a Derecha: P( VN x (VTVN(VT({(})
Regular a Izquierda: P( VN x (VNVT(VT({(})Notacion: (={(}

Tipo 2 o Libres de Contexto (CFG) (AP: Automatas de Pila)

G = (VT, VN, P, S)

VT: Conjunto de Simbolos Terminales
VN: Conjunto de Simbolos No Terminales
S(VN: Simbolo Inicial
P: Conjunto de Reglas de Produccion

P( VN x (VT(Vn)*

Tipo 1 o Sensibles al Contexto (CSG) (ALA:Automata Linealmente Acotado)

G = (VT, VN, P, S)

VT: Conjunto de Simbolos Terminales
VN: Conjunto de Simbolos No Terminales
S(VN: Simbolo Inicial
P: Conjunto de Reglas de Produccion

P( (VT(Vn)* Vn (VT(Vn)* x (VT(Vn)*
( ( con |(| ( |(|

Tipo 0 o Sin Restricciones o Estructuradas por Fase (MT:Maquinas de Turing)

G = (VT, VN, P, S)

VT: Conjunto de Simbolos Terminales
VN: Conjunto de Simbolos No Terminales
S(VN: Simbolo Inicial
P: Conjunto de Reglas de Produccion

P( (VT(Vn)* Vn (VT(Vn)* x (VT(Vn)*
Automatas

Automata Finito Deterministico

M = (Q, A, (, q0, F)

Q: Conjunto de Estados(finito)
A: Alfabeto.
(: Q x A ( Q: Funcion de un (Estado, Simbolo) a Estado.
q0( Q: Estado Inicial.
F( Q: Conjunto de Estdados de Aceptacion.

Extension de (: (*: Q x A* ( Q

Automata Finito No Deterministico

M = (Q, A, (, q0, F)

Q: Conjunto de Estados (finito)
A: Alfabeto.
( ( Q x A xQ: Funcion de un (Estado, Simbolo) a Estado.
q0( Q: Estado Inicial.
F( Q: Conjunto de Estdados de Aceptacion.

Automata Finito Con Transiciones (

M = (Q, A, (, q0, F, V)

Q: Conjunto de Estados (finito)
A: Alfabeto.
( ( Q x A x Q: Relacion de (Estados, Simbolo, Estado).
q0( Q: Estado Inicial.F( Q: Conjunto de Estdados de Aceptacion.
V( Q x Q: Relacion de transicion (

Automata de Pila

M = (Q, AE, AP, (, q0, z0, F)

Q: Conjunto de Estados (finito)
AE: Alfabeto de Entrada.
AP: Alfabeto de Pila.
(: Q x (AE ( {(}) x (AP ( {(}) ( Subconjuntos Finitos de Q x AP*:
Funcion de un(Estado, Simbolo) a Estado.
q0( Q: Estado Inicial.
z0( AP: Simbolo Inicial de la Pila.
F( Q: Conjunto de Estados de Aceptacion.

Restricciones Automata de Pila Deterministico

I. Para cada q ( Q y z ( AP , cuando (q, (,Z) es no vacio, entonces ((q,a,Z) es vacio para todo a ( AE.
II. Para ningun q ( Q, z ( AP y a (AE ( {(}, ((q,a,Z) contiene mas de un elemento.

Descripcion Instantanea:

(q,(,() ( Q x AE* x AP*

Automatas

Maquina de Turing

M = (Q, AE, AC, (, q0, b, F)

Q: Conjunto de Estados (finito)
AE: Alfabeto de Entrada (AC - b).
AC: Alfabeto de Cinta.
(: Q x AC ( Q x AC x {L, R, N}: Funcion de un (Estado, Simbolo) aEstado
(En el libro de Hopcroft no aparece N).
q0( Q: Estado Inicial.
b( AC: Blanco en la Cinta.
F( Q: Conjunto de Estdados de Aceptacion.

Descripcion Instantanea

((,q,() ( AC* x Q x AC*
Expresiones Regulares

1. ( es una ER.
2. ( es una ER.
3. ( a ( A, a es una ER.
4. Si ( y ( son ER...