Unidad 3 Flashcards
(14 cards)
Máquina de Mealy
las máquinas de estados más simples, se reserva la denominación de máquinas secuenciales
ME = (ΣE, ΣS, Q, f, g)
donde:
ΣE : Alfabeto de símbolos de entrada
ΣS : Alfabeto de símbolos de salida
Q : Conjunto finito y no vacío, de estados posibles.
f : Función de transición, f: Q x ΣE → Q
g : Función de salida, g: Q x ΣE → ΣS
La función de transición f tiene la finalidad de definir el próximo estado que adoptará la máquina
a partir de su estado actual y cada uno de los posibles símbolos de entrada. De igual forma, la función de salida g define la salida de la máquina a partir de los mismos argumentos.
Máquina de Moore
La máquina de Moore tiene los mismos cinco componentes ya indicados para la máquina de Mealy, diferenciándose únicamente en su función de salida, ya que ésta solo depende del estado actual y no de la entrada en ese instante. Es decir que:
MO = (ΣE, ΣS, Q, f, g)
donde la función de transición f no cambia y en g hay una relación directa entre el estado en cada intervalo de tiempo y el símbolo de salida:
f: Q x ΣE → Q g: Q → ΣS
la máquina de Moore incorpora un retardo entre la entrada y la salida.
Autómatas Finitos Deterministas (AFD)
Si a la máquina secuencial de Mealy se le incorpora un estado inicial y un conjunto de estados de aceptación, estamos en presencia de un Autómata Finito Determinista (AFD).
AFDT=(ΣE,ΣS,Q,q0 ,A,f,g)
donde:
ΣE: Alfabeto de símbolos de entrada
ΣS: Alfabeto de símbolos de salida
Q : Conjunto finito y no vacío, de estados posibles
𝑞0: Estado inicial de operación, 𝑞0∈𝑄
A : Conjunto de estados de aceptación, A⊆Q
f : Función de transición, f:Q×ΣE→Q
g : Función de salida, g:Q×Σ E→ΣS
Automata Finitio Reconocedor
Si el AFDT se limita a reconocer o validar cadenas, resultan innecesarios su alfabeto de salida
y su correspondiente función de salida, por lo que ambas pueden ser eliminadas, dando lugar al
Autómata Finito Reconocedor (AFDR), que queda definido como una quíntupla:
AFDR = (ΣE, Q, q0, A, f)
¿Como una maquina sabe que ya termino de leer una cadena?
i) se conocen anticipadamente los largos de las cadenas a ser leídas
ii) los caracteres son recibidos con una periodicidad regular
iii) el mensaje termina con un carácter especial.
¿Como se detiene una maquina?
i) la función de transición es parcial, no estando definido un próximo estado (la cadena es, por lo tanto, rechazada)
ii) se completó la lectura de la cadena de entrada.
En esta última condición, puede ocurrir que:
a) la máquina se encuentra en un estado de aceptación (qeA) y, por eso, la cadena es aceptada o reconocida
b) se encuentra en cualquier otro estado (qe/A), lo que indica que la cadena es desconocida o rechazada.
Configuracion instantanea y de Aceptacion
Kt de un autómata finito en un intervalo de tiempo t al par ordenado: Kt=(q,β);conq∈Q,β∈ΣE∗ donde q representa el estado en el que se encuentra y β el sufijo o subcadena de entrada que está pendiente de ser leída.
configuración de aceptación como:
donde Kn=(qn,λ);dondeqn ∈ A,n=∣α∣
Extensión al tratamiento de palabras
proceso mediante el cual un autómata finito (determinista o no determinista) procesa cadenas completas de símbolos (palabras) del alfabeto de entrada, no solo símbolos individuales.
f^:Q×Σ∗ → Q
Aceptación de palabras y lenguajes
la aceptación de una cadena por parte de un AFD implica dos condiciones simultáneas:
i) la completa lectura de la cadena de entrada α
ii) el arribo a un estado de aceptación. Por el contrario, si qn(e/)A la cadena α habrá sido rechazada.
L(M)={α∣α∈Σ E∗y(q 0,α) ⊢∗ (qn,λ)yqn∈A}
Accesibilidad entre estados y AFD Conexo
Accesibilidad entre estados
En un AFD, se dice que un estado p es accesible desde otro estado q, y se representa pAq, si existe una palabra de símbolos de entrada que haga transitar el autómata desde el estado q hasta el estado p. En símbolos:
pAq↔∃α∈ΣE∗/f ∗(q,α)=p,conp,q∈Q
Autómatas conexos
Si todos los estados de un autómata son accesibles desde su estado inicial, se dice que el mismo es conexo. En símbolos:
UnAFDesconexo↔∀pi∈Q:piAq0
Equivalencia entre estados:
Dos estados p,q e Q de un AFD se dice que son equivalentes, si desde cualquiera de los estados se aceptan y rechazan exactamente la mismas cadenas.
pEq↔[∀α∈ΣE∗ : f^(p,α)∈A↔ f^(q,α)∈A]
Cumple con la teoria de conjuntos equivalentes que necesitan que cumplan las propiedades de:
- Reflexividad
- Simetría
- Transitividad
Equivalencia entre autómatas
Dos AFD denominados A1 y A2, se dice que son equivalentes y se representa A1EA2, si ambos aceptan las mismas palabras o sentencias, esto quiere decir que dos autómatas son equivalentes si sus estados iniciales son iguales y si y solo si generan el mismo lenguaje. Simbolicamente:
A1EA2 ←→ L(A1)=L(A2)
Conjunto cociente:
conjunto que tiene por elementos a todas las clases de equivalencia o subconjuntos de estados equivalentes entre sí que puedan distinguirse en el conjunto de estados Q. Por ser la base de este agrupamiento, la relación de equivalencia entre estados E, el conjunto cociente se denota Q/E.
Minimización de autómatas
La minimizacion consiste en llevar un automata a uno equivalente pero con menos expresiones.
se recurre al concepto de conjunto cociente visto con anterioridad, es decir, a la partición del conjunto de estados Q producida por la relación de equivalencia E, que tiene por elementos a las clases de equivalencia, donde se agrupan todos los estados equivalentes o indistinguibles entre sí.
