El conjunto de todas las cadenas que son acepatadas por M se conoce como lenguaje aceptado o reconocido por M. Dos automatas de estado finitos se dice que son equivalentes, si aceptan el mismo lenguaje.
CADENAS DE ENTRADA Y SALIDAS PARA CADA FSM
AUTOMATA DE ESTADOS FINITOS(FSA)
LENGUAJE ACEPTADO POR UN 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 DETERMINISTICO Y NO DETERMINISTICO
Si un automatade estado finitos, la funcion de transicion asigna un unico estado siguiente a cada par de estado y entrada, entonces el FSA se llama automata de estados finitos deterministico.
si la transicion asigna varios estados siguientes a cada par de estado y entrada, el FSA se llama automata de estados finitos no deterministico
LENGUAJE ACEPTADO POR UN NFA
una cadena no nula α se dice que sera aceptada por un NFA si existe al menos una trayectoria que represente α en el diagrama de estados empezando en el estado inicial y terminando en el estado de aceptacion
Una FMS genera una cadena de salida correspondiente a una cadena de entrada cunado se lee la cadenade entrada simbolo por simbolo(de izquierda a derecha, cada smbolo de entrada lleva a la FSM de un estado a otro. Puesto que cada transicion produce una salida,una cadena de entrada tambien produce una cadena de salida. sSi x = x1,x2,…xn es la cadena de entrada, la cadena de salida correspondiente Y = y1,y2,…yn esta dada por Yi = g(si – 1,xi) para i = 1,2,...,n,
Si = f(si-1,xi) para i = 1,2,...,n,