Requisito previo: diseño de autómatas finitos
En este artículo, veremos algunos diseños de autómatas finitos deterministas (DFA).
Problema-1: Construcción de un DFA mínimo que acepta un conjunto de strings sobre {a} en el que {a n | n≥0, n≠2 es decir, ‘n’ debe ser mayor que 0 y no igual a 2}.
Explicación: El idioma deseado será como:
L1 = {ε, a, aaa, aaaa, aaaaa, ..................}
Aquí ε se toma como una string porque el valor de ‘n’ es mayor o igual a cero y el resto de las strings tienen ‘a’ elevado a cualquier número natural positivo, pero no 2.
Este DFA no acepta el siguiente lenguaje porque parte de la string que contiene ‘a’ elevada a 2.
L2 = {aa, aaaaa, ..........}
Este idioma L2 no es aceptado por este DFA requerido debido a que su string contiene ‘a’ elevado a 2.
El diagrama de transición de estado del idioma deseado será el siguiente:
En el DFA anterior, el estado inicial y final ‘W’ al obtener ‘a’ como entrada, transita a un estado final ‘X’. El estado final ‘X’ al obtener ‘a’ como entrada, transita a un estado ‘Y’. El estado ‘Y’ al obtener ‘a’ como entrada, transita a un estado final ‘Z’ que al obtener cualquier número de ‘a’ permanece en el estado de sí mismo.
Implementación de Python:
Python3
def stateW(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
#stateX function
if (n[0]=='a'):
stateX(n[1:])
def stateX(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:])
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:])
def stateZ(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
#stateZ function
if (n[0]=='a'):
stateZ(n[1:])
#take input
n=input()
#call stateW function
#to check the input
stateW(n)
Problema-2: Construcción de un DFA mínimo que acepta un conjunto de strings sobre {a} en el que {a n | n≥0, n≠2, n≠4 es decir, ‘n’ debe ser mayor que 0 y no igual a 2 y 4}.
Explicación: El idioma deseado será como:
L1 = {ε, a, aa, aaaaa, aaaaaa, .................. }
Aquí ε se toma como una string porque el valor de ‘n’ es mayor o igual a cero y el resto de las strings tienen ‘a’ a la potencia de cualquier número natural positivo, pero no 2 y 4.
Esto no acepta el lenguaje a continuación . DFA porque parte de la string contiene ‘a’ elevado a 2 y 4.
L2 = {aa, aaaaa, aaaaaaaaaa, ............. }
El diagrama de transición de estado del idioma deseado será el siguiente:
En el DFA anterior, el estado inicial y final ‘A’ al obtener ‘a’ como entrada, transita a un estado final ‘B’. El estado final ‘B’ al obtener ‘a’ como entrada, transita a un estado ‘C’. El estado ‘C’ al obtener ‘a’ como entrada, transita a un estado final ‘D’. El estado final ‘D’ al obtener ‘a’ como entrada, transita a un estado ‘E’. El estado ‘E’ al obtener ‘a’ como entrada, transita a un estado final ‘F’. El estado final ‘F’ al obtener ‘a’ como entrada, permanece en el estado de sí mismo.
Implementación de Python:
Python3
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
#stateB function
if (n[0]=='a'):
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:])
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
#stateD function
if (n[0]=='a'):
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
#stateE function
if (n[0]=='a'):
stateE(n[1:])
def stateE(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
#stateF function
if (n[0]=='a'):
stateF(n[1:])
def stateF(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
#stateF function
if (n[0]=='a'):
stateF(n[1:])
#take input
n=input()
#call stateA function
#to check the input
stateA(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