DFA para exactamente uno de a y al menos uno de b

Los autómatas finitos deterministas (DFA) se definen como un concepto matemático abstracto que se utiliza para resolver varios problemas específicos en diferentes software y hardware. En este tipo de problemas tenemos algunos parámetros dados según los cuales debemos diseñar DFA. 

En este artículo, se dan dos instrucciones: 

• DFA debe tener uno de 
   
• DFA debe tener al menos una b 
   

Este DFA debería aceptar strings como ab, ba, abb, bab, bba, abbb, babb, bbab, bbba, abbbb…. etc. pero no debería aceptar strings como a, b, bb, bbb, aabb, ababa… etc. 

Diseño paso a paso: 

Paso 1: 
tome un estado inicial A, y la string más pequeña posible es ab y ba, si A toma ‘a’ como primer alfabeto de entrada, pasa al estado B y si A toma ‘b’ como primer alfabeto de entrada, pasa al estado C . 

Paso 2: 
ahora piense en el estado B, si toma el alfabeto de entrada ‘a’, rompe nuestra condición de solo una ‘a’, pero si toma el alfabeto de entrada ‘b’, crea una string aceptable y ahora pasa al estado D, que se establece en el estado final. 

Paso 3: 
en el estado C, si puede tomar cualquier número de ‘b’ que sea posible y también puede tomar ‘a’ como alfabeto de entrada. En el alfabeto ‘b’ permanece en el mismo estado pero en la entrada ‘a’ va al estado E que se establecerá en el estado final. 

Paso 4: 
el alfabeto de entrada ‘a’ del estado B rompe la condición, por lo que pasa a algún estado muerto (Q). 

Paso 5: 
Hasta ahora, nuestra máquina acepta strings que terminan en ‘a’ y ‘ab’. Pero, ¿qué pasa si ‘a’ viene en el medio, como bab, babb, bbab, etc. y si hay muchas ‘b’? al final. Para hacer eso, dé el bucle automático de ‘b’ al estado final y envíe su ‘a’ al estado muerto. 

Nota: 
los alfabetos de entrada de estado inactivo van a estado inactivo solo por eso no se muestran en los diagramas. 

Tabla de Transición y Reglas de Transición del diagrama anterior. 
 

finite set of states = {A, B, C, D, E, Q} 

En la tabla de transición, el estado inicial está representado por → y el estado final son E y D. 
 

set of input alphabets = {a, b} 

ESTADO	ENTRADA (a)	ENTRADA (b)
→A	B	C
B	Q (estado muerto)	D
C	mi	C
D	Q (estado muerto)	D
mi	Q (estado muerto)	mi