Construya un DFA que comience con aa o bb

Prerrequisito: Diseño de Autómatas Finitos

DFA (Deterministic Finite Automata or Acceptor) es una máquina de estados finitos que acepta o rechaza strings de símbolos. DFA acepta la string si alcanza el estado final; de lo contrario, la rechaza. En este tipo de problemas, tenemos algunos parámetros dados según los cuales debemos diseñar DFA.

Problema : construya un DFA que comience con aa o con bb a partir de la entrada (a,b).

Solución : en este problema, se dan dos parámetros:

• DFA debe comenzar con aa

                           o  

• DFA debe comenzar con bb

Esto significa que el DFA resultante debe aceptar strings como aa, bb, aab, bba, aaa, bbb…. etc. pero no debería aceptar strings como a, b, ba, bab, abb, abbaba… etc.

Diseño de DFA paso a paso:

Paso 1: tome el estado inicial qo , y la string más pequeña posible es aa y bb si qo toma ‘a’ como el primer alfabeto de entrada, pasa al estado q1 y si qo toma ‘b’ como el primer alfabeto de entrada, pasa al estado q3 .

Paso 2: ahora piense en el estado q1 , si toma el alfabeto de entrada ‘b’, rompe nuestra condición de ‘aa’, pero si toma el alfabeto de entrada ‘a’, crea una string aceptable, y ahora pasa al estado q2 , que es establecido en el estado final.

Paso 3: en el estado q3 , si toma el alfabeto de entrada ‘a’, rompe nuestra condición de ‘bb’, pero si toma el alfabeto de entrada ‘b’, crea una string aceptable, y ahora pasa al estado q2 , que se establece en estado final

Paso 4: si el alfabeto de entrada ‘a’ del estado q3 rompe la condición y el alfabeto de entrada ‘b’ del estado q1 rompe la condición, entonces van a algún estado muerto ( D ).

Paso 5: Hasta ahora, nuestra máquina acepta strings que comienzan con ‘aa’ o ‘bb’, pero también tenemos que ocuparnos de todos los símbolos después de que la string haya comenzado con ‘aa’ o ‘bb’ y, por lo tanto, introducimos nosotros mismos hacemos bucles en q2 (estado final) y D (estado muerto).

Tabla de transición y reglas de transición para el diagrama anterior:

El conjunto finito de estados = { qo, q1, q2, q3, D }  

En la tabla de transición, el estado inicial (qo) está representado por → y el estado final es q2 y tiene dos círculos.

Conjunto de alfabetos de entrada = {a, b}  

Tabla de transición

ESTADO	a	b
->qo	q1	q3
q1	q2	D (muerto)
q3	D (muerto)	q2
q2	q2	q2
D (muerto)	D (muerto)	D (muerto)