Clase2 Sesion2

Universidad Nacional del Callao
Escuela de Posgrado
Unidad de Posgrado de la FIIS
Maestría en Ingeniería de sistemas

Teoría de Lenguajes de programación
Autómatas AFN y AFD

Diagrama de
transiciones
Dra. MSc. Mg. Ing. Sally Torres

[email protected]
Teoría de lenguajes de Programación UPFIIS-UNAC Dra. Msc. Sally Torres
Contenido
Autómatas
Autómata finito no determinista
Grafo de Transiciones
Tabla de Transiciones
Guía practica de ejercicios

Autómatas
Definición.-
La teoría de autómatas es una rama de la teoría de la

computación que estudia las máquinas abstractas y los
problemas que éstas son capaces de resolver.
La teoría de autómatas está estrechamente relacionada con
la teoría del lenguaje formal ya que los autómatas son
clasificados a menudo por la clase de lenguajes formales
que son capaces de reconocer.
También son de gran utilidad en la teoría de la complejidad
computacional.

Autómatas Finitos no deterministas
• Es un autómata que para par (estado, caracter), tiene
mas de un estado de transición y permite transiciones
para la entrada vacía.
• Un autómata finito “no determinista” AFN tiene la
capacidad de estar en varios estados simultáneamente.
El término “no determinista” hace referencia al hecho de
que para cada entrada devuelve un conjunto de cero,
uno o más estados.
• Si para cada par estado actual una entrada existe mas de
un estado siguiente indica que se puede elegir entre las
distintas posibilidades. No existe nada que determine la
elección. De ahí el nombre de no determinista.

AUTOMATAS FINITO NO DETERMINISTA-AFN
Definición formal.- Un AFN es un modelo matemático formado por:

1) Un conjunto finito de “estados” S.
2) Un alfabeto de “símbolos de entrada” V.
3) Un estado S0 que se considera “de inicio” o “inicial” (S0 ϵ S )
4) Un conjunto de estados F considerados “estados de aceptación” o
“finales”. (F ⸦ S )
5) Una función de transición mueve que transforma pares estado-símbolo
en conjuntos de estados. “mueve” es una función que toma como
argumentos un estado de S y un símbolo de entrada de V y devuelve
un subconjunto de S.
mueve : S x V → P(S) conjunto de estados
Es decir, un AFN se puede denotar con la quíntupla :
AFN = {S, V, S0, mueve, F}

4
Teoría de Lenguajes
Teoría de lenguajes de Programación
y compiladores UPFIIS-UNACMg. Msc.
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Un AFN también se puede representar mediante un grafo dirigido y
etiquetado llamado “grafo de transiciones”, en el que los nodos
representan a los estados del autómata y las aristas etiquetadas y
orientadas representan la función mueve, es decir, las transiciones. Las
aristas pueden etiquetarse con el símbolo especial
El siguiente es el grafo de transiciones que reconoce el lenguaje
( a | b ) * a b b abb , aaaaabb, bbbabb, abababaabb
1. Estados: 0, 1, 2, 3 3. Estado inicial: 0

2. Alfabeto: { a, b } 4. Estados finales o aceptación: { 3 }
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Tabla de transiciones
La manera más sencilla de implementar esto en un computador es por
medio de un cuadro o matriz en el cual a cada estado le corresponde una
fila y a cada símbolo una columna (tabla de doble entrada). Esta tabla
recibe el nombre de “Tabla de Transiciones” del autómata
Cada entrada representa el conjunto
de estados que puede ser alcanzado
por una transición desde el estado i
con la entrada j.
Ejemplo: La tabla de transiciones
de AFN para el lenguaje
representado por la expresión
regular (a | b)*abb.
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Aceptación de una cadena por parte de un AFN

Un AFN acepta una cadena de entrada x si hay algún “camino” en el
grafo de transiciones desde el estado de inicio a algún estado de
aceptación, tal que concatenando las etiquetas de las sucesivas aristas a
lo largo del “camino” se obtiene x (la cadena x). ( a | b ) * a b b
Ejemplo x=aba El camino debe ser: ababb 0 0 1 2 3
a b a
00 01
pero como no termina en 3
que es el estado de
aceptación termina en
estado 1 por eso dicha
cadena no pertenece al
grafo
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Aceptación de una cadena por parte de un AFN

