AUTOMATAS Y LENGUAJES FORMALES

TRABAJO COLABORATIVO 2

LENGUAJES REGULARES

Tarea 2 Diseño de autómatas

TUTOR:
VERMEN RAINER AYALA

PRESENTADO POR :

RAFAEL ALONSO VERGARA

JESUS FERNANDO SALAZAR
HERNANDO SANCHEZ GIL
DANNY LEANDRO SURITICA

OCTUBRE 2020_BOGOTA D.C

 EJERCICIO DE LA FASE 2

ACTIVIDAD INDIVIDUAL

Pasos de la estrategia de aprendizaje a desarrollar

Paso 1. Revisión de los contenidos de la Unidad 1. El estudiante debe ingresar al

entorno de aprendizaje Unidad 1 y revisar las referencias requeridas para la Unidad.

EJERCICIO A Registre aquí el Ejercicio a trabajar. Por favor agregue la imagen

TRABAJAR -

Caracterizació En este espacio se realiza:

n del autómata - Identificación de la quíntupla del autómata

Elementos de la 5tupla = ( K, ∑, &, S, F)

M
M = {q 0, q 1,q 2,} {a, b, c } (cada un de los estados que
conforman el autómata
&, 0, { q 2} Estado inicial y estado final
q
K = {q 0, q 1,q 2} (Los estados )
∑ {a, b, c} Alfabeto
S = q 0 (Estado Inicial) |
F = q 2 (Estado Final )
- Plasme la tabla de transición

ESTADOS - ALFABET - TRANSICIONES

O
Q0 > - a - q1
Q0 > - b - q2
Q1 - c - q2
Q2 - a - q0
Q0> - b - q2

- Identificación del Autómata Finito Determinista o Autómata

Finito No Determinista

Según el ejercicio correspondiente al autómata demarca dado con

b, que me corresponde o número b, es un autómata
determinista, por los siguientes motivos

a) El Autómata Finito Determinista:

(AFD)
El autómata finito determinista; quiere decir que con transición
a, podemos ir de un estado a otro; pero con esta misma
transición a , no podemos ir desde este estado a otro estado con
la misma transición
 Entendiendo que no se llega a dos estados al mismo
tiempo, con la misma transición

Aplicando el ejemplo el ejercicio B Seria de la siguiente

manera
Es decir

1. quiere decir que de acuerdo este ejercicio b, que con

la letra transición a vamos de q 0 a q 1, Pero con
 transición a, no volvemos a salir de q 0 y llegar a q 2 ,
porque si no ya no sería un autómata finito
determinístico

 EL determinismo, indica precisamente que no existe dos

estados finales o dos estados del Llegada, con la misma
transición

b. ) El Autómata Finito No
Determinista: (AFND)

Un Autómata Finito No Determinista (AFND) Es un autómata

finito, pero con características como:

 Posee un estado con muchas transiciones

 Transiciones sin leer entradas
 Transiciones de un estado final con transiciones a otros
estados

El Autómata Finito No Determinista, quiere decir que, con La

misma letra transición, podemos ir de un estado a varios
estados

Las propiedades de un autómata finito no determinista son

muy similares a los de un autómata Finito determinista
Simplemente que en su función sigma o en la función de
transición se utiliza una mayor amplitud teniendo en cuenta
que podemos llegar desde un estado inicial a varios estados
con la m isma transición

Ejemplo
 En esta autómata, vemos una imagen con 4 estados; q 0 ,q 1 q 3 q2

, específicamente tenemos que desde el estado inicial q 0 ,con

transición 0, Vamo a , q 1 , y con la misma transición inicial q 0 ,
podemos ir a q 2

Procedimiento Realice de manera detallada el procedimiento paso a paso de la

de conversión conversión del autómata a expresión regular y según ejemplo
de Autómata revisado.
Finito a
Expresión  Paso 1… para hallar la expresión Regular de este autómata
Regular paso a
paso
Autómata Final
convertido

Definición Expresiones regulares.

 Una expresión Regular es un equivalente algebraico para un autómata
 Utilizado en muchos lugares como un lenguaje para describir patrones en
texto que son sencillos pero muy útiles
 Pueden definir exactamente los mismos lenguajes que los autómatas pueden
describir: lenguajes regulares
 Ofrecen algo que los autómatas no : Manera declarativa de expresar las
 cadenas que queremos aceptar
Las expresiones regulares denotan lenguajes

TABLA DE TRANSICION

ESTADOS - ALFABET - TRANSICIONES

O
Q0 > - a - q1
Q0 > - b - q2
Q1 - c - q2
Q2 - a - q0
Q0> - b - q2

Procedimiento de conversión de Autómata A expresión

regular paso a paso

Método de eliminación x eliminación de estados

De acuerdo al ejercicio b

Paso 1. Inferimor que son dos expresiones que son dos expresiones q 0
A q 2 , pasando por q 1 , y de q 0 a q 2 ,,
Paso 2, eliminamosq 1 ,quedando de la siguiente manera
 Paso 3. Eliminamos q 0 ,, quedando asi :

Autómata Final Convertido

Lenguaje ER((b+ab*c)a)*
regular
Ejercicios 2: Conversión de Autómatas Finitos Deterministas a Autómatas Finitos
No deterministas (AFD a AFND) y viceversa

Para este autómata del ejercicio No.2 corresponde :

A un Autómata Finito No Determinista, quiere decir que, con La misma letra

transición, podemos ir de un estado a varios estados.

EJERCICIO A Registre aquí el Ejercicio a trabajar. Por favor agregue la imagen

TRABAJAR

En este espacio se realiza:

- Identificación de la quíntupla del autómata
Caracterizació
n del M
autómata
M = {q 0, q 1,q 2,} {a, b, c } (cada un de los estados que
conforman el autómata
&, q 0, { q 1} Estado inicial y estado final
K = {q 0, q 1,q 2} (Los estados )
∑ {a, b, c} Alfabeto
S = q 0 (Estado Inicial) |
F = q 1 (Estado Final )

- Plasme la tabla de transición

ESTADOS - ALFABET - TRANSICIONES
O
Q0 > - a - q1, q2
Q1 > - b - q0
Q1 > - c - q2
Q2 > - b - q1, q2

- Identificación del Autómata Finito Determinista o Autómata

 Finito No Determinista

El Autómata Finito No
Determinista: (AFND)

De Acuerdo al ejercicio este es un Autómata Finito No

Determinista (AFND) Es un autómata finito, pero con
características como:

 Posee un estado con muchas transiciones

 Transiciones sin leer entradas
 Transiciones de un estado final con transiciones a otros
estados

El Autómata Finito No Determinista, quiere decir que, con La

misma letra transición, podemos ir de un estado a varios estados

Las propiedades de un autómata finito no determinista son

muy similares a los de un autómata Finito determinista
Simplemente que en su fu

nción sigma o en la función de transición se utiliza una

mayor amplitud teniendo en cuenta que podemos llegar
desde un estado inicial a varios estados con la m isma
transición

 Quiere decir que teniendo en cuenta el autómata, con q 0 con transición a

podemos ir a q 1 , y tambien podemos ir a q 2 ,

 Por otro lado, con transición b, podemos ir desde

q 2 , hacia el mismoq 2tambien al mismo tiempo vamos con

- Explicar las características del tipo de autómata

Procedimiento Realice de manera detallada el procedimiento paso a paso de la
de conversión conversión del autómata según corresponda y según ejemplo
paso a paso revisado.

Procedimiento para la transformación de Autómata Finito

No determinista a Autómata Finito Determinista

- Paso 1…

El siguiente autómata se compone de 3 estados, q0,q2,q3

Identificamos el estado inicial que es q 0
El estado final que es q 2
El alfabeto maneja dos símbolos el a , b, c
Ya teniendo identificado estos pasos por consiguiente procedemos a realzar nuestra
tabla de transición

Paso 2- Realizamos la tabla de transición, para este caso identificamos los estados y el
alfabeto
De manera vertical manejamos los estados que maneja el autómata y de manera
horizontal agregamos los alfabetos o la cantidad de símbolos que maneja el alfabeto

TABLA DE TRANSICION

ESTADO - a - b - c
S
Q0 > q1, q2 - …………… ……………
q1, q2 ………… - q 2 , q1 - q2

Procedemos a dibujar el automata de acuerdo a los resultados obtenidos en la tabla de

transicion y vemos que esta convertido en un Autómata Finito
Determinista
Autómata En este espacio se presenta el autómata final
Final
convertido

Practicar y - Muestre en el simulador JFLAP (Anexo 1 - JFLAP) o VAS (Anexo

verificar lo 2- VAS) (gráficamente) como recorre una cadena válida.
aprendido Explique cada secuencia. (No se trata solo de captura las
imágenes, estas deben ser explicadas en pie de página o de
lo contrario no tienen validez)

 Para validar el automata le damos a Imput

 Steep withclosure

Por consiguiente, le damos la cadena que vamos a validar
En este caso le ingresamos varias cadenas

Vemos que nos acepta una cadena, el resto son rechazadas

Al recorrer la cadena tenemos:

Posición inicial de la cadena qo

Vemos que de las cuatro cadenas, solo me valida la cadena abba

Trabajo Colaborativo
Ejercicio Grupal
 Construir un autómata que realice lo siguiente
ER: {(a)*+cd(ab)*b}

EJERCICIO A TRABAJ A Registre aquí el Autómata realizado. Por favor agregue la imagen
TRABAJAR

NOTACION FORMAL En este espacio agrega la notación formal del autómata. Identifique la quíntupla del
DEL AUTOMATA autómata creado.
MINIMIZADO
CARACTERIZACION Identifique los elementos (tupla, estado final, inicial, alfabeto, etc.). Debe explicar y
DEL AUTOMATA describir cada elemento y la función y significado en el autómata.
PARTE TEORICA Conceptos y definiciones adicionales.

En este espacio se realiza:

- Identificación del Autómata Finito Determinista o Autómata
Finito No Determinista
- Explicar las características del tipo de autómata

DEFINICION DE TIPO DE AUTOMATA

Según el ejercicio, Realizado con el autómata ¿es un Autómata

finito no determinista. Es el autómata Finito que tiene transiciones vacías o
que por cada Símbolo desde un estado de origen se llega a más de un estado
destino, vemos que del estado q 14 ,
Nos dirigimos al estado q15, con transición ʎ, y con esta misma transición
de ʎ,, podemos volver al estado q 14 , al igual tenemos otro ejemplo en el
autómata que es ; del estado q 8 ,a q 9 , nos podemos dirigir con, el
estado de transición vacia (ʎ) al igual con esta misma transición nos
devolvemos al estado q 8
Es decir, en este caso el autómata presenta transiciones vacías y tiene al menos un
estado el cual permite llegar a mas de un estado de destino
ELEMENTOS DE LA QUITUPLA
Elementos de la 5tupla = ( K, ∑, &, S, F)
M
M{q 0,q 1 q 2 q 3 q4 q 5 q6 q7 q 8 q 9 q10 q11 q 12 q13 q14 q 15 q 16 q 17 q 18 q 19{a, b, c,cd, ab, ʎ, {
} (cada un de los estados que
conforman el autómata
&, q 0, { q 1} Estado inicial y estado final
K = q 0,q 1 q 2 q 3 q4 q 5 q6 q7 q 8 q 9 q10 q11 q 12 q13 q14 q 15 q 16 q 17 q 18 q 19} (Los estados )
∑ {a, b, c, cd, ab, ʎ, { } Alfabeto
S = q 0 (Estado Inicial) |
F = q 1 (Estado Final)
a b c d cd ab ʎ {
¿ Q0 Q2
¿ Q1
Q2 Q6
Q3 Q1
Q4 Q 10
Q5 Q1
Q6 Q7
Q7 Q20
Q8 Q 20
Q9 Q8
Q 10 Q4
Q11 Q12
Q 12 Q 13
Q 13 Q 14
Q 14 Q 22
Q 15 Q 24
Q 16 Q 17
Q 17 Q18
Q 18 Q 19
Q 19 Q5
Q 20 Q 21
Q21 Q9
Q 22 Q 24
Q23 Q 15
Q 24 Q 25
Q25 Q26
Q 26 Q 27
Q27 Q23
LENGUAJE REGULAR ER = {(a)*+cd(ab)*b}

Expresión Regular del autómata

 TRABAJO COLABOTATIVO JESUS FERNANDO SALAZAR

Construir autómata:
Construir un autómata que realice lo siguiente:
ER = {(a)*+cd(ab)*b}
EJERCICIO GRUPAL

Notación Formal Identificación de la quíntupla del autómata

A=({q0 , q1 }, { a , b , c , d } , δ ,q 0 , q1)

Caracterización del autómata

Q={q 0 , q 1 }
Σ= { a ,b ,c , d }
δ =¿ Ver tabla de Transicion
q 0=q 0
F={q1 }
Tabla de transición:
a b c d
→q0 q0 -- q1 q1
#q1 q1 q1,q0 -- --
  Autómata Finito No Determinista
Explicar las características del tipo de autómata: cada
entrada existe más de una transición o varios estados
con el mismo símbolo

Lenguaje regular ER = {(a)*+cd(ab)*b}

Validación de cadenas 5 aceptadas y 5 rechazadas