machine - regex online c#

Design DFA que acepta cadenas binarias divisibles por un número ''n''

Question

Necesito aprender cómo diseñar un DFA de modo que dado cualquier número ''n'', acepte cadenas binarias {0, 1} cuyo número equivalente decimal sea divisible por ''n''. Habrá diferentes DFA para diferentes ''n'', pero alguien puede dar un enfoque básico que debo seguir para proceder con cualquier número 0 <n <10.

Answer 1

A continuación, he escrito una respuesta para n igual a 5, pero puede aplicar el mismo enfoque para dibujar DFA para cualquier valor de n ''cualquier sistema de número posicional'', por ejemplo, binario, ternario ...

Primero, utilice el término "DFA completo", un DFA definido en dominio completo en δ: Q × Σ → Q se denomina "DFA completo". En otras palabras, podemos decir; en el diagrama de transición del DFA completo no hay ningún borde faltante (por ejemplo, de cada estado en Q hay un borde de salida presente para cada símbolo de idioma en Σ). Nota: En algún momento definimos partial DFA partial como δ ⊆ Q × Σ → Q (Lectura: ¿Cómo se lee "δ: Q × Σ → Q" en la definición de un DFA ).

Design DFA que acepta números binarios divisibles por el número ''n'':

Paso-1 : cuando divide un número ω por n , el recordatorio puede ser 0, 1, ..., (n - 2) o (n - 1). Si el resto es 0 eso significa que ω es divisible por n contrario no. Por lo tanto, en mi DFA habrá un estado q _r que correspondería a un valor restante r , donde 0 <= r <= (n - 1) y el número total de estados en DFA es n .
Después de procesar una cadena numérica ω sobre Σ, el estado final es q _r 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 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 corresponden a cinco información recordatoria de la siguiente manera:

1. Estado q ₀ alcanzado si el recordatorio es 0. Estado q ₀ es el estado final (estado de aceptación). También es un estado inicial.
2. Estado q ₁ alcanza si el recordatorio es 1, un estado no final.
3. Indique q ₂ si el recordatorio es 2, un estado no final.
4. Indique q ₃ si el recordatorio es 3, un estado no final.
5. Indique q ₄ 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 q _0, significa que el equivalente decimal de la cadena de entrada es divisible por 5. En la figura anterior q ₀ se marca el estado final como dos círculos concéntricos.
Además, he definido una regla de transición δ: (q ₀ , 0) → q ₀ como un bucle automático para el símbolo ''0'' en el estado q ₀ , esto es porque el equivalente decimal de cualquier cadena consiste en solo ''0'' es 0 y 0 es divisible por n .

Paso 2 : el TD anterior está incompleto; y solo puede procesar cadenas de ''0'' . Ahora agregue algunos bordes más para que pueda procesar las cadenas de números subsiguientes. Verifique la tabla a continuación, muestra las nuevas reglas de transición que pueden agregarse al siguiente paso:

┌──────┬──────┬─────────────┬─────────┐ │Number│Binary│Remainder(%5)│End-state│ ├──────┼──────┼─────────────┼─────────┤ │One │1 │1 │q₁ │ ├──────┼──────┼─────────────┼─────────┤ │Two │10 │2 │q₂ │ ├──────┼──────┼─────────────┼─────────┤ │Three │11 │3 │q₃ │ ├──────┼──────┼─────────────┼─────────┤ │Four │100 │4 │q₄ │ └──────┴──────┴─────────────┴─────────┘

1. Para procesar la cadena binaria ''1'' debe haber una regla de transición δ: (q ₀ , 1) → q ₁
2. Dos: - la representación binaria es ''10'' , el estado final debe ser q ₂ , y para procesar ''10'' , solo necesitamos agregar una regla de transición más δ: (q ₁ , 0) → q ₂
   Ruta : → (q ₀ ) ─1 → (q ₁ ) ─0 → (q ₂ )
3. Tres: - en binario es ''11'' , el estado final es q ₃ , y necesitamos agregar una regla de transición δ: (q ₁ , 1) → q ₃
   Ruta : → (q ₀ ) ─1 → (q ₁ ) ─1 → (q ₃ )
4. Cuatro: en el binario ''100'' , el estado final es q ₄ . TD ya procesa el prefijo cadena ''10'' y solo necesitamos agregar una nueva regla de transición δ: (q ₂ , 0) → q ₄
   Ruta : → (q ₀ ) ─1 → (q ₁ ) ─0 → (q ₂ ) ─0 → (q ₄ )

Figura 2

Paso-3 : Cinco = 101
El diagrama de transición anterior en la figura 2 aún está incompleto y hay muchos bordes faltantes, por ejemplo, no se define transición para δ: (q ₂ , 1) - ? . Y la regla debería estar presente para procesar cadenas como ''101'' .
Como ''101'' = 5 es divisible por 5, y para aceptar ''101'' agregaré δ: (q ₂ , 1) → q ₀ en la figura 2 anterior.
Ruta: → (q ₀ ) ─1 → (q ₁ ) ─0 → (q ₂ ) ─1 → (q ₀ )
con esta nueva regla, el diagrama de transición se convierte en lo siguiente:

Figura 3

A continuación, en cada paso, elijo el siguiente número binario para agregar un borde que falta hasta que obtengo TD como un ''DFA completo''.

Paso-4 : Seis = 110.

Podemos procesar ''11'' en el presente TD en la figura-3 como: → (q ₀ ) ─11 → (q ₃ ) ─0 → ( ? ). Debido a que 6% 5 = 1 esto significa agregar una regla δ: (q ₃ , 0) → q ₁ .

Figura 4

Paso-5 : Siete = 111

┌──────┬──────┬─────────────┬─────────┬────────────┬───────────┐ │Number│Binary│Remainder(%5)│End-state│ Path │ Add │ ├──────┼──────┼─────────────┼─────────┼────────────┼───────────┤ │Seven │111 │7 % 5 = 2 │q₂ │ q₀─11→q₃ │ q₃─1→q₂ │ └──────┴──────┴─────────────┴─────────┴────────────┴───────────┘

Figura 5

Paso-6 : Ocho = 1000

┌──────┬──────┬─────────────┬─────────┬──────────┬─────────┐ │Number│Binary│Remainder(%5)│End-state│ Path │ Add │ ├──────┼──────┼─────────────┼─────────┼──────────┼─────────┤ │Eight │1000 │8 % 5 = 3 │q₃ │q₀─100→q₄ │ q₄─0→q₃ │ └──────┴──────┴─────────────┴─────────┴──────────┴─────────┘

Figura-6

Paso-7 : Nueve = 1001

┌──────┬──────┬─────────────┬─────────┬──────────┬─────────┐ │Number│Binary│Remainder(%5)│End-state│ Path │ Add │ ├──────┼──────┼─────────────┼─────────┼──────────┼─────────┤ │Nine │1001 │9 % 5 = 4 │q₄ │q₀─100→q₄ │ q₄─1→q₄ │ └──────┴──────┴─────────────┴─────────┴──────────┴─────────┘

Figura-7

En TD-7, el número total de bordes es 10 == Q × Σ = 5 × 2. Y es un DFA completo que puede aceptar todas las cadenas binarias posibles, ese equivalente decimal es divisible por 5.

Design DFA que acepta números ternarios divisibles por el número n:

Paso-1 Exactamente igual que para el binario, use la figura-1.

Paso-2 Agregue 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 Agregue 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 Agregue 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 Agregue 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 Añade 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 figura 12 es 15 = Q × Σ = 5 * 3 (un DFA completo). Y este DFA puede aceptar que todas las cadenas estén compuestas por {0, 1, 2} que 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 el estado q _{r se} obtenga para 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, ese equivalente decimal es divisible entre 3 o 5, luego dibuje dos DFA separados para divisible entre 3 y 5, luego unir ambos DFA para construir DFA objetivo (para 1 <= n <= 10 tienes que unir 10 DFA de la unión).

Si le piden que dibuje DFA que acepte cadenas binarias de modo que ese equivalente decimal sea divisible entre 5 y 3, entonces está buscando DFA divisible entre 15 (¿pero qué pasa con 6 y 8?).

