Investigamos por distintos espacios para de esta forma tener para ti la solución para tu problema, si continúas con alguna inquietud déjanos la inquietud y te contestamos con mucho gusto.
Solución:
A continuación, he escrito una respuesta para n es igual a 5, pero puede aplicar el mismo enfoque para dibujar DFA para cualquier valor de n y ‘cualquier sistema numérico posicional’, por ejemplo, binario, ternario …
Primero apoye el término ‘DFA completo’, un DFA definido en el dominio completo en δ: Q × Σ → Q se llama ‘DFA completo’. En otras palabras, podemos decir; en el diagrama de transición de DFA completo no falta ningún borde (por ejemplo, en cada estado en Q hay un borde saliente presente para cada símbolo de idioma en Σ). Nota: En algún momento definimos DFA parcial como δ ⊆ Q × Σ → Q (Leer: ¿Cómo se lee “δ: Q × Σ → Q” en la definición de un DFA).
Diseñe DFA que acepte números binarios divisibles por el número ‘n’:
Paso 1: Cuando divide un número ω por n entonces el recordatorio puede ser 0, 1, …, (n – 2) o (n – 1). Si el resto es 0 eso significa que ω es divisible por n de otra forma no. Entonces, en mi DFA habrá un estado qr que correspondería a un valor restante r, dónde 0 <= r <= (n - 1), y el número total de estados en DFA es n.
Después de procesar una cadena de números ω sobre Σ, el estado final es qr implica que ω% n => r (% operador recordatorio).
En cualquier autómata, el propósito de un estado es como un elemento de memoria. Un estado en un atomata almacena cierta información, como el interruptor del ventilador, que puede indicar si el ventilador está en estado "apagado" o "encendido". Para n = 5, cinco estados en DFA correspondientes a cinco recordatorios de información de la siguiente manera:
- Estado q0 alcanzado si el recordatorio es 0. Estado q0 es el estado final (estado de aceptación). También es un estado inicial.
- Estado q1 alcanza si el recordatorio es 1, un estado no final.
- Estado q2 si el recordatorio es 2, un estado no final.
- Estado q3 si el recordatorio es 3, un estado no final.
- Estado q4 si el recordatorio es 4, un estado no final.
Usando la información anterior, podemos comenzar a dibujar el diagrama de transición TD de cinco estados de la siguiente manera:
Figura 1
Entonces, 5 estados para 5 valores restantes. Después de procesar una cadena ω si el estado final se convierte en q0 eso significa que el equivalente decimal de la cadena de entrada es divisible por 5. En la figura anterior q0 se marca el estado final como dos círculos concéntricos.
Además, he definido una regla de transición δ: (q0, 0) → q0 como un bucle propio para el símbolo '0' en el estado q0, esto se debe a que el equivalente decimal de cualquier cadena consta de solo '0' es 0 y 0 es divisible por n.
Paso 2: TD anterior está incompleto; y solo puede procesar cadenas de '0's. Ahora agregue algunos bordes más para que pueda procesar las cadenas de números posteriores. Consulte la tabla a continuación, muestra las nuevas reglas de transición que se pueden agregar en el siguiente paso:
┌──────┬──────┬─────────────┬─────────┐ │Number│Binary│Remainder(%5)│End-state│ ├──────┼──────┼─────────────┼─────────┤ │One │1 │1 │q1 │ ├──────┼──────┼─────────────┼─────────┤ │Two │10 │2 │q2 │ ├──────┼──────┼─────────────┼─────────┤ │Three │11 │3 │q3 │ ├──────┼──────┼─────────────┼─────────┤ │Four │100 │4 │q4 │ └──────┴──────┴─────────────┴─────────┘
- Para procesar una cadena binaria
'1'debería haber una regla de transición δ: (q0, 1) → q1 - Dos: - la representación binaria es
'10', el estado final debe ser q2y procesar'10', solo necesitamos agregar una regla de transición más δ: (q1, 0) → q2
Sendero: → (q0) ─1 → (q1) ─0 → (q2) - Tres: - en binario es
'11', el estado final es q3, y necesitamos agregar una regla de transición δ: (q1, 1) → q3
Sendero: → (q0) ─1 → (q1) ─1 → (q3) - Cuatro: - en binario
'100', el estado final es q4. TD ya procesa la cadena de prefijo'10'y solo necesitamos agregar una nueva regla de transición δ: (q2, 0) → q4
Sendero: → (q0) ─1 → (q1) ─0 → (q2) ─0 → (q4)
Figura 2Paso 3: Cinco = 101
El diagrama de transición anterior en la figura 2 aún está incompleto y faltan muchos bordes; por ejemplo, no se define ninguna transición para δ: (q2, 1) -?. Y la regla debe estar presente para procesar cadenas como '101'.
Porque '101' = 5 es divisible por 5, y aceptar '101' Agregaré δ: (q2, 1) → q0 en la figura 2 anterior.
Sendero: → (q0) ─1 → (q1) ─0 → (q2) ─1 → (q0)
con esta nueva regla, el diagrama de transición se convierte en el siguiente:
Figura 3A continuación, en cada paso, elijo el siguiente número binario posterior para agregar un borde faltante hasta que obtenga TD como un 'DFA completo'.
Paso 4: Seis = 110.
Podemos procesar '11' en TD presente en la figura 3 como: → (q0) ─11 → (q3) ─0 → (?). Como 6% 5 = 1, esto significa agregar una regla δ: (q3, 0) → q1.
Figura 4
Figura 4Paso 5: Siete = 111
┌──────┬──────┬─────────────┬─────────┬────────────┬───────────┐ │Number│Binary│Remainder(%5)│End-state│ Path │ Add │ ├──────┼──────┼─────────────┼─────────┼────────────┼───────────┤ │Seven │111 │7 % 5 = 2 │q2 │ q0─11→q3│ q3─1→q2 │ └──────┴──────┴─────────────┴─────────┴────────────┴───────────┘
Figura 5Paso 6: Ocho = 1000
┌──────┬──────┬─────────────┬─────────┬──────────┬─────────┐ │Number│Binary│Remainder(%5)│End-state│ Path │ Add │ ├──────┼──────┼─────────────┼─────────┼──────────┼─────────┤ │Eight │1000 │8 % 5 = 3 │q3 │q0─100→q4 │ q4─0→q3 │ └──────┴──────┴─────────────┴─────────┴──────────┴─────────┘
Figura 6Paso 7: Nueve = 1001
┌──────┬──────┬─────────────┬─────────┬──────────┬─────────┐ │Number│Binary│Remainder(%5)│End-state│ Path │ Add │ ├──────┼──────┼─────────────┼─────────┼──────────┼─────────┤ │Nine │1001 │9 % 5 = 4 │q4 │q0─100→q4 │ q4─1→q4 │ └──────┴──────┴─────────────┴─────────┴──────────┴─────────┘
Figura 7En TD-7, el número total de aristas es 10 == Q × Σ = 5 × 2. Y es un DFA completo que puede aceptar todas las cadenas binarias posibles, el equivalente decimal es divisible por 5.
Diseño DFA aceptando números ternarios divisibles por el número n:
Paso 1 Exactamente igual que para el binario, use la figura 1.
Paso 2 Agregar cero, uno, dos
┌───────┬───────┬─────────────┬─────────┬──────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼──────────────┤ │Zero │0 │0 │q0 │ δ:(q0,0)→q0 │ ├───────┼───────┼─────────────┼─────────┼──────────────┤ │One │1 │1 │q1 │ δ:(q0,1)→q1 │ ├───────┼───────┼─────────────┼─────────┼──────────────┤ │Two │2 │2 │q2 │ δ:(q0,2)→q3 │ └───────┴───────┴─────────────┴─────────┴──────────────┘
Figura 8
Paso 3 Suma tres, cuatro, cinco
┌───────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Three │10 │3 │q3 │ δ:(q1,0)→q3 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Four │11 │4 │q4 │ δ:(q1,1)→q4 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Five │12 │0 │q0 │ δ:(q1,2)→q0 │ └───────┴───────┴─────────────┴─────────┴─────────────┘
Figura 9
Paso 4 Suma seis, siete, ocho
┌───────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Six │20 │1 │q1 │ δ:(q2,0)→q1 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Seven │21 │2 │q2 │ δ:(q2,1)→q2 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Eight │22 │3 │q3 │ δ:(q2,2)→q3 │ └───────┴───────┴─────────────┴─────────┴─────────────┘
Figura-10
Paso 5 Suma nueve, diez, once
┌───────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Nine │100 │4 │q4 │ δ:(q3,0)→q4 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Ten │101 │0 │q0 │ δ:(q3,1)→q0 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Eleven │102 │1 │q1 │ δ:(q3,2)→q1 │ └───────┴───────┴─────────────┴─────────┴─────────────┘
Figura 11
Paso 6 Suma doce, trece, catorce
┌────────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal │Ternary│Remainder(%5)│End-state│ Add │ ├────────┼───────┼─────────────┼─────────┼─────────────┤ │Twelve │110 │2 │q2 │ δ:(q4,0)→q2 │ ├────────┼───────┼─────────────┼─────────┼─────────────┤ │Thirteen│111 │3 │q3 │ δ:(q4,1)→q3 │ ├────────┼───────┼─────────────┼─────────┼─────────────┤ │Fourteen│112 │4 │q4 │ δ:(q4,2)→q4 │ └────────┴───────┴─────────────┴─────────┴─────────────┘
Figura 12
El número total de aristas en el diagrama de transición de la figura 12 es 15 = Q × Σ = 5 * 3 (un DFA completo). Y este DFA puede aceptar que todas las cadenas constan de 0, 1, 2 el equivalente decimal es divisible por 5.
Si observa en cada paso, en la tabla hay tres entradas porque en cada paso agrego todos los bordes salientes posibles de un estado para hacer un DFA completo (y agrego un borde para que qr el estado obtiene por el resto es r)!
Para agregar más, recuerde que la unión de dos idiomas regulares también es regular. Si necesita diseñar un DFA que acepte cadenas binarias, el equivalente decimal es divisible por 3 o 5, luego dibuje dos DFA separados para divisible por 3 y 5, luego combine ambos DFA para construir DFA de destino (para 1 <= n <= 10 tienes que unir 10 DFA).
Si se le pide que dibuje DFA que acepte cadenas binarias de modo que el equivalente decimal sea divisible por 5 y 3, entonces está buscando DFA divisible por 15 (pero ¿qué pasa con 6 y 8?).
Nota: los DFA dibujados con esta técnica se minimizarán DFA solo cuando haya no factor común entre número n y base, por ejemplo, hay no entre 5 y 2 en el primer ejemplo, o entre 5 y 3 en el segundo ejemplo, por tanto, ambos DFA construidos anteriormente son DFA minimizados. Si está interesado en leer más sobre posibles mini estados para el número n y base b Leer artículo: Divisibilidad y Complejidad del Estado.
A continuación, agregué un script de Python, lo escribí para divertirme mientras aprendía pygraphviz de la biblioteca de Python. Lo estoy agregando. Espero que pueda ser útil para alguien de alguna manera.
Diseñe DFA para cadenas de números base 'b' divisibles por el número 'n':
Entonces podemos aplicar el truco anterior para dibujar DFA para reconocer cadenas de números en cualquier base 'b' esos son divisibles un número dado 'n'. En ese DFA, el número total de estados será n (por n restos) y el número de aristas debe ser igual a 'b' * 'n', es decir, DFA completo: 'b' = número de símbolos en el idioma de DFA y 'n' = número de estados.
Usando el truco anterior, a continuación escribí un script de Python para dibujar DFA para la entrada base y number. En script, función divided_by_N completa las reglas de transición de DFA en base * number pasos. En cada paso numérico, convierto num en cadena de números num_s usando la función baseN(). Para evitar procesar cada cadena de números, he usado una estructura de datos temporal lookup_table. En cada paso, estado final de la cadena numérica num_s se evalúa y almacena en lookup_table para usar en el siguiente paso.
Para el gráfico de transición de DFA, escribí una función draw_transition_graph usando la biblioteca Pygraphviz (muy fácil de usar). Para utilizar este script, debe instalar graphviz. Para agregar bordes coloridos en el diagrama de transición, genero códigos de color aleatoriamente para cada símbolo get_color_dict función.
#!/usr/bin/env python
import pygraphviz as pgv
from pprint import pprint
from random import choice as rchoice
def baseN(n, b, syms="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
""" converts a number `n` into base `b` string """
return ((n == 0) and syms[0]) or (
baseN(n//b, b, syms).lstrip(syms[0]) + syms[n % b])
def divided_by_N(number, base):
"""
constructs DFA that accepts given `base` number strings
those are divisible by a given `number`
"""
ACCEPTING_STATE = START_STATE = '0'
SYMBOL_0 = '0'
dfa =
str(from_state):
str(symbol): 'to_state' for symbol in range(base)
for from_state in range(number)
dfa[START_STATE][SYMBOL_0] = ACCEPTING_STATE
# `lookup_table` keeps track: 'number string' -->[dfa]--> 'end_state'
lookup_table = SYMBOL_0: ACCEPTING_STATE .setdefault
for num in range(number * base):
end_state = str(num % number)
num_s = baseN(num, base)
before_end_state = lookup_table(num_s[:-1], START_STATE)
dfa[before_end_state][num_s[-1]] = end_state
lookup_table(num_s, end_state)
return dfa
def symcolrhexcodes(symbols):
"""
returns dict of color codes mapped with alphabets symbol in symbols
"""
return
symbol: '#'+''.join([
rchoice("8A6C2B590D1F4E37") for _ in "FFFFFF"
])
for symbol in symbols
def draw_transition_graph(dfa, filename="filename"):
ACCEPTING_STATE = START_STATE = '0'
colors = symcolrhexcodes(dfa[START_STATE].keys())
# draw transition graph
tg = pgv.AGraph(strict=False, directed=True, decorate=True)
for from_state in dfa:
for symbol, to_state in dfa[from_state].iteritems():
tg.add_edge("Q%s"%from_state, "Q%s"%to_state,
label=symbol, color=colors[symbol],
fontcolor=colors[symbol])
# add intial edge from an invisible node!
tg.add_node('null', shape='plaintext', label='start')
tg.add_edge('null', "Q%s"%START_STATE,)
# make end acception state as 'doublecircle'
tg.get_node("Q%s"%ACCEPTING_STATE).attr['shape'] = 'doublecircle'
tg.draw(filename, prog='circo')
tg.close()
def print_transition_table(dfa):
print("DFA accepting number string in base '%(base)s' "
"those are divisible by '%(number)s':" %
'base': len(dfa['0']),
'number': len(dfa),)
pprint(dfa)
if __name__ == "__main__":
number = input ("Enter NUMBER: ")
base = input ("Enter BASE of number system: ")
dfa = divided_by_N(number, base)
print_transition_table(dfa)
draw_transition_graph(dfa)
Ejecutalo:
~/study/divide-5/script$ python script.py
Enter NUMBER: 5
Enter BASE of number system: 4
DFA accepting number string in base '4' those are divisible by '5':
'0': '0': '0', '1': '1', '2': '2', '3': '3',
'1': '0': '4', '1': '0', '2': '1', '3': '2',
'2': '0': '3', '1': '4', '2': '0', '3': '1',
'3': '0': '2', '1': '3', '2': '4', '3': '0',
'4': '0': '1', '1': '2', '2': '3', '3': '4'
~/study/divide-5/script$ ls
script.py filename.png
~/study/divide-5/script$ display filename
Producción:
DFA acepta cadenas de números en base 4 que son divisibles por 5
De manera similar, ingrese base = 4 y número = 7 para generar - dfa acepta la cadena de números en la base '4', esos son divisibles por '7'
Por cierto, intenta cambiar filename para .png o .jpeg.
Hace referencia a los que utilizo para escribir este script:
➊ Función baseN de "convertir entero a una cadena en una base numérica dada en Python"
➋ Para instalar "pygraphviz": "Python no ve pygraphviz"
➌ Para aprender a usar Pygraphviz: "Python-FSM"
➍ Para generar códigos de color hexadecimales aleatorios para cada símbolo de idioma: "¿Cómo haría un generador de código hexadecimal aleatorio usando .join y para bucles? "
Sé que llegué bastante tarde, pero solo quería agregar algunas cosas a la respuesta ya correcta proporcionada por @Grijesh. Me gustaría señalar que la respuesta proporcionada por @Grijesh no produce el DFA mínimo. Si bien la respuesta seguramente es la forma correcta de obtener un DFA, si necesita el DFA mínimo, tendrá que buscar en su divisor.
Como por ejemplo en los números binarios, si el divisor es una potencia de 2 (es decir, 2 ^ n), entonces el número mínimo de estados requeridos será n + 1. ¿Cómo diseñarías un autómata así? Solo vea las propiedades de los números binarios. Para un número, digamos 8 (que es 2 ^ 3), todos sus múltiplos tendrán los últimos 3 bits como 0. Por ejemplo, 40 en binario es 101000. Por lo tanto, para que un idioma acepte cualquier número divisible por 8, solo necesitamos un autómata que ve si los últimos 3 bits son 0, lo que podemos hacer en solo 4 estados en lugar de 8 estados. Eso es la mitad de la complejidad de la máquina.
De hecho, esto se puede extender a cualquier base. Para un sistema numérico base ternario, si por ejemplo necesitamos diseñar un autómata para divisibilidad con 9, solo necesitamos ver si los últimos 2 números de la entrada son 0. Lo cual nuevamente se puede hacer en solo 3 estados.
Aunque si el divisor no es tan especial, entonces solo debemos seguir con la respuesta de @ Grijesh. Como por ejemplo, en un sistema binario si tomamos los divisores de 3 o 7 o quizás 21, necesitaremos tener esa cantidad de estados solamente. Entonces, para cualquier número impar n en un sistema binario, necesitamos n estados para definir el lenguaje que acepta todos los múltiplos de n. Por otro lado, si el número es par pero no una potencia de 2 (solo en el caso de números binarios) entonces necesitamos dividir el número por 2 hasta que obtengamos un número impar y luego podamos encontrar el número mínimo de estados por sumando el número impar producido y el número de veces que dividimos entre 2.
Por ejemplo, si necesitamos encontrar el número mínimo de estados de un DFA que acepta todos los números binarios divisibles por 20, lo hacemos:
20/2 = 10
10/2 = 5
Por tanto, nuestra respuesta es 5 + 1 + 1 = 7. (El 1 + 1 porque dividimos el número 20 dos veces).
valoraciones y reseñas
Si aceptas, puedes dejar un ensayo acerca de qué te ha parecido este post.