- LENGUAJE ACEPTADO POR UN FSA
- FSA DETERMINISTICO Y NO DETERMINISTICO
- LENGUAJE ACEPTADO POR UN NFA
- CONVERSION DE UN NFA EN UN DFA EQUIVALENTE
- computadora = maquina
- AUTOMATAS DE ESTADOS FINITOS (FSA)
- CADENAS DE ENTRADA Y SALIDAS PARA UNA FSM
- una maquina de estados finitos denotada como M = {S,I,O,F,g,s0} es un modelo abstracto de una maquina, el cual consiste en un conjunto finito S de estados, un conjunto finito I de simbolos de entrada, un conjunto finito O de simbolos de salida, una funcion de transicion f que asigna un nuevo estado a cada par de estados y entrada.
- Una FSM genera una cadena de salida correspondiente a una cadena de entrada. Por ejemplo la cadena de entrada para la FSM la cadena de salida sera 10001 correspondiente a los simboos de entrada
- Una automata de estados finitos es un modelo abstracto de una maquina que consiste en un conjunto finito "S" de estados. Algunas veces se denota las letras del mismo significado pero consiste en dos simbolos de salida 0 y 1
- Cuando los simbolos de una cadena de entrada se alimentan secuencialmente a una FSM estos cambian los estados del automata de manera sucesiva y el utomata termina en cierto estado, el conjunto de todas las cadenas que son aceptadas por M se onoce como lenguaje acptado o reconocido. Dos automatas de estado finito se dice que si son equivalentes aceptan el mismo lenguaje.
- Si un automata de estados finitos la funcion de transicion asigna un unico estado siguiente a cada par de estado y entrada se llama automata de estados finitos deterministicos. por otro lado si la funcion d transision asigna varios estados siguientes a cada par de estado y entrada se le llama automata de estados finitos no deterministicos.
- Una cadena no nula se dice que ser aceptada por un NFA si existe al menos una trayectoria en el diagrama de estados empzando en el estado inicial y terminando en el esrado de aceptacion ya se ha señalado que si dos FSA aceptan el mismo lenguaje los dos son equivalentes.
- Cada estado de M sera un subconjunto de S de manera correspondiente el estado iniial de M l conjunto de simbolos de entrada de M es el mimmo que I y a es el simbolo de entrada alimentando a este estado.