Ejemplo x=aabb El camino debe ser:
a a b b
001 23
termina en 3 que es el
estado de aceptación
entonces dicha cadena
pertenece al grafo
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
El siguiente es el grafo de transiciones que reconoce el lenguaje
( a a*| bb* )  a, b, aaaaa,bbbbb
Símbolo/ a b Ꜫ
Estados
0 - - {1,3}
1 2 - -
2 2 - -
3 - 4 -
4 - 4 -
1. Estados: 0, 1, 2, 3,4 3. Estado inicial: 0

2. Alfabeto: { Ꜫ, a, b } 4. Estados fìnales: { 2,4 }
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
a* Ø,a,aaaa,aaa…..a
a, aaa,aa…aaa
a+
Ø,a
a?
a|b
a,b
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
AUTOMATAS FINITO DETERMINISTA-AFD
Definiciòn
Un AFD es un caso especial de un AFN en el cual:
1. No existe transiciones Ø
2. Para cada estado S y cada símbolo de entrada a, hay a lo sumo una
arista etiqueta.
Un autómata finito “determinista” (AFD) siempre está en un solo
estado después de leer cualquier secuencia de entrada. El término
“determinista” hace referencia al hecho de que, para cada
entrada, existe un único estado al que el autómata pueda llegar
partiendo del estado actual. Por lo tanto es fácil determinar si un AFD
acepta una cadena, ya que hay a lo sumo un camino desde el
estado de inicio etiquetado con esa cadena.
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Un AFD es un modelo matemático formado por:
1) Un conjunto finito de “estados” S.
2) Un alfabeto de “símbolos de entrada” V
3) Un estado S0 que se considera “de inicio” o “inicial” (S0 ϵ S )
4) Un conjunto de estados F considerados “estados de aceptación” o
“finales”. (F incluye S )
5) Una función de transición “mueve” que toma como argumentos un
estado de S y un símbolo de entrada de V y devuelve un estado de S.
mueve : S x V → P(S) conjunto de estados
un AFD se puede denotar con la quíntupla : A = {S, V, S0, mueve, F}

Observación: en una AFD cualquiera sea el estado y cualquiera sea el
símbolo no habrá arista saliente con ese símbolo o habrá a lo sumo 1, o
sea, para cada estado y para cada símbolo existe una única alternativa.
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
(a|b)*abb La cadena en estudio se
llama “cadena candidata”. x
= bababbab → termina en 2
no aceptada
aaaaabb si
ababababb si
bbbabb si
ababababab no
Las imágenes son conjuntos,
pero al tratarse de un AFD
para cada par estado–símbolo
el conjunto es vacío ( - ) o
tiene un único estado
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Este autómata tiene la particularidad de que para cualquier estado –

símbolo hay una llegada, no tiene vacíos ( - ), se llama “tabla llena”.
Desde el punto de vista práctico esto quiere decir que cualquiera sea la
cadena, ya sea aceptada o no, va a ser leída completa, no aborta.
Ejem. De “tabla no llena”
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
DIAGRAMA DE TRANSICIONES
• Compuestos por estados y transiciones entre éstos
o Círculos: estados
o Arcos etiquetados: transiciones
• Sirven para representar lo que sucede a medida que se toman
caracteres de la entrada
o Cada círculo = un estado
o Cada arista = un carácter en la entrada
o Doble círculo = aceptación de un elemento léxico
o Asterisco = el último carácter se debe devolver a la entrada
(retroceso)
o Otro = cualquier carácter no asignado a otra flecha
• No tiene estados de error (sin transición = error)
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Ejemplo: se muestra un reconocedor de números enteros sin signo
mediante la ER [0-9]+ ò D+  D{0,1,…9} 3456+suma+
D D X=45+x
entero
Tabla de
transiciones D
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Para especificar correctamente el funcionamiento de un Analizador
léxico se debe utilizar una maquina de estados llamado Diagrama de
transiciones (DT) son grafos dirigidos muy parecidos a un AFD, con las
siguientes diferencias:
· Un AFD sólo dice si la cadena de caracteres pertenece al lenguaje o

