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

Prerrequisito: Introducción a los autómatas finitos 
En este artículo, veremos algunos diseños de autómatas finitos no deterministas (NFA).
Problema-1: Construcción de un NFA mínimo que acepta un conjunto de strings sobre {a, b} en el que cada string del lenguaje comienza con ‘ab’. 
Explicación: El idioma deseado será como: 
 

L1 = {ab, abba, abaa, ...........}

Aquí, como podemos ver, cada string del idioma anterior comienza con ‘ab’ y termina con cualquier alfabeto, ya sea ‘a’ o ‘b’. 
Pero el lenguaje a continuación no es aceptado por esta NFA porque ninguna de las strings del lenguaje a continuación comienza con ‘ab’. 
 

L2 = {ba, ba, babaaa..............}

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

En el NFA anterior, el estado inicial ‘X’ al obtener ‘a’ como entrada, transita a un estado ‘Y’. El estado ‘Y’ al obtener ‘b’ como entrada, transita a un estado final ‘Z’. El estado final ‘Z’ al obtener ‘a’ o ‘b’ como entrada, permanece en el estado de sí mismo. 
 

Implementación de Python:

def stateX(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
        #stateY function   
        if (n[0]=='a'):
            stateY(n[1:])
         
        #if at zero index
        #'b' then print
        #not accepted
        elif (n[0]=='b'):
            print("string not accepted")  
        
def stateY(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' then print
        #not accepted  
        if (n[0]=='a'):
            print("string not accepted")
             
        #if at zero index
        #'b' found call
        #stateZ function   
        elif (n[0]=='b'):
            stateZ(n[1:])
             
def stateZ(n):
    #if length of n become 0
    #then print accepted
    if(len(n)==0):
        print("string accepted")
         
    else: 
        #if at zero index
        #'b' found call
        #stateZ function   
        if (n[0]=='a'):
            stateZ(n[1:])
             
        #if at zero index
        #'b' found call
        #stateZ function   
        elif (n[0]=='b'):
            stateZ(n[1:])            
         
 
             
             
#take input
n=input()
 
#call stateA function
#to check the input
stateX(n)

Problema 2: construcción de un NFA mínimo que acepta un conjunto de strings sobre {a, b} en el que cada string del idioma no comienza con ‘ab’. 
Explicación: El idioma deseado será como: 
 

L1 = {ba, bba, bbaa, ...........}

Aquí, como podemos ver, cada string del lenguaje anterior no comienza con ‘ab’ sino que puede terminar con ‘a’ o ‘b’. 
Pero el lenguaje a continuación no es aceptado por esta NFA porque parte de la string del lenguaje a continuación comienza con ‘ab’. 
 

L2 = {ab, aba, ababaab..............}

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

En el NFA anterior, el estado inicial ‘X’ al obtener ‘b’ como entrada, transita a un estado ‘Y’. El estado ‘Y’ al obtener ‘a’ o ‘b’ como entrada, transita a un estado final ‘Z’. El estado final ‘Z’ al obtener ‘a’ o ‘b’ como entrada, permanece en el estado de sí mismo. 
 

Implementación de Python:

def stateX(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 then
        #print not accepted   
        if (n[0]=='a'):
            print("string not accepted")  
         
        #if at zero index
        #'b' then call
        #stateY function
        elif (n[0]=='b'):
            stateY(n[1:])
        
def stateY(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
        #stateZ function  
        if (n[0]=='a'):
            stateZ(n[1:])
             
        #if at zero index
        #'b' found call
        #stateZ function
        elif (n[0]=='b'):
            stateZ(n[1:])
             
def stateZ(n):
    #if length of n become 0
    #then print accepted
    if(len(n)==0):
        print("string accepted")
         
    else: 
        #if at zero index
        #'b' found call
        #stateZ function   
        if (n[0]=='a'):
            stateZ(n[1:])
             
        #if at zero index
        #'b' found call
        #stateZ function   
        elif (n[0]=='b'):
            stateZ(n[1:])            
         
 
             
             
#take input
n=input()
 
#call stateA function
#to check the input
stateX(n)