Ensayo de Autómata Finito

INSTITUTO TECNOLÓGICO DE JIQUILPAN
INGENIERÍA EN SISTEMAS COMPUTACIONALES
Materia:
Lenguajes y Autómatas
Tarea:
Ensayo de autómata finito
Alumnos:
Ruvalcaba Mendoza Martin Eduardo
Profesor:
José Odiseo López Calderón
Jiquilpan, Michoacán, 30 de septiembre del 2022

Índice
Introducción…………………………………………………..…….. página 2
Autómata finito……………………………………………………... página 2
¿Cómo está formado?............................................................... página 2
Autómata finito determinista…………………………................... página 3
Autómata finito no determinista ………………………………….. página 3
Construcción de un autómata finito ……..………………………. página 4
Ejemplo…. …………………………………………………………..página 5
Conclusión…. …………………………..…………………………..página 5
Bibliografía …. …………………………………………….………..página 6
1|Página
Introducción.
Analizaremos que es un autómata finito, las diferencias que tienen un

autómata finito determinista y no determinista, como también la manera
en la cual están conformados y que restricciones tienen.
Al realizar esta investigación nos damos cuenta de la importancia que

estos tienen y las ventajas con las que cuenta, ya que es muy
importantes conocerlos para poder desarrollar un buen análisis.
Autómata finito
Los autómatas finitos son definidos por algunos autores como “Modelos
computacionales que realizan cómputos en forma automática sobre una
entrada para reproducir una salida” aunque también se podría definir
como conjunto finito de estados y conjunto de transacciones entre esos
estados, los cuales dependen de las restricciones que tenga el
autómata.
¿Cómo está formado?
Los autómatas finitos están formados por diferentes símbolos los cuales
ayudan a representar las diferentes partes de este.
- Q es un conjunto finito de estados.

- Σ es un alfabeto finito de símbolos terminales;
- q0 es el estado inicial en Q;
- δ es la relación de transiciones de la forma <qi,x,qj> con qi y qj
como estados de Q y x, símbolo de Σ ó puede ser también la
cadena vacía;
- F es el conjunto de estados finales o de aceptación y
(evidentemente) subconjunto de Q.
Los autómatas se encuentras separados en 2 grandes ramas como lo

son los autómatas finitos deterministas y no deterministas.
2|Página
Autómata finito determinista
Un Autómata finito determinista por sus siglas también conocidos como

AFD, es un tipo de autómata finito que además es un sistema
determinista, el cual cuenta con un estado de error y con cualquier
símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición
posible δ(q,a).
Estos tienen 2 principales casos que nunca se deben de dar como lo

son:
- Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2,
siendo q1 ≠ q2;
- Que existan transiciones del tipo δ(q,ε), salvo que q sea un estado
final, sin transiciones hacia otros estados.
Autómata finito no determinista
Un autómata finito no determinista por su siglas AFND es aquel que a

diferencia del determinista no contiene un estado de error, posee al
menos un estado q ∈Q, tal que para un símbolo a ∈ Σ del alfabeto, existe
más de una transición δ(q,a) posible.
Al contrario del determinista en este si se pueden dar los siguientes

casos:
- Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1
≠ q2;
- Que existan transiciones del tipo δ(q,ε), siendo q un estado no-
final, o bien un estado final pero con transiciones hacia otros
estados.
3|Página
Construcción de un autómata finito
- Estados: Los estados del autómata son representados por círculo.

Los nombres de los estados están escritos dentro de esos
círculos.
- Estado inicial: Estado en el cual el autómata inicia. El estado inicial
tiene una flecha apuntando hacia el.
- Estados Intermedios: Todos los estados intermedios tienen al
menos 2 flechas; una apuntando hacia el estado y otra apuntando
hacia otro estado.
- Estado Final: Si una cadena es cumplida exitosamente, se espera
que el autómata quede en este estado. Se representa con un
círculo doble. Puede tener una cantidad impar de flechas
apuntando hacia él y una cantidad par de flechas apuntando hacia
otros estados. El número de flechas impares es siempre uno más
que el de flechas pares.
- Transición: La transición de un estado a otro ocurre cuando un
símbolo deseado es encontrado en la cadena de entrada.
Después de una transición, un autómata se puede mover al
siguiente estado, o quedarse en el mismo estado. El movimiento
de un estado a otro es representado por una flecha dirigida, esta
flecha apunta al estado de destino. si el autómata se queda en el
mismo estado se dibuja una flecha que apuntara hacia el mismo.
4|Página
Ejemplo
Un autómata finito que contenga un valor de 3 dígitos binarios que
termine en 1.
Conclusión
Los autómatas finitos son una herramienta muy interesante
que nos ayuda a analizar el problema y desplegar un camino a
seguir de forma gráfica, ya que nos dan la perspectiva de el
camino a seguir para poder generar una cadena que tenga
ciertas restricciones.
5|Página
Bibliografía
Ricardogeek, Automatas Finitos Deterministas Y No Deterministas
https://ricardogeek.com/automatas-finitos-deterministas-y-no-
deterministas/
Mate fácil, Autómata Finito Determinista

https://www.matesfacil.com/automatas-lenguajes/automata-
finito-y-su-lenguaje.html
Ecu Red, Autómata finito

https://www.ecured.cu/Aut%C3%B3mata_finito#Definici.C3.B
3n_formal
Ciencias de la computación, Autómata finito

https://users.exa.unicen.edu.ar/catedras/ccomp1/ApunteAuto
matasFinitos.pdf
6|Página

Ensayo de Autómata Finito

Cargado por

Copyright:

Formatos disponibles

Ensayo de Autómata Finito

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

Ensayo de Autómata Finito

Cargado por

Copyright:

Formatos disponibles

INSTITUTO TECNOLÓGICO DE JIQUILPAN

INGENIERÍA EN SISTEMAS COMPUTACIONALES

Jiquilpan, Michoacán, 30 de septiembre del 2022

Autómata finito……………………………………………………... página 2

¿Cómo está formado?............................................................... página 2

Autómata finito determinista…………………………................... página 3

Autómata finito no determinista ………………………………….. página 3

Construcción de un autómata finito ……..………………………. página 4

Analizaremos que es un autómata finito, las diferencias que tienen un

Al realizar esta investigación nos damos cuenta de la importancia que

¿Cómo está formado?

- Q es un conjunto finito de estados.

Los autómatas se encuentras separados en 2 grandes ramas como lo

Un Autómata finito determinista por sus siglas también conocidos como

Estos tienen 2 principales casos que nunca se deben de dar como lo

Autómata finito no determinista

Un autómata finito no determinista por su siglas AFND es aquel que a

Al contrario del determinista en este si se pueden dar los siguientes

- Estados: Los estados del autómata son representados por círculo.

Mate fácil, Autómata Finito Determinista

Ecu Red, Autómata finito

Ciencias de la computación, Autómata finito

También podría gustarte