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 ‘a’.
Explicación: El idioma deseado será como:
L1 = {ab, abba, abaa, ...........}
Aquí, como podemos ver, cada string del idioma anterior comienza con ‘a’ 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 ‘a’.
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 final ‘Y’. El estado final ‘Y’ 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 accepted
if(len(n)==0):
print("string accepted")
else:
#if at zero index
#'a' found call
#stateY function
if (n[0]=='a'):
stateY(n[1:])
#if at zero index
#'b' found call
#stateY function
elif (n[0]=='b'):
stateY(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 ‘a’.
Explicación: El idioma deseado será como:
L1 = {ba, bba, bbaa, ...........}
Aquí, como podemos ver, cada string del lenguaje anterior no comienza con ‘a’ 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 ‘a’.
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 final ‘Y’. El estado final ‘Y’ 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
#'b' found call
#stateY function
if (n[0]=='b'):
stateY(n[1:])
#if at zero index
#'a' then print
#not accepted
elif (n[0]=='a'):
print("string not accepted")
def stateY(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
#stateY function
if (n[0]=='a'):
stateY(n[1:])
#if at zero index
#'b' found call
#stateY function
elif (n[0]=='b'):
stateY(n[1:])
#take input
n=input()
#call stateA function
#to check the input
stateX(n)
Publicación traducida automáticamente
Artículo escrito por Kanchan_Ray y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA