En un DFA, ¿cada estado tiene una transición en cada símbolo del alfabeto?

12

Si no es así, ¿qué significa cuando para algún estado q y algún símbolo a , δ(q,a) no existe?

Duncan
fuente
Llamaría a un autómata no determinista que nunca tiene más de una transición en el mismo estado y determinista de símbolo de entrada. Simplemente no se ajusta a la definición de DFA.
reinierpost
1
Si las reglas de un DFA están dispuestas de modo que nunca puedan estar en el estado q cuando el símbolo en la cinta es a , ¿realmente necesitamos definir δ (q, a) ?
Peter Shor
44
La respuesta es claramente que depende de cómo se defina el "autómata finito determinista". Como tal, no estoy seguro de que esta pregunta sea totalmente constructiva, ya que no hay una respuesta correcta universalmente aceptada, es decir, esta pregunta requiere opinión y debate.
Patrick87
1
Si se supone que δ es una función , debe definirse para todos los pares q,a .
vonbrand
En mi noción de un DFA, esta es una condición de "aborto", o si prefiere un salto implícito a un estado de "rechazo".
Yves Daoust

Respuestas:

22

Parece que te has topado con un tema polémico. Al parecer, a los informáticos les gusta discutir. Ciertamente me gusta discutir, ¡así que aquí va!

Mi respuesta es inequívoca: No. Un autómata finito determinista no necesita una transición de cada estado para cada símbolo. El significado cuando δ(q,a) no existe es simplemente que el DFA no acepta la cadena de entrada.

Si bien puede crear una definición de DFA que requiera que δ(q,a) exista, simplemente no es el caso de que una transición faltante haga que la estructura resultante (como se llame) no sea determinista, ya que muchos de los comentaristas son reclamando. Si está tomando un curso sobre teoría de autómatas, el siguiente tema será lenguajes libres de contexto y autómatas pushdown donde la distinción entre autómatas deterministas y no deterministas es crítica, y debe utilizar la definición correcta de no determinismo.

El no determinismo se asocia con tener más de una transición legal.

Creo que todos estamos de acuerdo con la siguiente definición de Wikipedia (que mostraré en un segundo es un poco ambigua):

Un autómata finito determinista M es una tupla de 5, ( Q , Σ , δ , q0 , F ), que consiste en

  1. un conjunto finito de estados ( Q )
  2. un conjunto finito de símbolos de entrada llamado alfabeto ( Σ )
  3. una función de transición ( δ:Q×ΣQ )
  4. un estado de inicio ( q0Q)
  5. un conjunto de estados de aceptación ( FQ ).

Sea w=a1a2an una cadena sobre el alfabeto Σ . El autómata M acepta la cadena w si existe una secuencia de estados, r0,r1,,rn , en Q con las siguientes condiciones:

  1. r0=q0
  2. ri+1=δ(ri,ai+1) , parai=0,,n1
  3. rnF .

La ambigüedad, y la controversia es sobre la definición de la función de transición, δ (número "3" en la primera lista con viñetas.) Todos estamos de acuerdo en que lo que diferencia un DFA de un NFA es que δ es una función más que una relación . ¿Pero es δ una función parcial o una función total ?

La definición de DFA funciona bien si δ es una función parcial. Dada una cadena de entrada, si alcanza un estado qi con un símbolo de entrada aj donde no hay un estado siguiente, el autómata simplemente no acepta.

Además, cuando amplíe esta definición para crear la definición de autómatas push-down, deberá distinguir que los autómatas push-down con funciones de transición que son funciones parciales se clasifican como deterministas, no no deterministas.

δ

  1. qerror
  2. (qi,sj)δδ(qi,sj)=qerror

δ

Editar, enero de 2019

El comentarista @Alex Smart me critica con razón por no dar referencias ni por explicar por qué debería importarnos. Entonces aquí va:

La razón por la que nos importa la definición exacta de determinismo versus no determinismo es que algunas clases de autómatas no deterministas son más poderosas que sus primos deterministas, y algunas clases de autómatas no deterministas no son más poderosas que sus primos deterministas. Para autómatas finitos y máquinas de Turing, las variantes deterministas y no deterministas son de potencia equivalente. Para los autómatas pushdown hay idiomas en los que la distinción es importante: hay NPDA que aceptan el idioma y ningún DPDA acepta el idioma. Para los autómatas acotados lineales, la pregunta está abierta (o la última vez que la revisé). El aumento del poder de NPDA sobre DPDA proviene de permitir múltiples transiciones, no de convertir la función de transición de una función total a una función parcial.

Libros de la comunidad del compilador:

Aho y Ullman, Principios del diseño del compilador , 1977: Primero define NFA (página 88) con una relación de transición, luego (p. 90-91):

ϵsaas

Aho, Sethi y Ullman, Compiladores, principios, técnicas y herramientas , la reimpresión de 1988, es similar, primero define NFA con una relación de transición, luego (p. 115-116):

as

(Tenga en cuenta que en los comentarios @Alex Smart dice: "el dragón menciona específicamente que la función es total". Supongo que está hablando de la edición posterior con el coautor Lam, a la que no tengo acceso en este momento. )

Appel, Implementación del compilador moderno en Java , 1988 (p. 22):

En un determinista autómata finito (DFA), no hay dos bordes que salen desde el mismo estado están etiquetados con el mismo símbolo.

Luego, Appel continúa explicando que cuando usamos DFA para reconocer las coincidencias más largas, explícitamente hacemos uso de las transiciones que faltan para decidir cuándo parar (p. 23):

cuando un muerto se alcanza el estado (un estado no final sin transiciones de salida), las variables [que registran el partido más largo que hemos visto hasta ahora] decirle que token fue igualada, y donde se acabó.

Libros de la comunidad de teoría de conmutación:

Kohavi, Switching and Finite Automata Theory, 2 / e , 1978, p. 611 dice:

Debido a que un diagrama de estado describe una máquina determinista , la siguiente transición de estado debe determinarse únicamente por el estado actual y el símbolo de entrada escaneado actualmente.

Normalmente interpretaría de manera única que significa "exactamente uno", no "no más de uno". (Es decir, Kohavi parece estar diciendo que el determinismo requiere una función total)

Libros de la comunidad de teoría de la computación:

Aquí parece ser más común definir DFA antes que NFA, y requerir que los DFA tengan una función de transición total, pero luego definir NPDA antes de DPDA, y definir "determinismo" como una restricción de la relación de transición para no tener más de -una entrada para cada par estado / símbolo.

Esto es cierto para Hopcroft y Ullman, 1979, Lewis y Papadimitriou, 1981, y, especialmente para Sipser, 2006, que utiliza la definición de DFA pedagógicamente para introducir definiciones formales precisas y explicar su importancia y dice explícitamente (p.36):

δ

s×Σ

Curiosamente, Rabin y Scott, también definen autómatas finitos no deterministas en términos de una función total. Página 120, Definición 9:

MS×ΣS

Es decir: ¡la función de transición siendo total no hace que el sistema sea determinista!

Sipser 2006 sigue a Rabin y Scott y usa una función de transición total de estados / símbolos al conjunto de estados de poder para sus definiciones de autómatas finitos no deterministas, PDA no deterministas y máquinas de Turing no deterministas, pero omite el tema de las máquinas deterministas deterministas. PDA

Tanto Hopcroft como Ullman, 1979, y Lewis y Papadimitriou, 1981 utilizan funciones parciales en sus definiciones de PDA deterministas. Primero definen los NPDA con una relación de transición, y luego, cuando llegan a los PDA, Lewis y Papadimitriou dicen (p. 135):

Un autómata pushdown es determinista , intuitivamente hablando, si hay como máximo una transición aplicable a cada configuración.

Mientras Hopcroft y Ullman dicen (p. 112):

El PDA ... es determinista en el sentido de que, como máximo, un movimiento es posible desde cualquier ID.

Lógica Errante
fuente
qerror
2
La versión de función parcial es la que se proporciona en Hopcroft y Ullman, si eso marca la diferencia. Por lo tanto, la idea de que una función parcial es inherentemente no determinista no es en modo alguno estándar.
jmite
1
@jmite No es que las funciones parciales impliquen no determinismo; Es que las funciones totales implican determinismo lo que hace que las funciones totales sean la mejor opción. Por supuesto, es una cuestión más o menos arbitraria de las definiciones que está utilizando.
Patrick87
3
δ
1
Como ha demostrado, la versión de función parcial tiene una traducción fácil a la versión de función total, y hasta donde puedo ver, no gana absolutamente nada, pedagógicamente o de otro modo, al permitir que la función de traducción sea parcial. El dragón menciona específicamente que la función es total. ¿Por qué en el mundo estamos creando una discusión sobre algo que se ha definido claramente en un libro de texto estándar que la mayoría de la gente sigue cuando no hay absolutamente nada que ganar al elegir una definición no estándar?
Alex Smart
8

δ(q,a)qQaΣQΣ

ε

En términos de computabilidad, los NFA son equivalentes a los DFA: hay un algoritmo para convertir de un NFA a un DFA, y un DFA es trivialmente un NFA que no utiliza ningún no determinismo, por lo que ambos definen el conjunto de lenguajes regulares.

Luke Mathieson
fuente
2
Esto depende de la definición; Hay varios que son equivalentes en potencia.
Raphael
3
+1 Lo mejor es apegarse a esta definición, en mi humilde opinión, ya que todos estarían de acuerdo en que un FA que define exactamente una transición para cada par (estado, símbolo) constituye un DFA válido.
Patrick87
1
Y esta definición es completamente incorrecta cuando intenta extenderla para decidir si un lenguaje libre de contexto es determinista o no determinista. Un autómata pushdown con transiciones faltantes siempre se puede transformar en un autómata pushdown con exactamente una transición por estado / símbolo de entrada / símbolo de pila. Un autómata pushdown no determinista con múltiples transiciones posibles por estado / símbolo de entrada / símbolo de pila no se puede transformar necesariamente en un autómata pushdown determinista. (Por ejemplo: en el caso de que el idioma reconocido sea libre de contexto no determinista.)
Wandering Logic
2
@jmite Simplemente defina los autómatas de recorte independientemente de los DFA. Creo que es mucho más importante que los DFA mínimos tengan el número correcto de estados según el teorema de Myhill-Nerode, que solo se obtiene con estados muertos.
Patrick87
44
ϵϵϵ
6

Hay definiciones de DFA en la línea de

A|δ(q,a)|1qaδ(q,ε)δ(q,a)=aΣA

En ese caso, no necesita todas las transiciones. Si el autómata no tiene una transición que se ajuste al siguiente símbolo de entrada, lo rechaza.

Es un buen ejercicio demostrar que ambas definiciones son equivalentes en términos de qué idiomas se pueden aceptar.

Rafael
fuente
Creo que la pregunta del OP debe editarse para incluir la definición formal de DFA.
scaaahu
0

En la definición de DFA, todos los estados deben tener todo el alfabeto en £. Por ejemplo, si £ = {a, b, c} y Q = {q0, q1, q2}, todos estos estados deben tener todos los símbolos a, b, c que hacen la transición a otro estado o al mismo estado.

Hasee Amarathunga
fuente
1
¿Cuál es la diferencia con las respuestas existentes para publicar una nueva respuesta?
xskxzr
0

La respuesta más simple para esto es, agrega estado muerto para el símbolo izquierdo . Al igual que en la conversión de NFA a DFA, obtenemos Φ transión para algunos símbolos, lo que significa que creamos un estado Muerto para él.

niks
fuente