Finite Automata (FA) es la máquina más sencilla para reconocer patrones. Se utiliza para caracterizar un lenguaje regular, por ejemplo: /baa+!/.
También se utiliza para analizar y reconocer expresiones del lenguaje natural. El autómata finito o máquina de estados finitos es una máquina abstracta que tiene cinco elementos o tuplas. Tiene un conjunto de estados y reglas para pasar de un estado a otro, pero depende del símbolo de entrada aplicado. Según los estados y el conjunto de reglas, la cadena de entrada puede aceptarse o rechazarse. Básicamente, es un modelo abstracto de una computadora digital que lee una cadena de entrada y cambia su estado interno dependiendo del símbolo de entrada actual. Cada autómata define un lenguaje, es decir, un conjunto de cadenas que acepta. La siguiente figura muestra algunas características esenciales de la automatización general.

Cifra: Características de los autómatas finitos

La figura anterior muestra las siguientes características de los autómatas:

1. Aporte
2. Producción
3. Estados de autómatas
4. relación estatal
5. Relación de salida

Un autómata finito consta de lo siguiente:

Q : Finite set of states. ? : set of Input Symbols. q : Initial state. F : set of Final States. ? : Transition Function.>

La especificación formal de la máquina es

{ Q, ?, q, F, ? }>

La FA se caracteriza en dos tipos:

1) Autómatas finitos deterministas (DFA):

DFA consists of 5 tuples {Q, ?, q, F, ?}. Q : set of all states. ? : set of input symbols. ( Symbols which machine takes as input ) q : Initial state. ( Starting state of a machine ) F : set of final state. ? : Transition Function, defined as ? : Q X ? -->P.>

En un DFA, para un carácter de entrada particular, la máquina pasa a un solo estado. Se define una función de transición en cada estado para cada símbolo de entrada. Además, en DFA no se permite el movimiento nulo (¿o?), es decir, DFA no puede cambiar de estado sin ningún carácter de entrada.

Por ejemplo, cree un DFA que acepte un lenguaje de todas las cadenas que terminen en 'a'.
Dado: ? = {a,b}, q = {q₀}, F={q₁}, Q = {q₀, q₁}

Primero, considere un conjunto de lenguaje de todas las posibles cadenas aceptables para construir un diagrama de transición de estado preciso.
L = {a, aa, aaa, aaaa, aaaaa, ba, bba, bbba, padre, padre, padre, padre}
Arriba hay un subconjunto simple de las posibles cadenas aceptables; pueden haber muchas otras cadenas que terminan en 'a' y contienen símbolos {a,b}.

Fig 1. Diagrama de transición de estado para DFA con ? = {a,b}

Las cadenas no aceptadas son,
ab, bb, aab, abbb, etc.

Tabla de transición de estado para el autómata anterior,

subcadena de cadena java

Una cosa importante a tener en cuenta es, Puede haber muchos DFA posibles para un patrón. . Generalmente se prefiere un DFA con un número mínimo de estados.

2) Autómatas finitos no deterministas (NFA): NFA es similar a DFA excepto por las siguientes características adicionales:

1. Se permite el movimiento nulo (¿o?), es decir, puede avanzar sin leer símbolos.
2. Capacidad de transmitir a cualquier número de estados para una entrada particular.

Sin embargo, estas características anteriores no añaden ningún poder a NFA. Si comparamos ambos en términos de potencia, ambos son equivalentes.

Debido a las características adicionales anteriores, NFA tiene una función de transición diferente, el resto es igual que DFA.

?: Transition Function ?: Q X (? U ? ) -->2 ^ P.>

Como puede ver en la función de transición, para cualquier entrada, incluido nulo (¿o?), NFA puede ir a cualquier número de estados. Por ejemplo, a continuación se muestra una NFA para el problema anterior.

Fig 2. Diagrama de transición de estado para NFA con ? = {a,b}

Tabla de transición de estado para el autómata anterior,

Una cosa importante a tener en cuenta es, En NFA, si alguna ruta para una cadena de entrada conduce a un estado final, entonces la cadena de entrada es aceptado . Por ejemplo, en la NFA anterior, hay varias rutas para la cadena de entrada 00. Dado que una de las rutas conduce a un estado final, la NFA anterior acepta 00.

Algunos puntos importantes:

colecciones en java

Justificación:

In case of DFA ? : Q X ? -->P ¿En caso de NFA? :QX? --> 2Q>

Ahora bien, si observas, descubrirás Q X ? –> Q es parte de Q X ? –> 2^q.

En el lado derecho, Q es el subconjunto de 2^qlo que indica que Q está contenido en 2^qo Q es parte de 2^q, sin embargo, lo contrario no es cierto. Entonces matemáticamente podemos concluir que cada DFA es NFA pero no al revés . Sin embargo, existe una forma de convertir un NFA en DFA, por lo que existe un DFA equivalente para cada NFA .

1. Tanto NFA como DFA tienen el mismo poder y cada NFA se puede traducir en un DFA.
2. Puede haber varios estados finales tanto en DFA como en NFA.
3. La NFA es más un concepto teórico.
4. DFA se utiliza en el análisis léxico del compilador.
5. Si el número de estados en la NFA es N, entonces su DFA puede tener un máximo de 2^nortenúmero de estados.

Consulte el cuestionario sobre expresiones regulares y autómatas finitos.