Sintaxis - Segundo Parcial

Descargar como docx, pdf o txt
Descargar como docx, pdf o txt
Está en la página 1de 13

Libro 2

Capitulo 2: Autómatas finitos con pila (AFPs).


Permiten reconocer LICs, generados por una GIC con producciones V -> (T|V)*
Es más poderoso ya que tiene una memoria de PILA (stack) que permite almacenar, retirar y
consultar información.
Un AFP está constituido por:
 Flujo de entrada, infinito en una dirección: Contiene la secuencia de caract a analizar.
 Control finito: Formado por estados y transiciones.
 Pila abstracta: Secuencia de caracteres de cierto alfabeto, diferente al alfabeto del LIC
reconocido. El primer carácter de la secuencia es que el que está en el tope. Puede
incrementar de a muchos, pero decrementar de a uno.
Formalmente es una 7-upla M = (E, A, A', T, e0, p0, F)
 E: Conjunto finito y no vacio de estados.
 A: Alfabeto de entrada. Símbolos que forman las palabras del LIC (existe fdt: fin de cadena)
 A': Alfabeto de pila. Símbolo $"pila lógicamente vacía".
 e0: Estado inicial (único).
 p0: Símbolo inicial de la pila (indica que está vacía).
 T: Función de transiciones T: E x (A U {ε}) x A' -> E x A'*.
Ej. T(4,a,Z) = {(4,RPZ), (5, ε)} Si el el AFP esta en el estado 4, en el tope de la pila esta Z y lee a,
entonces se queda en el estado 4, y agrega RP a la pila; o se mueve al estado 5 y quita Z del tope.
Hay AFPD y AFPN.
Un AFP puede reconocer un LIC por estado final o por pila vacía. Siempre que se pueda construir
un AFPD que reconozca por estado final, se podrá construir un AFPD que reconozca por pila vacía,
y viceversa.
Autómata Finito con Pila Determinístico (AFPD): Formado por 8 elementos.
 A
 Flujo de entrada
 A'
 Pila: Infinita en una dirección. Inicialmente vacía ($ en el tope)
 E
 e0
 Conjunto de estados finales
 T
Formas de movimiento:
 Si a ∈ A ->T(e,a,R) = (e', α): Si esta en el estado e, lee a y tiene en el R en el tope, entonces
pasa al estado e', reemplaza R por la secuencia α y adelanta una posición en el flujo de
entrada.
 T(e, ε, R) = (e', α): Si esta en el estado e y tiene R en el tope de la pila, entonces pasa al
estado e', reemplaza R por la secuencia α y no adelanta ninguna posición en el flujo.

Capitulo 3: Proceso de compilación.


El programa que se debe compilar es una secuencia de caracteres que termina con un centinela.

Compilador: Complejo programa que lee un programa fuente (escrito en un lenguaje fuente, de
alto nivel) y lo traduce a un programa objeto equivalente (en un lenguaje objeto, más cercano al
lenguaje de maquina).

El proceso de compilación está formado por dos partes:


1) Análisis: A partir del programa fuente, crea una representación intermedia del mismo.
Formado por:
a) Análisis Léxico
b) Análisis Sintáctico
c) Análisis Semántico
2) Síntesis: A partir de la representación intermedia, construye el programa objeto.
Etapa de traducción,consiste en generar código para una MV que puede tener instrucciones del
tipo OP A, B, C A o B o C pueden no ser utilizados.
OP: Código de operación.
A, B: Operandos (variables o constantes).
C: Dirección donde se almacena el resultado.
La traducción es realizada rutinas semánticasllamadas por el Parser.
Se le agregan símbolos de acción(#nombre, a cada símbolo de acción le corresponde una rutina
semántica)a la Gramática Sintáctica para especificar cuándo se debe realizar un procesamiento
semántico. Estos símbolos no forman parte de la sintaxis.
A cada símbolo gramatical (terminal o noterminal) se le asocia un registro semántico.
Ej.: Al símbolo #sumar le corresponde la rutina semántica Sumar.
<expresión> -><primaria> + <primaria> #sumar
Por cada aparición de <primaria> se generara un registro semántico que contendrá datos sobre
cada operando (Ej.: donde está almacenado y cuál es su valor). Cuando la función Sumar es
invocada (por estar #sumar), se le deben pasar estos registros semánticos como argumentos.
Como resultado, Sumar produce un nuevo registro semántico correspondiente a <expresión>.

Una definición completa de un LP debe incluir especificaciones de su Sintaxis y de su Semántica.


La Sintaxis se divide en componentes:
Independientes del Contexto: Se especifican con GICs.
Sensibles al Contexto: Compatibilidad de tipos y reglas de alcance de las variables.

Las restricciones Sensibles al Contexto son manejadas como situaciones semánticas. El


componente semántico de un LP se divide en:
SemánticaEstática: Define las restricciones Sensibles al Contexto que deben cumplirse para
que el programa sea considerado correcto (identificadores declarados, operadores y
operandos con tipos compatibles, rutinas llamadas con un numero apropiado de
argumentos, etc.). Estas restricciones no se pueden expresar en una GIC.
Semántica en Tiempo de Ejecución.

Gramática Léxica: Define los posibles lexemas.


Ej.: <token> -> uno de <id><constante><palReserv><opAdit><asignación><caractPunt>
<id> -><letra> {<letra o digito>} ...
Gramática Sintáctica: Permite precisar las construcciones válidas.
Ej.: <programa> -> inicio <listaSentencias> fin
<listaSentencias> -><sentencia> {<sentencia>} ...

Cada noterminal de la GramáticaSintáctica tiene asociado una rutina de AnálisisSintáctico (PAS:


Procedimiento de AnálisisSintáctico) que puede reconocer cualquier secuencia de tokens
generada por ese noterminal.
Cuando se crea un PAS, las invocaciones a las rutunas semánticas son insertadas en los símbolos
de acción.
Dentro de un PAS, noterminales y terminales del lado derecho deben ser procesados y en el orden
que aparece.
Si se debe procesar un noterminal <A>, invocamos al PAS correspondiente llamado A (esta llamada
puede ser recursiva).
Para procesar un terminal t, invocamos al procedimiento Match(t): Invoca al Scanner para obtener
el próximo token del flujo. Si el token es t, todo es correcto (hubo match) y el token es guardado
en una variable global tokenActual.Si no coincide con t, se produce un Error
Sintáctico(ErrorSintactico(token)). En un PAS también se utiliza la función ProximoToken().

Capitulo 4
La etapa de compilación conocida como análisis se forma por 3 etapas: Análisis Léxico, Análisis
Sintáctico y Análisis Semántico. Todas interactúan con la tabla de símbolos.

Tabla de símbolos (TS)


Conjunto de estructuras de datos que se utiliza para contener todos los identificadores del
programa fuente, junto con atributos que posee cada identificador.
Si los identificadores son: Sus atributos son:
Nombres de variables Tipo y ámbito
Nombres de rutinas Cantidad de parámetros, tipo de cada parámetro, métodos
de transferencia, tipo de valor que retorna.
Ej.: int XX (double a) { … } Podría representarse como (XX, function, int, 1, double)
Las palabras reservadas son identificadores. Para diferenciarlos a veces la TS incluye también las
palabras reservadas en las primeras entradas con un atributo para diferenciarlas de los
identificadores.

Análisis Léxico
Es realizado por el Scanner. Consiste en recorrer el flujo de caracteres que forman el programa
fuente, detectar los lexemas y traducirlos en una secuencia de tokens.
El Scanner se implementa como una función sin parámetros que retorna valores de tipo token,
uno por vez, en la medida que es invocada por el Parser.
El Scanner ignora los espacios separadores de lexemas en el texto del programa fuente.
Cada lexema está formado por la mayor secuencia posible de caracteres para el token
correspondiente; esto requiere que a veces se lea el primer carácter que no pertenece a ese
lexema (centinela).
Ese carácter extra debe ser retornado al flujo con la función ungetc.
Ej.: int Abcd (void) { … } Abcd: pertenece a un LR infinito, requiere el centinela (espacio).
{ : Pertenece a un LR finito, no requiere centinela.
+ :Requiere centinela ya que podría ser ++ o +=
Para que el Parser pueda saber cuándo el Scanner le paso el ultimo token detectado en el flujo de
entrada, se crea un token fdt (fin de texto).

Formas de implementar el Scanner:


a) Con un programa auxiliar, en el que los datos son tokens representados mediantes ERs.
b) Mediante una rutina basada en un AFD: Representado mediante su TT
Acciones que lleva a cabo el Scanner:
 Almacenar el carácterleído en el buffer (vector de caracteres externo a la función
que almacena los caract. de los ids y dígitos de ctes).
 Determinar si es una pal. reserv. o un identificador (si es id lo almacena en TS).
 Almacenar secuencias de dígitos en la TS.
 Detectar Errores Léxicos y llevar a cabo las acciones correspondientes (Si en
cualquier momento de la compilación el primer carácter que lee el Scanner para
detectar el próximo lexema no es un carácter valido para ningún lexema, entonces
se detectó un error léxico y le informa al Parser.)

Para llevar a cabo estas estas acciones son necesarias funciones auxiliares:
 void AgregarCaracter(Int); añade un carácter al buffer.
 TOKEN EsReservada(void); dado un id retorna el token correspondiente.
 void LimpiarBuffer(void);
 feof de ANSI C, para detectar el fdt.
 fgetcde ANSI C, para leer cada carácter del flujo de entrada.
 las funciones ANSI C isspace, isalpha, isalnum, isdigit.

En muchos casos, los lexemas son almacenados en la TS y se representara mediante un índice que
indica la posición en la TS. Entonces el Scanner retornara el par ordenado:
(palabraReservada, índice).
Además podemos encontrar en tablas reservadas:
 Identificadores  (identificador, índice)
 Literales-cadena  (literal-cadena, índice)
 Cntes. numéricas  (tipoConstanteNumerica, índice) o (tipoConstanteNumerica, valor)

Análisis Sintáctico
Es realizado por el Parser (conjunto de procedimientos PAS que implementa la Gramática
Sintáctica y funciones auxiliares: ProximoToken(), Match(t) y ErrorSintáctico(token)). Este verifica
si los tokens que recibe de Scanner forman secuencias o construcciones validas (son
sintácticamente correctas), según la gramática sintáctica del LP.
Si encuentra un error sintáctico, el Parser emite el diagnostico correspondiente.
A medida que las estructuras semánticas son reconocidas, el Parser llama a las correspondientes
rutinas semánticas que realizaran el Análisis Semántico y producen una salida en un lenguaje de
bajo nivel para una MV.
El Parser está formado por un grupo de rutinas que convierte el flujo de tokens en un árbol de
análisis sintáctico. Este árbol representa a la secuencia analizada, donde los tokens que forman la
construcción son las hojas del árbol.