Nota: los DFA dibujados con esta técnica se minimizarán DFA solo cuando no haya un factor común entre el número n base; por ejemplo, no hay entre 5 y 2 en el primer ejemplo, o entre 5 y 3 en el segundo ejemplo, por lo tanto, ambos DFA construidos anteriormente son DFA minimizados. Si le interesa leer más acerca de los posibles mini estados para el número n y la base b lea el documento: Divisibilidad y Complejidad del Estado .

^{a continuación he agregado un script de Python, lo escribí por diversión mientras aprendía la biblioteca de Python pygraphviz. Lo estoy agregando. Espero que pueda ser útil para alguien de alguna manera.}

Diseño de DFA para cadenas de números ''b'' base divisibles por el número ''n'':

Así que podemos aplicar el truco anterior para dibujar DFA para reconocer cadenas de números en cualquier base ''b'' sean divisibles por un número dado ''n'' . En ese DFA, el número total de estados será n (para n residuos) y el número de bordes debe ser igual a ''b'' * ''n''; eso es completo DFA: ''b'' = número de símbolos en el lenguaje de DFA y ''n ''= número de estados.

Utilizando el truco anterior, a continuación he escrito un script de Python para dibujar DFA para la base y el number entrada. En el script, la función divided_by_N rellena las reglas de transición de DFA en pasos de base * number . En cada paso-num, convierto num en numérico string num_s usando function baseN() . Para evitar procesar cada cadena numérica, he usado una estructura de datos temporal lookup_table . En cada paso, el estado final para el número de cadena 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, he escrito una función draw_transition_graph utilizando la biblioteca Pygraphviz (muy fácil de usar). Para usar este script, necesitas instalar graphviz . Para agregar bordes coloridos en el diagrama de transición, genero aleatoriamente códigos de color para cada función de símbolo get_color_dict .

#!/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

Salida:

DFA acepta cadenas de números en la base 4, que son divisibles por 5

Del mismo modo, ingrese base = 4 y number = 7 para generar - dfa aceptar cadena de números en la base ''4'', que son divisibles por ''7''
Por cierto, intente cambiar el filename de filename a .png o .jpeg .

_{Referencias a las que uso para escribir este script:
➊ baseN de baseN desde baseN()
➋ Para instalar "pygraphviz": "Python no ve pygraphviz"
➌ Para aprender el uso de Pygraphviz: "Python-FSM"
➍ Generar códigos de color hexadecimales aleatorios para cada símbolo de idioma: "¿Cómo crearía un generador de código aleatorio de dígitos hexadecimales utilizando .join y para bucles?"}

Answer 2

Sé que llegué bastante tarde, pero solo quería agregar algunas cosas a la respuesta correcta ya provista por @Grijesh. Me gustaría simplemente señalar que la respuesta proporcionada por @Grijesh no produce el DFA mínimo. Si bien la respuesta es seguramente la forma correcta de obtener un DFA, si necesita el DFA mínimo, tendrá que buscar en su divisor.

Como por ejemplo en 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 ese autómata? Solo ve 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. Esa es la mitad de la complejidad de la máquina.

De hecho, esto se puede extender a cualquier base. Para un sistema de números base ternarios, si por ejemplo necesitamos diseñar un autómata para la divisibilidad con 9, solo necesitamos ver si los últimos 2 números de la entrada son 0. Lo cual puede hacerse nuevamente en solo 3 estados.

Aunque si el divisor no es tan especial, entonces tenemos que seguir con la respuesta de @ Grijesh solamente. Como por ejemplo, en un sistema binario si tomamos los divisores de 3 o 7 o tal vez 21, tendremos que 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 acepte todos los múltiplos de n. Por otro lado, si el número es par, pero no es una potencia de 2 (solo en el caso de números binarios), entonces debemos dividir el número entre 2 hasta obtener un número impar y luego podemos encontrar el número mínimo de estados por agregando el número impar producido y el número de veces que dividimos por 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, hacemos:

20/2 = 10 
10/2 = 5

Por lo tanto, nuestra respuesta es 5 + 1 + 1 = 7 . (El 1 + 1 porque dividimos el número 20 dos veces).