Si no es así, ¿qué significa cuando para algún estado y algún símbolo , no existe?
terminology
automata
finite-automata
Duncan
fuente
fuente
Respuestas:
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 deterministaM es una tupla de 5, ( Q , Σ , δ , q0 , F ), que consiste en
Seaw=a1a2⋯an 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:
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.
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):
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):
(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):
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):
Libros de la comunidad de teoría de conmutación:
Kohavi, Switching and Finite Automata Theory, 2 / e , 1978, p. 611 dice:
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):
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:
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):
Mientras Hopcroft y Ullman dicen (p. 112):
fuente
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.
fuente
Hay definiciones de DFA en la línea de
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.
fuente
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.
fuente
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.
fuente