- Automata para estados finitos(FSA)
- Cadena de entrada y salidas para una FSM
- FSA deterministico y no deterministico
- Lenguaje aceptado por un FSA
- Conversion de un NFA en un DFA equivalente
- Lenguaje aceptado por un NFA
- Una FSM genera una cadena de salida correspondiente a una cadena de entrada.Cuando se lee la cadena de entrada simbolo por simbolo (de izquierda a derecha), cada simbolo de entrada lleva ala FSM de un estado a otro. Puesto que cada trancicion produce una salida, una cadena de entrada tambien produce una cadena de salida.
Por ejemplo la cadena de entrada para la FSM es aabba, la cadena de salida seria 10001.
- Una cadena no nula a se dice que sera aceptada por una NFA si existe almenos una trayectoria que representa a a en el diagrama de estado enpezando en el estado inicial y terminado en el estado de aceptacion. El conjunto de todas las cadenas aceptadas por un NFA recibe el nombre de lenguaje aceptado por el NFA.
por ejemplo, las cadenas aab, aaba, aabaa son aceptadas, pero las cadenas abb, aabb, ababb son rechazadas por el NFA indicado.
Ya se ha señalado que si dos FSA aceptan el mismo lengiaje, estos son equivalentes.
Ademas cualquier NFA puede convertirce en un DFA equivalente en virtud del siguiente teorema que se establece sin demostracion:
Teorema:
Si un lenguaje L es aceptado por un NFA, existe entonces un DFA que tanvien acepta a L.
- Cuando los símbolos de una cadena de entrada se alimentan secuencial-
raente a una FSM M éstos cambian los estados del autómata de manera
sucesiva y el autómata termina en cierto estado. Si el último estado es un estado de
aceptación del autómata se dice que la cadena será aceptada o reconocida por M
En otro caso, se afirma que será rechazada por M. El conjunto de todas las cadenas
que son aceptadas por M se conoce como lenguaje aceptado o reconocido por
^b M. Dos autómatas de estados finitos se dice que son equivalentes, si aceptan
j el mismo lenguaje.
- Considere que el NFA dado es M= {S, I,f, % A} y sea M' el DFA equivalente que se requiere. Cada estado de M' será un subconjunto de S. De manera correspondiente el estado inicial de M' es {sQ}. El conjunto de símbolos de entrada de M' es el mismo que 2". Si ¡s¡ , s,- ,... s¡ j es un estado de M' y a es el símbolo de entrada alimentado a este estado, el siguiente estado de M' es la unión de los conjuntos f(.s¡ f(s¡n )>.. o f(s¡ ), donde/es la función de transición de M. De tal modo, los estados de M' son algunos de todos los subconjuntos de S incluyendo el conjunto vacio (j). Los estados finales de M' son aquellos que contienen a ios estados finales de M.
- FSA deterministico y no deterministico
Conciderando que el NFA dado es M=FSA
Si en un autómata de estados finitos, la función de transición asigna un único estado siguiente a cada par de estado y entrada, entonces el FSA. se llama autómata de estados finitos determimstico (DFA). El FSA dado en los ejemplos anteriores es de este tipo. Por otro lado, si la función de transición asigna varios estados siguientes a cada par de estado y entrada, el FSA se llama autómata de estados finitos no de-terrninistico (NFA).
En otras palabras, un NFA denotado como M= {S, Lf, sQ, A}, consiste en un conjunto S de estados, un alfabeto de entrada i, una función de transición que asigna un conjunto de estados a cada par de estado y entrada, un estado final y por ello un subconjunto A de S consistente en estados de aceptación.
En la tabla de estados de un NFA. se dará una lista de posibles estados siguientes correspondientes a cada par de estado y valores de entrada. En el diagrama de estados de un NFA, una arista desde cada estado hasta todos los posibles estados siguientes se incluirá con ia entrada o entradas que conduzcan a esta transición marcada encima de las aristas.
- Un tipo de FSM que se llama autómatas de estado finito (FSA) es de interés especial ya que puede reconocer cadenas de un lenguaje.
Un autómata de estados finitos, denota como M = {S, I, F, s0, A} es un modelo abstracto de una maquina que consiste en un conjunto finito S de estados.