no; un DT debe funcionar como un analizador léxico; es decir, debe leer
caracteres hasta que complete un
token, y en ese momento debe retornar (en los estados de aceptación) el
token que ha leído y dejar el buffer de entrada preparado para la
siguiente llamada.
· Un DT no puede tener estados de absorción (para cadenas incorrectas

en AFDs) ni de error (se considerará que las entradas para las que no
hay una transición desde cada estado son error).
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
· De los estados de aceptación de un DT no deben salir transiciones.
· En el caso de las tiras no específicas, necesitamos otro estado al que ir

cuando se lea un carácter que no pueda formar parte del patrón. En este
último estado (al que se llega con la transición especial otro) se debe
devolver al buffer de entrada el carácter leído (que puede ser parte del
siguiente token), lo cual se indica marcando el estado con un asterisco, y
se debe retornar el token correspondiente a ese estado de aceptación. Por
ejemplo, para reconocer números enteros, con un AFD son necesarios
solamente dos estados; con un DT necesitamos ese otro estado al que ir
cuando se lea un carácter que no pueda formar parte del número.
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
En el caso más general, se suelen utilizar estos diagramas de transiciones
para reconocer los tokens de entrada, construidos a partir de sus patrones
correspondientes, expresados mediante las respectivas expresiones
regulares. Estos autómatas se combinan en una máquina única que,
partiendo de un único estado inicial, sigue un recorrido u otro por los
estados hasta llegar a alguno de los estados de aceptación. En función de
en cuál se detenga devolverá un token u otro.
Si no llega a un estado de aceptación o recibe una entrada que no le
permite hacer una transición a otro estado, entonces dará error.
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Ejemplo: se muestra un reconocedor de números enteros sin signo
mediante la ER [0-9]+
El DT surge un nuevo estado, que es realmente el de aceptación y que

está marcado con un asterisco que indica que se llega a él leyendo un
carácter más de los necesarios para reconocer ese token, y por tanto hay
que devolver ese carácter a la entrada. La transición a ese estado se hace
mediante la entrada otro que significa cualquier otro carácter del
alfabeto del lenguaje que no esté en el rango [0-9].
Dra.Ing.
Msc.Sally
SallyTorres
Torres
• Se da prioridad al token con el lexema más largo:

– Si se lee “>=” y “>” se reconoce el primero.
• Si el mismo lexema se puede asociar a dos tokens, estos

patrones estarán definidos en un orden determinado.
• Ejemplo:
– while palabra reservada “while”
– letra (letra | digito)* identificador
– Si en la entrada aparece “while”, se elegirá la palabra reservada
por estar primero.
– Si estas especificaciones iniciales aparecieran en orden inverso, se
reconocería un token identificador
4
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Guía de resolución de
ejercicios
Uso de la desicion
24
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Ejercicios de autómatas finitos no
deterministas -AFN
Describir la expresión regular. 2 ejemplos de cadenas construir su
AFN escribir el MM. Y hacer tabla de transiciones
1. (a│b)? a*b+
2. (a│b) (a│b)
3. ab (a│b)? (a│bb)
4. a?(a│b) (a│b)*
5. b+ (a│bb)?a* b, ba
6. a (a│b)?ab*a
7. (a│b)*ba? (a│b)+
8. b? (aa*│bb*)a
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Ejercicios de diagramas de transiciones
1. Identificador y operadores lógicos (&&,||,!)

L(L|D)*
2. Operadores aritméticos, numero entero con signo, PR Do,
Done
3.-Identificador, operadores relacionales, PR repeat, rep,
Dra.Ing.
Msc.Sally
SallyTorres
Torres
Identificación de palabras reservadas
EJEMPLO: Constrúyase un diagrama de transiciones para el
reconocimiento de identificadores, números enteros sin signo y las
palabras reservadas “do” y “done”.
Notación: d = dígito; l = letra; t = otro; f = otro alfanumérico (dígito o
letra); a n = ir al estado n.

Identificación de palabras reservadas
EJEMPLO: Constrúyase un diagrama de transiciones para el
reconocimiento de números enteros con signo negativo o sin signo
(ER: (-|e)_d+ ) y los operadores suma (“+”) y doble incremento

Lexemas Patrones y Tokens
Componente léxico (token): Son las unidades lógicas que genera el
analizador léxico. Es el conjunto de cadenas de entrada que produce
como salida el mismo componente léxico.
Los componentes léxicos más comunes son los siguientes:
• palabras clave o reservadas.
•operadores aritméticos.
•operadores relacionales.
•operadores lógicos.
•operador de asignación.
•Identificadores.
•Constantes.
•Cadenas.
• literales.
•signos de puntuación.
•librerías
Especificaciones de Componentes léxicos
•Las expresiones regulares se utilizan para describir los componentes
léxicos de un lenguaje o tokens. Las expresiones regulares utilizan
varios tipos de operadores para definir los componentes léxicos:
• Paréntesis. Para agrupar símbolos
• Operación concatenación. Se permite la concatenación de cadenas.
• Operación alternativa. Se representa por |, y permite la elección
entre dos o más alternativas.

Especificaciones de Componentes léxicos
•Componentes léxicos:
a) Identificador: (Letra seguida de letras y dígitos). Se puede definir a
partir de dos símbolos: letra y dígito.
letra (letra|dígito)*
b) Constante entera
(sin signo) digito+
(con signo) (+|-) digito+
c) Constante de punto flotante sin exponente
(+|-) digito+.digito+
Abreviaturas en la notación
1. Uno o más casos de. +
2. Cero o un caso. ?
Conjuntos no regulares.-Aquellos lenguajes que no se pueden
describir con ninguna expresión regular.

Clase2 Sesion2

Cargado por

Copyright:

Formatos disponibles

Clase2 Sesion2

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Clase2 Sesion2

Cargado por

Copyright:

Formatos disponibles

Universidad Nacional del Callao

Maestría en Ingeniería de sistemas

Autómatas AFN y AFD

Dra. MSc. Mg. Ing. Sally Torres

Autómata finito no determinista

Guía practica de ejercicios

Teoría de lenguajes de Programación UPFIIS-UNAC Dra. Msc. Sally Torres

La teoría de autómatas es una rama de la teoría de la

Teoría de lenguajes de Programación UPFIIS-UNAC Dra. Msc. Sally Torres

Teoría de lenguajes de Programación UPFIIS-UNAC Dra. Msc. Sally Torres

Definición formal.- Un AFN es un modelo matemático formado por:

AFN = {S, V, S0, mueve, F}

1. Estados: 0, 1, 2, 3 3. Estado inicial: 0

Aceptación de una cadena por parte de un AFN

Aceptación de una cadena por parte de un AFN

1. Estados: 0, 1, 2, 3,4 3. Estado inicial: 0

mueve : S x V → P(S) conjunto de estados

un AFD se puede denotar con la quíntupla : A = {S, V, S0, mueve, F}

Este autómata tiene la particularidad de que para cualquier estado –

· Un AFD sólo dice si la cadena de caracteres pertenece al lenguaje o

· Un DT no puede tener estados de absorción (para cadenas incorrectas

· De los estados de aceptación de un DT no deben salir transiciones.

· En el caso de las tiras no específicas, necesitamos otro estado al que ir

El DT surge un nuevo estado, que es realmente el de aceptación y que

• Se da prioridad al token con el lexema más largo:

• Si el mismo lexema se puede asociar a dos tokens, estos

1. Identificador y operadores lógicos (&&,||,!)

Teoría de lenguajes de Programación UPFIIS-UNAC Dra. Msc. Sally Torres

Teoría de lenguajes de Programación UPFIIS-UNAC Dra. Msc. Sally Torres

Teoría de lenguajes de Programación UPFIIS-UNAC Dra. Msc. Sally Torres

Teoría de lenguajes de Programación UPFIIS-UNAC Dra. Msc. Sally Torres

También podría gustarte