Investigación acerca de las diferencias de autómatas determinados y y autómatas no determinados

 

Definición de autómata finito determinista

Un autómata finito determinista consta de:

1. Un conjunto finito de estados, a menudo designado como Q.

2. Un conjunto finito de símbolos de entrada, a menudo designado como Σ.

3. Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve un estado. La función de transición se designa habitualmente como δ. En nuestra representación gráfica informal del autómata, δ se ha representa mediante arcos entre los estados y las etiquetas sobre los arcos. Si q es un estado y a es un símbolo de entrada, entonces δ(q,a) es el estado p tal que existe un arco etiquetado a que va desde q hasta p.

4. Un estado inicial, uno de los estados de Q.

5. Un conjunto de estados finales o de aceptación F. El conjunto F es un subconjunto de Q.

 

Un autómata finito “no determinista” (AFN) tiene la capacidad de estar en varios estados a la vez. Esta capacidad

a menudo se expresa como la posibilidad de que el autómata “conjeture” algo acerca de su entrada. Por ejemplo, cuando el autómata se utiliza para buscar determinadas secuencias de caracteres (por ejemplo, palabras clave) dentro de una cadena de texto larga, resulta útil “conjeturar” que estamos al principio de una de estas cadenas y utilizar una secuencia de estados únicamente para comprobar la aparición de la cadena, carácter por carácter. Veremos un ejemplo de este tipo de aplicación en la Sección 2.4.

Antes de examinar las aplicaciones, necesitamos definir los autómatas finitos no deterministas y demostrar que aceptan un lenguaje que también es aceptado por algunos AFD. Es decir, los AFN aceptan los lenguajes regulares, al igual que los AFD. Sin embargo, existen razones para estudiar los AFN: a menudo son más compactos y fáciles de diseñar que los AFD. Además, siempre es posible convertir un AFN en un AFD, este último puede tener un número exponencialmente mayor de estados que el AFN; afortunadamente, son pocos los casos de este tipo.