Diseño de autómatas finitos deterministas (Conjunto 11)

Requisito previo: diseño de autómatas finitos
En este artículo, veremos un diseño de autómatas finitos deterministas (DFA).

Problema: construcción de un DFA mínimo que acepta un conjunto de strings sobre {a, b} en el que Número de a(w) mod 2 = 0 o Número de b(w) mod 2 = 0, es decir, el número de ‘a’ debe ser divisible por 2 o el número de ‘b’ debe ser divisible por 2 o ambos son divisibles por 2, donde ‘w’ es cualquier string sobre {a, b}.

Explicación: El idioma deseado será como:

L1 = {ε, aa, aabb, aab, bb, bba, ...........}

Aquí, como podemos ver, cada string del lenguaje anterior satisface la condición del problema dado, es decir, aquí se acepta ε porque el número de ‘a’ y ‘b’ es cero y el resto de las strings tienen ‘a’. divisible por 2 o ‘b’ divisible por 2 o ambos son divisibles por 2.

Pero el siguiente lenguaje no es aceptado por este DFA porque sus strings no satisfacen la condición del problema dado.

L2 = {ba, bbba, baaa, ..............}

Aquí, como podemos ver, ninguna de las strings del lenguaje anterior satisface la condición del problema dado, es decir, ‘a’ o ‘b’ o cualquiera de las strings anteriores no son divisibles por 2.

El diagrama de transición de estado del idioma deseado será el siguiente:

En el DFA anterior, en cada estado hay un nombre de estado como ‘A’ y justo debajo hay (ee) que indica que el número de ‘a’ es par (e) y el número de ‘b’ es par (e) también. Para el nombre del estado como ‘B’ y justo debajo de él hay (eo) que indica que el número de ‘a’ es par (e) y el número de ‘b’ es impar (o) y así sucesivamente.

• El estado inicial y final ‘A’ al obtener ‘a’ como entrada transita a un estado final ‘D’ y al obtener ‘b’ como entrada transita a otro estado final ‘B’.
• El estado final ‘B’ al obtener ‘a’ como entrada, transita a un estado ‘C’ y al obtener ‘b’ como entrada regresa al estado inicial ‘A’.
• El otro estado final ‘D’ al obtener ‘b’ como entrada, transita a un estado ‘C’ y al obtener ‘a’ como entrada, regresa al estado inicial ‘A’.
• El estado ‘C’ al obtener ‘b’ como entrada, transita al estado final ‘D’ y al obtener ‘a’ como entrada, regresa al estado ‘B’.

Implementación de Python:

def stateA(n):
    #if length of n become 0 
    #then print accepted
    if(len(n)==0):
        print("string accepted")
          
    else: 
        #if at zero index 
        #'a' found call
        #stateD function    
        if (n[0]=='a'):
            stateD(n[1:])
          
        #if at zero index 
        #'b' found call
        #stateB function    
        elif (n[0]=='b'):
            stateB(n[1:])    
         
def stateB(n):
    #if length of n become 0 
    #then print accepted
    if(len(n)==0):
        print("string accepted")
          
    else:  
        #if at zero index 
        #'a' found call
        #stateC function    
        if (n[0]=='a'):
            stateC(n[1:])
              
        #if at zero index 
        #'b' found call
        #stateA function    
        elif (n[0]=='b'):
            stateA(n[1:])    
          
def stateC(n):
    #if length of n become 0 
    #then print not accepted
    if(len(n)==0):
        print("string not accepted")
          
    else:
        #if at zero index 
        #'a' found call
        #stateB function    
        if (n[0]=='a'):
            stateB(n[1:])
              
        #if at zero index 
        #'b' found call
        #stateD function    
        elif (n[0]=='b'):
            stateD(n[1:])    
          
def stateD(n):
    #if length of n become 0 
    #then print accepted
    if(len(n)==0):
        print("string accepted")
          
    else: 
        #if at zero index 
        #'a' found call
        #stateA function    
        if (n[0]=='a'):
            stateA(n[1:])
              
        #if at zero index 
        #'b' found call
        #stateC function    
        elif (n[0]=='b'):
            stateC(n[1:])    
  
              
              
#take input
n=input()
  
#call stateA function
#to check the input
stateA(n)