Un autómata finito determinista (DFA) es un modelo de máquina de estados capaz de aceptar todos los lenguajes regulares. Los DFA se pueden definir (y generalmente se definen) de tal manera que cada estado debe proporcionar alguna transición para todos los elementos del alfabeto de entrada; en otras palabras, la función de transición debería ser una función (total).
Imagine lo que llamaremos un autómata finito doblemente determinista (DDFA). Se define de manera similar a un DFA, con dos excepciones: primero, en lugar de la transición que conduce de un estado a otro para cada símbolo de entrada posible, debe conducir a dos estados distintos; segundo, para aceptar una cadena, todas las rutas potenciales deben cumplir una u otra de las siguientes condiciones:
- Todas las rutas potenciales a través del DDFA conducen a un estado de aceptación (lo llamaremos DDFA de tipo 1).
- Todas las rutas potenciales a través del DDFA conducen al mismo estado de aceptación (lo llamaremos DDFA de tipo 2).
Ahora para mi pregunta:
Las pruebas (o al menos bocetos moderadamente desarrollados) son apreciadas, si no son demasiado complicadas.
fuente