Requisito previo : problema de introducción a los autómatas finitos: dibujar autómatas finitos deterministas (DFA) del lenguaje que contiene el conjunto de todas las strings sobre {a, b} en el que el segundo símbolo de RHS es ‘a’.
Las strings en las que el penúltimo símbolo es «a» son:
aa, ab, aab, aaa, aabbaa, bbbab etc
Por ejemplo:
INPUT : baba OUTPUT: NOT ACCEPTED INPUT: aaab OUTPUT: ACCEPTED
Construir directamente el DFA del problema dado es muy complicado. Entonces, aquí vamos a diseñar los autómatas finitos no deterministas (NFA) y luego convertirlos en autómatas finitos deterministas (DFA).
El NFA del idioma que contiene todas las strings en las que el segundo símbolo de la RHS es «a» es:
Aquí, A es el estado inicial y C es el estado final.
Ahora, vamos a construir la tabla de transición de estado de la NFA anterior.
Después de eso, dibujaremos la tabla de transición de estado de DFA utilizando la configuración de subconjuntos en la tabla de transición de estado de NFA. Mencionaremos todas las transiciones posibles para a y b.
Ahora es muy fácil dibujar el DFA con la ayuda de su tabla de transición. En este DFA, tenemos cuatro estados diferentes A, AB, ABC y AC, donde ABC y AC son los estados finales y A es el estado inicial del DFA.
Este es nuestro DFA requerido del idioma que contiene el conjunto de todas las strings sobre {a, b} en el que el segundo símbolo de RHS es ‘a’.
Tabla de transición:
| ESTADOS | ENTRADA (a) | ENTRADA (b) |
| —> A (estado inicial) | AB | A |
| AB | ABC* (estado final) | AC* (estado final) |
| AC* (estado final) | AB | A |
| ABC* (estado final) | ABC* (estado final) | AC* (estado final) |
Implementación de Python:
def stateA(n):
#if length found 0
#print not accepted
if (len(n)==0):
print("string not accepted")
else:
#if at index 0
#'a' found call
#function stateAB
if(n[0]=='a'):
stateAB(n[1:])
#else if 'b' found
#call function A.
elif (n[0]=='b'):
stateA(n[1:])
def stateAB(n):
#if length found 0
#print not accepted
if (len(n)==0):
print("string not accepted")
else:
#if at index 0
#'a' found call
#function stateABC
if(n[0]=='a'):
stateABC(n[1:])
#else if 'b' found
#call function AC.
elif (n[0]=='b'):
stateAC(n[1:])
def stateABC(n):
#if length found 0
#print accepted
if (len(n)==0):
print("string accepted")
else:
#if at index 0
#'a' found call
#function stateABC
if(n[0]=='a'):
stateABC(n[1:])
#else if 'b' found
#call function AC.
elif (n[0]=='b'):
stateAC(n[1:])
def stateAC(n):
#if length found 0
#print accepted
if (len(n)==0):
print("string accepted")
else:
#if at index 0
#'a' found call
#function stateAB
if(n[0]=='a'):
stateAB(n[1:])
#else if 'b' found
#call function A.
elif (n[0]=='b'):
stateA(n[1:])
#take string input
n=input()
#call stateA
#to check the input
stateA(n)
Publicación traducida automáticamente
Artículo escrito por SUDIPTADANDAPAT y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA