Scribd
Cargar
203 vistas7 páginas

Autómatas Y Lenguajes Formales Diseño de Autómatas

Este documento presenta ejercicios sobre autómatas finitos y su conversión a expresiones regulares. En el ejercicio 1, se caracteriza un autómata finito no determinista y se convierte a la expresión regular a+b*+c+(b+bab*) mediante el método de eliminación de estados. En el ejercicio 2, se caracteriza un autómata finito no determinista diferente y se explica el procedimiento para convertirlo a un autómata finito determinista. Finalmente, se invita a practicar y verificar los conceptos aprendidos

Cargado por

Cristian Camilo Gonzalez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
203 vistas7 páginas

Autómatas Y Lenguajes Formales Diseño de Autómatas

Este documento presenta ejercicios sobre autómatas finitos y su conversión a expresiones regulares. En el ejercicio 1, se caracteriza un autómata finito no determinista y se convierte a la expresión regular a+b*+c+(b+bab*) mediante el método de eliminación de estados. En el ejercicio 2, se caracteriza un autómata finito no determinista diferente y se explica el procedimiento para convertirlo a un autómata finito determinista. Finalmente, se invita a practicar y verificar los conceptos aprendidos

Cargado por

Cristian Camilo Gonzalez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

AUTÓMATAS Y LENGUAJES FORMALES DISEÑO DE AUTÓMATAS

Anyi Andrea Murcia Prada


Código: 1014256918

TUTOR
Edgar Antonio Cortes

Universidad Nacional Abierta y a Distancia


José Acevedo y Gómez
Bogotá 2020
Ejercicios 1: Autómata a Expresión regular

EJERCICIO A
REALIZAR

Caracterización En este espacio se realiza:


del autómata - Identificación de la quíntupla del autómata :
K = {q0,q1,q2}
∑ = {a,b,c}
s = q0
F = q2
δ=
δ{q0,a} = q1
δ{q1,b} = q1
δ{q1,c} = q2
δ{q2,a} = q0
δ{q0,b} = q2

- Plasme la tabla de transición:


q σ δ(q,σ)
→q0 a q1
→q0 b q2
q1 b q1
q1 c q3
#q2 a q0

- Identificación del Autómata Finito Determinista o


Autómata Finito No Determinista:
Se trata de un autómata Finito no Determinista:

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


Autómata Finito no Determinista: se caracteriza por tener
transiciones vacías o que por cada símbolo desde un
estado de origen se llega a más de un estado destino.
Procedimiento de Realice de manera detallada el procedimiento paso a
conversión de paso de la conversión del autómata a expresión regular y
Autómata Finito a según ejemplo revisado:
Expresión Regular
paso a paso  Se realizara por método de Eliminación:
 Empezamos por Eliminar el estado “Q1” trazando
el camino de q0 hasta q2 quedando de la siguiente
manera:

a+b*+c

 Luego se procede a eliminar “Q0” quedando

a+b*+c+(b+bab*)

Autómata Final Por método de eliminación:


convertido a+b*+c+(b+bab*)

Desde la aplicación JFLAP:

Lenguaje regular a+b*+c+(b+bab*)

Ejercicios 2: Conversión de Autómatas Finitos Deterministas a Autómatas Finitos


No deterministas (AFD a AFND) y viceversa.
EJERCICIO A
REALIZAR

Caracterizació En este espacio se realiza:


n - Identificación de la quíntupla del autómata :
del autómata K = {q0,q1,q2}
∑ = {a,b,c}
s = q0
F = q1
δ=
δ{q0,a} = q1
δ{q0,b} = q0,q2
δ{q1,b} = q0
δ{q1,c} = q2
δ{q2,b} = q1

- Plasme la tabla de transición:


Estados a b c
→q0 q1 q0,q2 ....
#q1 ….. q0 q2
q2 ….. q1 …..

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


Finito No Determinista:
Se trata de un autómata Finito no Determinista:

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


Autómata Finito no Determinista: se caracteriza por tener
transiciones vacías o que por cada símbolo desde un estado de
origen se llega a más de un estado destino.
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
de Autómata revisado:
Finito a
Expresión  Se realizara proceso de conversión de AFND a AFD
Regular paso  Se genera la tabla con nuevos estados para quitar los
a paso indeterminismos

Estados a b c
→q0 q1 q0,q2 ....
#q1 ….. q0 q2
q0,q2 q1 q0,q2,q1 …..
q0,q2,q1 q1 q0,q2,q1 q2
q2 ….. q1 …..

 Se grafica la información:

Autómata
Final
convertido
Practicar y
verificar lo
aprendido
REFERENCIAS BIBLIOGRAFICAS

Unad (2020), Autómatas y lenguajes formales, encuentro sincrónico, Recuperado


de:[Link]
usp=sharing

Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales. Universidad


de Extremadura. Servicio de Publicaciones. (pp. 39 - 70). Recuperado de:
[Link]
url=[Link]
direct=true&db=edsbas&AN=edsbas.62161440&lang=es&site=eds-
live&scope=site

También podría gustarte