Al derivar una secuencia de tokens, si existe más de un noterminal en una cadena de derivación,
debemos elegir cual es el próximo noterminal que se va a expandir.
 Derivación por izquierda: Se reemplaza el primer noterminal.
 Derivación por derecha: Se reemplaza el último noterminal.
La derivación siempre comienza en el axioma de la GIC y finaliza con una secuencia de terminales.
Una GIC que permite dos derivaciones a izquierda para obtener la misma cadena de terminales se
denomina ambigua y debe ser evitada.

El tipo de análisis sintáctico dependerá de la derivación.


 Análisis Sintáctico Descendiente (top-down): Produce una derivación por izquierda.
Comienza en el noterminal (llamado axioma) y finaliza con los terminales. (Despliega el
árbol hasta llegar a las hojas).Se realiza a través del ParserDescendente.
Derivación por izquierda - Análisis Sintáctico Descendiente
Cadena de derivación obtenida Próxima producción a aplicar
S (axioma) S ->aST
aST S ->Ast
aaSTT S -> b
aabTT T ->cT
aabcTT T -> d
aabcdT T -> d
aabcdd

 Análisis Sintáctico Ascendiente (bottom-up): Utiliza la derivación a derecha de una manera


particular. La última producción aplicada en la derivación a derecha, es la primera en ser
descubierta, mientras que primera producción aplicada (que involucra al axioma) es la
última producción en ser descubierta. (Reduce el árbol hasta llegar al axioma).Se realiza a
través del Parser Ascendente.
Derivación por derecha Análisis Sintáctico Ascendiente
Cadena de derivación Próxima producción Cadena de derivación Próxima producción
S S ->aST aabcdd S -> b
aST T -> d aaScdd T -> d
aSd S ->aST aaScTd T ->cT
aaSTd T ->cT aaSTd S ->aST
aaScTd T -> d aSd T -> d
aaScdd S -> b aST S ->aST
aabcdd S
La derivación es un proceso muy cercano al que
utiliza el Parser para analizar la construcción dada.
 Análisis Sintáctico LL: Consiste en analizar el flujo de tokens de izquierda a derechapor
medio de una derivación por izquierda. Se realiza a través del ParserLL.
 Análisis Sintáctico LR: Consiste en analizar el flujo de tokens de izquierda a derechapor
medio de la derivación por derecha.Se realiza a través del ParserLR.

Las GIC que pueden ser utilizadas en los diferentes Análisis Sintácticos son:
Gramática LL: Es una GIC que puede ser utilizada en un AnálisisSintáctico LL.
GramáticaLR: Es una GIC que p
uede ser utilizada en un Análisis Sintáctico LR.
GramáticaLL(1): Si un noterminal tiene varias producciones, el Parser puede decidir cuál lado
derecho debe aplicar con solo conocer el próximo token del flujo de entrada (llamado símbolo de
preanálisis), por lo que es muy útil y eficiente.
A partir de esta se realiza el Análisis Sintáctico Descendiente.
Sin embargo sus principales problemas son
 No pueden ser recursivas a izquierda.
 No pueden tener un noterminal con dos o más producciones cuyos lados derechos
comiencen con el mismo terminal.
Estas restricciones en las producciones permitieron desarrollar los PAS.
Las operaciones que deben realizarse para transformar la GIC en una GIC equivalente apta para ser
utilizada por el ParserLL(1):
 Factorización a izquierda: Para evitar el segundo problema es necesario modificar las
producciones de ese noterminal de tal forma que el prefijo común quede aislado en una
sola producción.
Ej.: <sentencia if>if (<condición>) <sentencia> else <sentencia> |
If (<condición>) <sentencia>
Corregido: <sentencia if>if(<condición>) <sentencia><opción else>
<opción else> else <sentencia> | ɛ
 Eliminar recursividad a izquierda: Se logra transformando la recursividad a derecha por
una recursividad a izquierda.
Ej.: XXa | b Corregido: XbZ
Z  aZ | ɛ
 Obtención del conjunto PRIMERO: Permite la obtención del conjunto de todos los posibles
símbolos de preanálisis.
Sea la producción A ->X1 …Xm (con Xi pudiendo ser un terminal o noterminal); entonces
PRIMERO(X1…Xm) es el conjunto de terminales que puede iniciar cualquier cadena de
derivación que se obtenga a partir de X1…Xm.
Por cada símbolo Xi hay que fijarse:
o Si Xi es terminal, entonces Xi є PRIMERO.
o Si Xi es noterminal, se calculan los conjuntos PRIMERO las producciones de Xi.
o Si Xi puede generar ɛ, entonces Xi puede ser eliminada.
Ej.: E1  T1 E2 PRIMERO (E1) = PRIMERO (T1 E2)
E2 + T1 E2 | - T1 E2 | ɛ PRIMERO (T1 E2) = PRIMERO (T1)
T1  F1 T2 PRIMERO (T1) = PRIMERO (F1 T2)
T2 * F1 T2 | / F1 T2 | ɛ PRIMERO (F1 T2) = PRIMERO (F1)
F1 ( E1) | num PRIMERO (FI) = { ( , num }

PRIMERO (E1) = { ( , num }


 Obtención del conjunto SIGUIENTE:En caso de que cada Xi pueda producir ɛ, el símbolo de
preanalisis para A esta determinado por aquellos terminales que siguen inmediatamente
al noterminal A.
Para obtener SIGUIENTE(A):
o Si A es seguido por un terminal x (…Ax…), xє SIGUIENTE(A).
o Si A es seguido por un noterminal B (…AB….), PRIMERO(B) є SIGUIENTE(A).
o Si A es el último símbolo de una producción T (T  Y1…YmA),
SIGUIENTE(T) є SIGUIENTE(A).
Ej.: S aSe | B SIGUIENTE(S) = {e}
B bBe | C SIGUIENTE (B) = {e}
C cCe | d SIGUIENTE (C) = {e}
 Función PREDICE: Permite decidir qué producción utilizar para buscar la concordancia con
el símbolo de preanalisis. La función de predicción examina el símbolo de preanalisis para
deducir que producción debe ser utilizada para expandir cada noterminal.
o SI ɛ está en PRIMERO (X1…Xm) :
PREDICE(A -> X1…Xm) = ( PRIMERO (X1…Xm) – {ɛ } ) U SIGUIENTE (A)
o SI ɛno está en PRIMERO (X1…Xm) :
PREDICE(A -> X1…Xm) = PRIMERO (X1…Xm)

Gramática LR(1): Solo requiere conocer el próximo token (símbolo preanálisis) para hacer un
AnálisisSintáctico correcto. El Análisis Sintáctico Ascendiente se hace a partir de esta.

Análisis Semántico
Está inmerso dentro del Análisis Sintáctico, es el comienzo de la etapa de Síntesis del compilador.
No se refiere a la interpretación del significado, sino que consiste en la realización de tareas de
verificación y conversión que no puede realizar el Análisis Sintáctico. El Análisis Semántico debe
verificar que se cumplan todas las reglas sensibles al contexto, como por ejemplo, que una
variable haya sido declarada antes de su utilización, verificación de tipos (para que cada operador
trabaje sobre operandos permitidos), etc.
Para ello, el análisis semántico utiliza mucho la tabla de símbolos.
Las rutinas semánticas llevan a cabo dos funciones:
1) Chequean la semántica estática de cada construcción: Verifican que la construcción sea legal y
tenga un significado, que las variables estén definidas, que los tipos sean correctos, etc.
2) Si la construcción es semánticamente correcta, hacen la traducción: Generan el código para una
Maquina Virtual (MV)que, a través de sus instrucciones, implementa la construcción analizada.
Libro 3
Capítulo 1
Autómatas Finitos
Un autómata finito es un mecanismo que reconoce un determinado LR (acepta cadenas que
pertenecen al lenguaje y rechaza las que no). Existen:
 Autómatas Finitos Determinísticos (AFDs)
 Autómatas Finitos No Determinísticos (AFNs)
o Autómatas Finitos No Determinísticos con transiciones-ɛ

Autómatas Finitos Determinísticos


Su característica funcional es que los estados de llegada están unívocamente determinado por el
estado de partida. Es decir, la lectura de un carácter se determina SIN AMBIGUEDADES.

Formalmente un AFD es un 5-upla (Q, ∑, T, q0, F), donde:


 Q es el conjunto finito no vacío de estados.
 ∑ es el alfabeto de caracteres reconocidos por el autómata
 q0 є Q es el estado inicial (único)
 F є Q es el conjunto no vacío de estados finales.
 T: Q x ∑ -> Q es la función de transiciones.

 Dos AFDs son equivalentes sí reconocen el mismo LR. Además.


 Un AFD es completo si cada estado tiene exactamente una transición por cada carácter del
alfabeto, es decir que su tabla de transiciones no tiene “huecos”. Sino es incompleto.
Completar un AFD es eliminar los huecos, para lo cual:
 Se agrega un nuevo estado llamado estado rechazado.
 Se reemplaza cada “hueco” por una transición a este nuevo estado.
 No se podrá salir del estado rechazado.

AFD incompleto AFD completo


TT a b TT a b
0- 1 - 0- 1 4
1 2 3 1 2 3
2+ - - 2+ 4 4
3+ 3 - 3+ 3 4
4 4 4

Un AFD incompleto y su completo son equivalentes, ya que generan el mismo LR.

Autómatas Finitos No Determinísticos


En este caso cualquier estado puede tener 0, 1 o más transiciones por el mismo carácter del
alfabeto. Habrá por lo menos un estado y un carácter para los que el autómata deberá ELEGIR
entre 2 o más transiciones.
La definición formal es igual a la del AFD, excepto que T: Q x ∑ ->2Q

Autómatas Finitos No Determinísticos con transiciones-ɛ


Es un segundo modelo de AFN y se caracteriza por la existencia de una o más transiciones que
ocurren sin que el autómata lea el próximo carácter de la cadena que está analizando (transiciones
ɛ).

La definición formal es igual a la del AFN, excepto que T: Q x (∑ U {ɛ}) ->2Q

La tabla de transiciones de un AFN con transiciones- ɛ debe tener una columna por cada carácter
del alfabeto, más una por el símbolo ɛ.

Capítulo 2

Algoritmo de Thompson Algoritmo de Clausula- ɛ Algoritmo de Clases


ER AFN AFD AFD Mínimo

Algoritmo de Thompson
Este algoritmo permite obtener un AFN con transiciones-ɛ a partir de una Expresión Regular dada.
Características:
 Al estado inicial no llegan transiciones.
 El estado final debe ser único.
 Del estado final no parten transiciones.
 De cualquier estado no final pueden partir: 1 transición etiquetada con un carácter del
alfabeto, o 1 o 2 transiciones ɛ.

 M1+M2

 M1M2

 M1*
Capítulo 3
Algoritmo de Clausuras-ɛ (o construcción de subconjuntos)
Para todo AFN existe un AFD que reconoce el mismo lenguaje, es decir, para todo AFN existe un
AFD equivalente. El algoritmo para construir un AFD a partir de un AFN se basa en el conocimiento
de dos tipos de conjuntos: Clausura-ɛ y el conjunto Hacia.
 Clausura- ɛ: Es el conjunto de estados formado por q y todos aquellos estados a los cuales
se llega desde q con transiciones-ɛ. Nunca puede ser vacío porque contiene, como
mínimo, a su propio estado.
TT a ɛ
Clausura-ɛ (0) = {0, 3, 4, 6}
0- {1} {3,6}
Clausura-ɛ (1) = {1, 2, 4}
1 - {2}
Clausura-ɛ (2) = {2, 4}
2+ - {4} Clausura-ɛ (3) = {3, 4}
3 - {4} Clausura-ɛ (4) = {4}
4 {5} - Clausura-ɛ (5) = {5}
5+ - - Clausura-ɛ (6) = {6}
6+ {6} -

Si R es un conjunto de estados, la Clausura-ɛ(R) es la unión de las Clausuras-ɛ de los


estados que componen el conjunto R.
R = {1, 3, 6} Clausura-ɛ(R) = {1, 2, 3, 4, 6}
 Hacia: Si R es un conjunto de estados y x un símbolo del alfabeto, hacia(R, x) es el conjunto
de estados a los cuales se transita por el símbolo x, desde los estados de R que tengan esa
transición.
R = {0, 3, 4} hacia(R, a) = {1,5}
Para obtener el AFD, necesitamos determinar:
 El estado inicial del AFD: Es la Clausura-ɛ del estado inicial del AFN.
 Sus estados Finales: Son todos aquellos conjuntos del AFN que contienen por lo menos, un
estado final.
 Su Tabla de Transiciones: Una serie de pasos detallados en el ejemplo.
TT a b ɛ 1) Calcular el estado inicial del AFD:
0- - - {1, 7} Clausura-ɛ (0) = {0, 1, 2, 3, 7, 8}
1 - - {2, 3} 2) Se coloca como estado inicial en la nueva tabla.
2 {4} - - 3) Calcular el estado hacía de este estado inicial:
3 - {5} - Hacia ({0, 1, 2, 3, 7, 8}, a) = {4, 9}
Hacia ({0, 1, 2, 3, 7, 8}, b) = {5}
4 - - {6}
4) Calcular las Clausura-ɛ para los Hacia anteriores:
5 - - {6}
Clausura-ɛ({4,9}) = {1-4, 6-10}
6 - - {1, 7}
Clausura-ɛ({5}) = {1-3, 5-8}
7 - - {8} 5) Completar tabla y volver a calcular los Hacia:
8 {9} - - Hacia ({1-4, 6-10}, a) = {1-4, 6-10}
9 - - {10} Hacia ({1-4, 6-10}, b) = {1-3, 5-8, 11}
10 - {11} - Hacia ({1-3, 5-8}, a) = {1-4, 6-10}
11+ - - - Hacia ({1-3, 5-8}, b) = {1-3, 5-8}
estado a b estado a b
{0, 1, 2, 3, 7, 8} - {1-4, 6-10} {1-3, 5-8} 0- 1 2
{1-4, 6-10} {1-4, 6-10} {1-3, 5-8, 11} 1 1 3
{1-3, 5-8} {1-4, 6-10} {1-3, 5-8} 2 1 2 
{1-3, 5-8, 11} + {1-4, 6-10} {1-3, 5-8} 3+ 1 2

 La columna de transiciones-ɛ se elimina ya que es un AFD


 {1-3, 5-8, 11} es estado final ya que contiene al 11, que es estado final en el AFN
 Renombrar los conjuntos por números, para que sea más entendible.
En caso de que el AFN no tenga transiciones- ɛ se trabaja de la misma forma, pero como las
Clausuras-ɛ de cada estado solo se contendrán a sí mismos, se puede calcular directamente los
Hacía.

Capitulo 4: Complemento e intersección de AFDs.


Complemento:
Todo estado no final será final y todo estado final será no final. (∓ →−¿ ) y (−→ ∓)
Completar tabla antes.
M = (Q, Σ, T, q0, F) -> M = (Q, Σ, T, q0, Q-F)

Intersección:
Reconoce las cadenas que son reconocidas tanto por M1 como por M2.
M1 = (Q1, Σ, T1, q1, F1) -> Mint = (Q1 x Q2, Σ, Tint, (q1 x q2), F1 x F2)
M1 = (Q2, Σ, T2, q2, F2)

Para que un nuevo estado sea inicial debe ser el producto entre los iníciales de sus respectivas
tablas. Y para que sea final, producto entre 2 finales.

En la TT final no se consideran los estados erróneos (inalcanzables o que se quedan en sí mismos).


Además deben eliminarse las equivalencias inmediatas (iguales filas en la TT).

Capitulo 5: De AF (AFD o AFN) a ER.


1) Eliminar estados erróneos por completar e inalcanzables.
2) Plantear ecuaciones para cada estado.
 ∑ ai ei
 Si e es final agrego +ε
 e = αe + β -> e = α*β
−¿¿
3) Resolver para el estado 0 .

Capitulo 6:AFD Mínimo.


AFD mínimo: Es el AFD con la mínima cantidad de estados (TT más reducida). Único autómata
optimo.
Dos o más AFD son equivalentes si su AFD mínimo es el mismo.
Dos o más ER son equivalentes su son reconocidas por el mismo AFD mínimo.
Dos o más estados son equivalentes si pertenecen a la misma clase y tienen el mismo
comportamiento (iguales filas en la TT).
Pasos:
1) Eliminar inalcanzables.
2) Eliminar equivalencias inmediatas.
3) Eliminar equivalencias por clases.

Capitulo 7: Máquina de Turing.


Maquina de Turing (MT): Es un autómata deterministico con la capacidad de reconocer cualquier
lenguaje formal. Está formada por:
 Alfabeto A de caracteres del lenguaje a reconocer.
 Cinta infinita dividida en celdas. En esta cinta se coloca la cadena a analizar seguida de
infinitos blancos que actúan como centinela. Cada celda contiene un carácter o un blanco.
 Cabeza de cinta: Puede en un solo paso leer una celda, reemplazarla con otro carácter o
dejar el mismo, y reposicionarse a derecha (avanzar) o izquierda (retroceder). No puede
retroceder en la celda que contiene el primer carácter de la cadena.
 Alfabeto A' de caracteres que pueden ser escritos en la cinta por la cabeza.
 Conjunto finito de estados (incluye un estado inicial y un conjunto de finales).
 Programa: Conjunto de reglas que, en función del estado y del carácter leído, indican que
carácter escribir en esa posición, en qué dirección moverse y a que estado pasar.

También podría gustarte