Requisito previo: Introducción a los autómatas finitos , Diseño
del problema de autómatas finitos 1:
Construir DFA, que acepta un conjunto de todas las strings sobre {0, 1} que se interpreta como un número binario divisible por 2.
Explicación:
Considere las siguientes entradas,
{0, 01, 10, 11, 100, 101, 110........}
El diagrama de transición de estado del lenguaje será como:
En este DFA hay dos estados q0 y q1 y la entrada son strings de {0, 1} que se interpretan como números binarios.
El estado q0 es el estado final y q1 es el estado no final. El estado q0 estará representando todos los números que son divisibles por 2, es decir {0, 10, 100, 110…..}.
El estado q1 estará representando todos los números que no son divisibles por 2, es decir {01, 11, 101, ……}.
def stateq0(n): #if length found 0 #print not accepted if (len(n)==0): print("string accepted") else: #if at index 0 #'0' found call #function stateq0 if(n[0]=='0'): stateq0(n[1:]) #else if '1' found #call function q1. elif (n[0]=='1'): stateq1(n[1:]) def stateq1(n): #if length found 0 #print not accepted if (len(n)==0): print("string not accepted") else: #if at index 0 #'0' found call #function stateq0 if(n[0]=='0'): stateq0(n[1:]) #else if '1' found #call function q1. elif (n[0]=='1'): stateq1(n[1:]) #take number from user n=int(input()) #converting number to binary n = bin(n).replace("0b", "") #call stateA #to check the input stateq0(n)
INPUT: 5 OUTPUT: String Not Accepted
Los autómatas anteriores aceptarán un conjunto de todas las strings sobre {0, 1} que, cuando se interpretan como un número binario, es divisible por 2.
Siempre que el número no sea divisible por 2, pasará del estado q0 al q1. Cuando el número es divisible por 2, entonces pasará del estado q1 a q0 o si inicialmente estaba en q0 entonces lo aceptará.
Problema 2:
construya DFA, que acepta un conjunto de todas las strings sobre {0, 1} que interpretado como un número binario es divisible por 3.
Explicación:
consulte la solución: string binaria múltiplo de 3 mediante DFA .
Problema 3:
construya DFA, que acepta un conjunto de todas las strings sobre {0, 1} que interpretado como un número binario es divisible por 4.
Explicación:
Considere las siguientes entradas,
{0, 01, 10, 11, 100, 101, 110........}
El diagrama de transición de estado del lenguaje será como:
Explicación:
En este DFA hay tres estados q0, q1, q2, q3 y la entrada son strings de {0, 1} que se interpretan como números binarios. El estado q0 es el estado final y q1, q2, q3 son estados no finales.
- El estado q0 estará representando todos los números que son divisibles por 4, es decir {0, 100, 1000…..}.
- Indique q1 representará todos los números que no son divisibles por 4 y dará resto 1 cuando se divide por 4, es decir {01, 101,,……}.
- Indique q2 estará representando todos los números que no son divisibles por 4 y dará resto 2 cuando se divide por 4, es decir {10, 110, ……}.
- Indique q4 representará todos los números que no son divisibles por 4 y dará resto 3 cuando se divide por 4, es decir {11, 111, ……}.
Los autómatas anteriores aceptarán un conjunto de todas las strings sobre {0, 1} que, cuando se interpreta como un número binario, es divisible por 4.
- Estado Siempre que el número no sea divisible por 4 y dé resto de 1, pasará al estado q1.
- Estado Siempre que el número no sea divisible por 4 y dé resto de 2, pasará al estado q2.
- Estado Siempre que el número no sea divisible por 4 y dé resto de 3, pasará al estado q3.
- Estado Siempre que el número sea divisible por 4, entonces pasará al estado q0 o si inicialmente estaba en q0 entonces lo aceptará.
def stateq0(n): #if length found 0 #print not accepted if (len(n)==0): print("string accepted") else: #if at index 0 #'0' found call #function stateq0 if(n[0]=='0'): stateq0(n[1:]) #else if '1' found #call function q1. elif (n[0]=='1'): stateq1(n[1:]) def stateq1(n): #if length found 0 #print not accepted if (len(n)==0): print("string not accepted") else: #if at index 0 #'0' found call #function stateq2 if(n[0]=='0'): stateq2(n[1:]) #else if '1' found #call function q3. elif (n[0]=='1'): stateq3(n[1:]) def stateq2(n): #if length found 0 #print not accepted if (len(n)==0): print("string not accepted") else: #if at index 0 #'0' found call #function stateq0 if(n[0]=='0'): stateq0(n[1:]) #else if '1' found #call function q1. elif (n[0]=='1'): stateq1(n[1:]) def stateq3(n): #if length found 0 #print not accepted if (len(n)==0): print("string not accepted") else: #if at index 0 #'0' found call #function stateq2 if(n[0]=='0'): stateq2(n[1:]) #else if '1' found #call function q3. elif (n[0]=='1'): stateq3(n[1:]) #take number from user n=int(input()) #converting number to binary n = bin(n).replace("0b", "") #call stateA #to check the input stateq0(n)
Publicación traducida automáticamente
Artículo escrito por AarchiAgrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA