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

Prerrequisito: Diseño de autómatas finitos , Diseño de autómatas finitos deterministas (Conjunto 3)
En este artículo, veremos algunos diseños de Autómatas finitos deterministas (DFA).

Problema 1: construcción de un conjunto mínimo de strings de caracteres que acepta DFA sobre {a, b} en el que cada ‘a’ va seguida de una ‘b’.
Explicación: El idioma deseado será como:

L1 = {ε, ab, abab, abbbb, ababababab, ..............}

Aquí, como podemos ver, cada string del idioma que contiene ‘a’ simplemente seguida de ‘b’, pero este DFA no acepta el siguiente idioma porque parte de la string del siguiente idioma no contiene ‘a’ seguido de ‘ b’.

L2 = {ba, baab, bbaba, ..............}

El diagrama de transición de estado del idioma que contiene ‘a’ seguido de ‘b’ será como:

En el DFA anterior, el estado ‘W’ es también el estado inicial y final que al obtener ‘b’ como entrada permanece en el estado de sí mismo y al obtener ‘a’ como entrada, transita a un estado normal ‘X’ que al obtener ‘b’ como entrada, transita al estado final ‘W’. El estado ‘X’ al obtener ‘a’ como entrada transita al estado muerto ‘Z’. El estado ‘Z’ se llama estado muerto porque al recibir cualquier entrada no puede transitar nunca al estado final.

def stateW(n):
    if(len(n)==0):
        print("Accepted")
    else:  
          
        #if 'a' found 
        #call function stateX
        if (n[0]=='a' ):
            stateX(n[1:])
        #if 'b' found 
        #call function stateW    
        elif (n[0]=='b' ):
            stateW(n[1:])    
          
def stateX(n):
    if(len(n)==0):
        print("Not Accepted")
    else:  
          
        #if 'a' found 
        #call function stateZ
        if (n[0]=='a' ):
            stateZ(n[1:])
          
        #if 'b' found 
        #call function stateW     
        elif (n[0]=='b' ):
            stateW(n[1:]) 
              
def stateZ(n):
    if(len(n)==0):
        print("Not Accepted")
    else:
          
         #if a or b found 
         #call stateZ
        if (n[0]=='a' or n[0]=='b'):
            stateZ(n[1:])              
  
  
  
#take input
n=input()
  
#call stateA
#to check the input
stateA(n)

Problema 2: construcción de un conjunto mínimo de strings que acepta DFA sobre {a, b} en el que cada ‘a’ nunca va seguido de ‘b’
Explicación: el idioma deseado será como:

L1 = {ε, a, aa, aaaa, b, bba, bbbbba..............}

Aquí, como podemos ver, cada string del idioma que contiene ‘a’ nunca va seguida de ‘b’, pero este DFA no acepta el siguiente idioma porque parte de la string del siguiente idioma que contiene ‘a’ va seguida de ‘ b’.

L2 = {ba, baab, bbaba, ..............}

El diagrama de transición de estado del lenguaje que contiene ‘a’ nunca será seguido por ‘b’ será como:

En el DFA anterior, el estado ‘X’ es el estado inicial y final que al obtener ‘b’ como entrada permanece en el estado de sí mismo y al obtener ‘a’ como entrada transita al estado final ‘Y’ que al obtener ‘a’ como entrada permanece en el estado de sí mismo y al obtener ‘b’ como entrada transita al estado muerto ‘ Z’. El estado ‘Z’ se llama estado muerto porque no puede pasar nunca a ninguno de los estados finales.

def stateX(n):
    if(len(n)==0):
        print("Accepted")
    else:  
          
        #if 'a' found 
        #call function stateY
        if (n[0]=='a' ):
            stateY(n[1:])
        #if 'b' found 
        #call function stateX   
        elif (n[0]=='b' ):
            stateX(n[1:])    
          
def stateY(n):
    if(len(n)==0):
        print("Accepted")
    else:  
          
        #if 'a' found 
        #call function stateZ
        if (n[0]=='a' ):
            stateZ(n[1:])
          
        #if 'b' found 
        #call function stateY   
        elif (n[0]=='b' ):
            stateY(n[1:]) 
              
def stateZ(n):
    if(len(n)==0):
        print("Not Accepted")
    else:
          
         #if a or b found 
         #call stateZ
        if (n[0]=='a' or n[0]=='b'):
            stateZ(n[1:])              
  
  
  
#take input
n=input()
  
#call stateA
#to check the input
stateA(n)