- Una computadora digital puede considerarse como una maquina.
- Una FSM suele representar en forma conpacta por medio
de una tabla llamada tablas de estados o tabla de transicion o mediante
un diagrama que recibe el nombre de diagrama de
estados o diagrama de transicion.
- CADENA DE ENTREDA Y SALIDA PARA UNA FSM.
- una FSM genera una cadena de salida
correspondiente a una cadena de entrada
- AUTOMATAS DE ESTADOS FINITOS (FSA)
- un tipo especial de FSM que se llama automata de
estados finitos (FSA) es de interes especial
ya que se puede conocer cadenas de un lenguaje.
- LENGUAJE ACEPTADO POR UNA FSA
- cuando los simbolos de una cadena de entrada
se alimentan secuencialmente a una FSM M estos cambian
los estados del automata de manera
sucesiva y el automata termina en cierto estado.
- FSA DETERMINICOS Y NO DETERMINICOS
- si un automata de estados finitos , la funcion
de transicion asigna un unico estado siguiendo a cada
par de estado y entrada entonces el FSA
se llama automata de estado finito determinico (DFA)
- LENGUAJE ACEPTADO POR UN NFA
- Una cadena no nula α se dice que sera haceptada por
un NFA si existe al menos una trayectoria que
represente a α en el diagrama de estados
empezando en el estado inicial y terminando
en el estado de aceptacion
- CONVERSION DE UN NFA EN UN DFA EQUIVALENTE
- considerese que el NFA dado es M = {S,I,f,s₀,A}
y sea M'́ el DFA equivalente que se requiere .