Automatas su definicion y tipos con ejemplos

Automatas y su teoria

1. AUTÓMATAS
TAREA #2 - LABORATORIO LENGUAJES FORMALES Y DE PROGRAMACIÓN
VALERY PAMELA ALARCÓN RAMOS - 202300794

2. ¿QUÉ SON?Un autómata es un modelo matemático de
una máquina abstracta utilizada para simular
el comportamiento de sistemas lógicos.
Los autómatas procesan una secuencia de
entradas y producen una salida según un
conjunto predefinido de reglas.
Se utilizan ampliamente en la teoría de la
computación, el análisis de lenguajes
formales y el diseño de sistemas digitales.

3. DEFINICIÓNSe define formalmente como una quíntupla (o séxtupla,
dependiendo del tipo de autómata) que incluye un conjunto
de estados, un alfabeto de entrada, una función de transición,
un estado inicial y un conjunto de estados de aceptación.
La definición varía ligeramente según el tipo específico
de autómata.

4. Autómata Finito
Determinista
DFA
tiene número finito
de estados
para cada estado y
símbolo de entrada
hay una única
transición definida
se utiliza para
reconocer lenguajes
formales
TIPOS
Autómata De Pila
PDA
extiende el DFA con
una pila que
proporciona
memoria extra
se utiliza para
reconocer lenguajes
libres de contexto
puede ser
determinista o no
determinista.
Autómata Finito No
Determinista
NFA
permite múltiples
transiciones para un
mismo símbolo de
entrada y estado
para cada estado y
símbolo de entrada hay
una única transición
definida
se utiliza para
reconocer lenguajes
formales
Máquinas De Turing
más poderoso que
puede similar cualquier
algoritmo
computacional
consiste en una cinta
infinita que actúa como
memoria y un cabezal
de lectura/escritura
usado para estudiar
computabilidad y límites
de lo que las máquinas
pueden calcular

5. COMPONENTES PRINCIPALESEstados (Q): un conjunto finito de estados que el autómata puede asumir.
Alfabeto de entrada (Σ)): un conjunto finito de símbolos que el autómata puede
procesar.
Función de Transición(δ): define cómo se mueve el autómata de un estado a otro en
función del símbolo de entrada.
Estado inicial(q0): el estado en el que comienza el autómata.
Estados de aceptación(F): un subconjunto de estados en los cuales, si el autómata
termina su procesamiento, la entrada es aceptada.

6. EJEMPLOS
Autómata Finito Determinista DFA Autómata De Pila PDA

7. EJEMPLOSAutómata Finito Determinista DFA
DFA con dos estados (q0 y qf), donde:
Estado q0: Es el estado inicial.
Estado qf: Es el estado de
aceptación.
Transiciones:
q0 a sí mismo con la entrada 0.
q0 a qf con la entrada 1.
qf a sí mismo con la entrada 1.
qf a q0 con la entrada 0. Autómata De Pila PDA
PDA con tres estados (q0, q1, y q2), donde:
Estado q0: Es el estado inicial.
Estado q2: Es el estado de aceptación
Transiciones:
De q0 a q0:
Con la entrada a y la cima de la
pila Z, se empuja AZ en la pila.
Con la entrada a y la cima de la
pila A, se empuja AAA en la pila.
De q0 a q1:
Con la entrada b y la cima de la
pila A, se hace pop (se elimina A
de la pila).
De q1 a q1:
Con la entrada b y la cima de la
pila A, se hace pop.

8. EJEMPLOS
Autómata Finito Determinista DFA
Entrada: 0011
q0 (Inicio) → Lee 0 → Permanece en
q0.
q0 → Lee 0 → Permanece en q0.
q0 → Lee 1 → Transición a qf.
qf → Lee 1 → Permanece en qf
(Aceptación).
La cadena 0011 tiene un número impar de
1s y es aceptada por el autómata.
Autómata De Pila PDA
Entrada: aabbb
q0: Lee a → Empuja A en la pila.
q0: Lee a → Empuja A en la pila.
q0: Lee b → Transición a q1 y hace
pop de A.
q1: Lee b → Hace pop de A.
q1: Lee b → No hay más A en la pila.
La pila está vacía y el autómata llega a
q2, lo que significa que la cadena es
aceptada porque tiene igual número de
as y bs.

9. CONCLUSIÓNLos autómatas son fundamentales en la teoría de la
computación y tienen aplicaciones prácticas en el diseño de
compiladores, procesamiento de texto, sistemas digitales y
más.
Entender los diferentes tipos y componentes de los autómatas
es esencial para explorar la computación y los lenguajes
formales.