Design-DFA akzeptiert binäre Zeichenfolgen, die durch eine Zahl 'n' teilbar sind.

Question 1

Ich muss lernen, wie man einen DFA so entwirft, dass er bei einer beliebigen Zahl 'n' binäre Zeichenfolgen {0, 1} akzeptiert, deren dezimale Äquivalentzahl durch 'n' teilbar ist.

Es wird verschiedene DFAs für verschiedene 'n' geben, aber kann jemand einen grundlegenden Ansatz nennen, dem ich folgen sollte, um mit einer beliebigen Zahl 0 <n <10 fortzufahren.

Question 2

Im Folgenden habe ich eine Antwort für ngleich 5 geschrieben, aber Sie können denselben Ansatz anwenden, um DFAs für jeden Wert nund jedes Positionsnummernsystem zu zeichnen , z. B. binär, ternär ...

Zuerst den Begriff 'Vollständiger DFA' verwenden. Ein DFA , der für die vollständige Domäne in δ: Q × Σ → Q definiert ist, wird als 'Vollständiger DFA' bezeichnet. Mit anderen Worten können wir sagen; Im Übergangsdiagramm des vollständigen DFA fehlt keine Kante (z. B. ist von jedem Zustand in Q für jedes Sprachsymbol in Σ eine ausgehende Kante vorhanden). Hinweis: Manchmal definieren wir partielle DFA als δ ⊆ Q × Σ → Q (Lesen: Wie liest „δ: Q × Σ → Q“ in der Definition einer DFA ).

Design DFA akzeptiert Binärzahlen, die durch die Zahl 'n' teilbar sind:

Schritt 1 : Wenn Sie eine Zahl ω durch dividieren, nkann die Erinnerung entweder 0, 1, ..., (n - 2) oder (n - 1) sein. Wenn der Rest ist 0, bedeutet dies, dass ω durch nsonst nicht teilbar ist . In meinem DFA gibt es also einen Zustand q _r , der einem Restwert entspricht r, wobei 0 <= r <= (n - 1)und die Gesamtzahl der Zustände in DFA ist n.
Nach der Verarbeitung einer Zahlenfolge ω über Σ impliziert der Endzustand q _r , dass ω% n => r (% Erinnerungsoperator).

In allen Automaten ist der Zweck eines Zustands wie ein Speicherelement. Ein Zustand in einem Atomata speichert einige Informationen wie den Schalter des Lüfters, die erkennen können, ob sich der Lüfter im Zustand "Aus" oder "Ein" befindet. Für n = 5 entsprechen fünf Zustände in DFA fünf Erinnerungsinformationen wie folgt:

Zustand q ₀ erreicht, wenn Erinnerung 0 ist. Zustand q ₀ ist der Endzustand (akzeptierender Zustand). Es ist auch ein Ausgangszustand.
Der Zustand q ₁ erreicht, wenn die Erinnerung 1 ist, einen nicht endgültigen Zustand.
Zustand q _2, wenn Erinnerung 2 ist, ein nicht endgültiger Zustand.
Zustand q _3, wenn Erinnerung 3 ist, ein nicht endgültiger Zustand.
Zustand q _4, wenn Erinnerung 4 ist, ein nicht endgültiger Zustand.

Unter Verwendung der obigen Informationen können wir mit dem Zeichnen des Übergangsdiagramms TD von fünf Zuständen wie folgt beginnen:

Abbildung 1

Also 5 Zustände für 5 Restwerte. Nach der Verarbeitung einer Zeichenfolge ω, wenn der Endzustand zu q _{0 wird} , bedeutet dies, dass das Dezimaläquivalent der Eingabezeichenfolge durch 5 teilbar ist. In der obigen Abbildung ist q ₀ als Endzustand als zwei konzentrische Kreise markiert.
Zusätzlich habe ich eine Übergangsregel δ definiert: (q ₀ , 0) → q ₀ als Selbstschleife für das Symbol '0'im Zustand q ₀ , weil das Dezimaläquivalent einer Zeichenfolge nur aus '0'0 besteht und 0 durch teilbar ist n.

Schritt 2 : TD oben ist unvollständig; und kann nur Strings von '0's verarbeiten. Fügen Sie nun einige weitere Kanten hinzu, damit die Zeichenfolgen der nachfolgenden Zahlen verarbeitet werden können. Die folgende Tabelle zeigt neue Übergangsregeln, die im nächsten Schritt hinzugefügt werden können:

┌───────────────────────────────────────┐
│ Zahl │ Binär │ Rest (% 5) │ Endzustand │
├───────────────────────────────────────┤
│Ein │1 │1 │q ₁        │
├───────────────────────────────────────┤
WoZwei │10 │2 │q ₂        │
├───────────────────────────────────────┤
HreDrei │11 │3 │q ₃        │
├───────────────────────────────────────┤
OurVier │100 │4 │q ₄        │
└───────────────────────────────────────┘

Um eine binäre Zeichenfolge '1'zu verarbeiten, sollte es eine Übergangsregel δ geben: (q ₀ , 1) → q ₁
Zwei: - Die binäre Darstellung ist '10', der Endzustand sollte q _{2 sein} , und um zu verarbeiten '10', müssen wir nur eine weitere Übergangsregel hinzufügen δ: (q ₁ , 0) → q ₂
Pfad : → (q ₀ ) ─1 → ( q ₁ ) ─0 → (q ₂ )
Drei: - Binär ist der Endzustand '11'q ₃ , und wir müssen eine Übergangsregel δ hinzufügen: (q ₁ , 1) → q ₃
Pfad : → (q ₀ ) ─1 → (q ₁ ) ─1 → (q ₃ )
Viertens: - Im Binärzustand '100'ist der Endzustand q ₄ . TD verarbeitet bereits die Präfixzeichenfolge '10'und wir müssen nur eine neue Übergangsregel δ hinzufügen: (q ₂ , 0) → q ₄
Pfad : → (q ₀ ) ─ 1 → (q ₁ ) ─ 0 → (q ₂ ) ─ 0 → (q ₄ )

Figur 2

Schritt 3 : Fünf = 101 Das
obige Übergangsdiagramm in Abbildung 2 ist noch unvollständig und es fehlen viele Kanten. Für ein Beispiel ist kein Übergang für δ definiert: (q ₂ , 1) - ? . Und die Regel sollte vorhanden sein, um Strings wie zu verarbeiten '101'.
Weil '101'= 5 durch 5 teilbar ist, und um zu akzeptieren '101', füge ich δ hinzu: (q ₂ , 1) → q ₀ in der obigen Abbildung-2.
Pfad: → (q ₀ ) ─1 → (q ₁ ) ─0 → (q ₂ ) ─1 → (q ₀ )
Mit dieser neuen Regel wird das Übergangsdiagramm wie folgt:

Figur 3

Unten in jedem Schritt wähle ich die nächste nachfolgende Binärzahl aus, um eine fehlende Kante hinzuzufügen, bis ich TD als 'vollständigen DFA' erhalte.

Schritt 4 : Sechs = 110.

Wir können '11'TD in Abbildung 3 wie folgt verarbeiten : → (q ₀ ) ─11 → (q ₃ ) ─0 → ( ? ). Da 6% 5 = 1 ist, bedeutet dies, eine Regel δ hinzuzufügen: (q ₃ , 0) → q ₁ .

Figur 4

Schritt 5 : Sieben = 111

┌─────────────────────────────────────────────────── ─┬────────────┐
│ Zahl │ Binär │ Rest (% 5) │ Endzustand │ Pfad        │ Hinzufügen        │
├─────────────────────────────────────────────────── ─┼────────────┤
│Seven │111 │7% 5 = 2 │q ₂        │ q ₀ ─ 11 → q ₃   │ q ₃ ─ 1 → q ₂     │
└─────────────────────────────────────────────────── ─┴────────────┘

Abbildung 5

Schritt 6 : Acht = 1000

┌─────────────────────────────────────────────────┬ ─────────┐
│ Zahl │ Binär │ Rest (% 5) │ Endzustand │ Pfad      │ Hinzufügen      │
├─────────────────────────────────────────────────┼ ─────────┤
Ight Acht %1000 │8% 5 = 3 │q ₃        │q ₀ ─100 → q ₄ │ q ₄ ─0 → q ₃   │
└─────────────────────────────────────────────────┴ ─────────┘

Abbildung 6

Schritt 7 : Neun = 1001

┌─────────────────────────────────────────────────┬ ─────────┐
│ Zahl │ Binär │ Rest (% 5) │ Endzustand │ Pfad      │ Hinzufügen      │
├─────────────────────────────────────────────────┼ ─────────┤
│Nein │1001 │9% 5 = 4 │q ₄        │q ₀ ─100 → q ₄ │ q ₄ ─1 → q ₄   │
└─────────────────────────────────────────────────┴ ─────────┘

Abbildung 7

In TD-7 beträgt die Gesamtzahl der Kanten 10 == Q × Σ = 5 × 2. Und es ist ein vollständiger DFA, der alle möglichen binären Zeichenfolgen akzeptieren kann, deren Dezimaläquivalent durch 5 teilbar ist.

Design DFA akzeptiert ternäre Zahlen, die durch die Zahl n teilbar sind:

Schritt-1 Verwenden Sie genau wie für binär Abbildung-1.

Schritt 2 Fügen Sie Null, Eins, Zwei hinzu

┌────────────────────────────────────────────────── ─────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │    Hinzufügen         │
├────────────────────────────────────────────────── ─────┤
EroZero │0 │0 │q0 │ δ: (q0,0) → q0 │
├────────────────────────────────────────────────── ─────┤
NeEin │1 │1 │q1 │ δ: (q0,1) → q1 │
├────────────────────────────────────────────────── ─────┤
WoZwei │2 │2 │q2 │ δ: (q0,2) → q3 │
└────────────────────────────────────────────────── ─────┘

Abbildung 8

Schritt 3 Fügen Sie drei, vier, fünf hinzu

┌────────────────────────────────────────────────── ────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │   Hinzufügen         │
├────────────────────────────────────────────────── ────┤
HreDrei │10 │3 │q3 │ δ: (q1,0) → q3 │
├────────────────────────────────────────────────── ────┤
OurVier │11 │4 │q4 │ δ: (q1,1) → q4 │
├────────────────────────────────────────────────── ────┤
IveFive │12 │0 │q0 │ δ: (q1,2) → q0 │
└────────────────────────────────────────────────── ────┘

Abbildung 9

Schritt 4 Fügen Sie sechs, sieben, acht hinzu

┌────────────────────────────────────────────────── ────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │   Hinzufügen         │
├────────────────────────────────────────────────── ────┤
│Six │20 │1 │q1 │ δ: (q2,0) → q1 │
├────────────────────────────────────────────────── ────┤
│Seven │21 │2 │q2 │ δ: (q2,1) → q2 │
├────────────────────────────────────────────────── ────┤
│ Acht │22 │3 │q3 │ δ: (q2,2) → q3 │
└────────────────────────────────────────────────── ────┘

Abbildung 10

Schritt 5 Fügen Sie neun, zehn, elf hinzu

┌────────────────────────────────────────────────── ────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │   Hinzufügen         │
├────────────────────────────────────────────────── ────┤
IneNein │100 │4 │q4 │ δ: (q3,0) → q4 │
├────────────────────────────────────────────────── ────┤
│Ten │101 │0 │q0 │ δ: (q3,1) → q0 │
├────────────────────────────────────────────────── ────┤
LeEleven │102 │1 │q1 │ δ: (q3,2) → q1 │
└────────────────────────────────────────────────── ────┘

Abbildung 11

Schritt 6 Addiere zwölf, dreizehn, vierzehn

┌─────────────────────────────────────────────────── ─────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │   Hinzufügen         │
├─────────────────────────────────────────────────── ─────┤
Zwölf wel110 │2 │q2 │ δ: (q4,0) → q2 │
├─────────────────────────────────────────────────── ─────┤
│Dreißig│111 │3 │q3 │ δ: (q4,1) → q3 │
├─────────────────────────────────────────────────── ─────┤
Our Vierzehn│112 │4 │q4 │ δ: (q4,2) → q4 │
└─────────────────────────────────────────────────── ─────┘

Abbildung 12

Die Gesamtzahl der Kanten im Übergangsdiagramm in Abbildung 12 beträgt 15 = Q × Σ = 5 * 3 (ein vollständiger DFA). Und dieser DFA kann akzeptieren, dass alle Zeichenfolgen über {0, 1, 2} bestehen. Diese Dezimaläquivalente sind durch 5 teilbar.
Wenn Sie bei jedem Schritt feststellen, gibt es in der Tabelle drei Einträge, da ich bei jedem Schritt alle möglichen ausgehenden Flanken aus einem Zustand hinzufüge um einen vollständigen DFA zu erstellen (und ich füge eine Kante hinzu, damit q _r state für den Rest erhalten wird r)!

Denken Sie daran, dass die Vereinigung zweier regulärer Sprachen ebenfalls eine reguläre ist. Wenn Sie einen DFA entwerfen müssen, der binäre Zeichenfolgen akzeptiert, ist dieses Dezimaläquivalent entweder durch 3 oder 5 teilbar. Zeichnen Sie dann zwei separate DFAs für teilbar durch 3 und 5, und vereinigen Sie dann beide DFAs, um das Ziel-DFA zu erstellen (für 1 <= n <= 10) Sie müssen 10 DFAs vereinen).

Wenn Sie aufgefordert werden, DFA zu zeichnen, das binäre Zeichenfolgen so akzeptiert, dass das Dezimaläquivalent durch 5 und 3 teilbar ist, suchen Sie nach DFA, das durch 15 teilbar ist (aber was ist mit 6 und 8?).

Hinweis: Mit dieser Technik gezeichnete DFAs werden nur dann minimiert, wenn es keinen gemeinsamen Faktor zwischen Zahl nund Basis gibt, z. B. gibt es im ersten Beispiel keinen zwischen 5 und 2 oder im zweiten Beispiel zwischen 5 und 3, daher werden beide oben konstruierten DFAs minimiert DFAs. Wenn Sie mehr über mögliche Mini-Zustände für Zahlen nund Basis blesen möchten, lesen Sie das Papier: Teilbarkeit und Zustandskomplexität .

^{Unten habe ich ein Python-Skript hinzugefügt. Ich habe es zum Spaß geschrieben, während ich die Python-Bibliothek pygraphviz gelernt habe. Ich füge es hinzu. Ich hoffe, es kann irgendwie für jemanden hilfreich sein.}

Entwerfen Sie den DFA für die durch die Zahl 'n' teilbaren Zeichenfolgen der Basis 'b':

Wir können also den obigen Trick anwenden, um DFA zu zeichnen, um Zahlenfolgen in jeder Basis zu erkennen, 'b'die durch eine bestimmte Zahl teilbar sind 'n'. In diesem DFA ist die Gesamtzahl der Zustände n(für nReste) und die Anzahl der Kanten sollte gleich 'b' * 'n' sein - das ist vollständig. DFA: 'b' = Anzahl der Symbole in der Sprache des DFA und 'n' = Anzahl der Staaten.

Mit dem obigen Trick habe ich unten ein Python-Skript geschrieben, um DFA für die Eingabe baseund zu zeichnen number. Im Skript divided_by_Nfüllt die Funktion die Übergangsregeln von DFA base * numberschrittweise aus. In jeder Schrittnummer konvertiere ich mit der Funktion numin eine Zahlenfolge . Um zu vermeiden, dass jede Zahlenfolge verarbeitet wird, habe ich eine temporäre Datenstruktur verwendet . In jedem Schritt wird der Endzustand für die Zahlenzeichenfolge ausgewertet und gespeichert , um im nächsten Schritt verwendet zu werden.num_sbaseN()lookup_tablenum_slookup_table

Für den Übergangsgraphen von DFA habe ich eine Funktion draw_transition_graphmit der Pygraphviz-Bibliothek geschrieben (sehr einfach zu bedienen). Um dieses Skript verwenden zu können, müssen Sie es installieren graphviz. Um dem Übergangsdiagramm farbige Kanten hinzuzufügen, generiere ich zufällig Farbcodes für jede Symbolfunktion 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)

Führ es aus:

~/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

Ausgabe:

DFA akzeptiert Zahlenfolgen in Basis 4, die durch 5 teilbar sind

In ähnlicher Weise geben Sie base = 4 und number = 7 ein, um zu generieren - dfa akzeptiert Zahlenzeichenfolge in base '4', die durch '7' teilbar sind.
Versuchen Sie, filenamezu .pngoder zu wechseln .jpeg.

_{Verweist auf
diejenigen, die ich zum Schreiben dieses Skripts verwende: ➊ Funktion baseNvon "Ganzzahl in eine Zeichenfolge in einer bestimmten numerischen Basis in Python

konvertieren " ➋ So installieren Sie "pygraphviz": "Python sieht pygraphviz nicht"

➌ So lernen Sie die Verwendung von Pygraphviz: "Python- FSM "

➍ So generieren Sie zufällige Hex-Farbcodes für jedes Sprachsymbol: " Wie würde ich einen zufälligen Hexdigit-Code-Generator mit .join und for-Schleifen erstellen? "}

Question 3

Ich weiß, dass ich ziemlich spät dran bin, aber ich wollte der bereits korrekten Antwort von @Grijesh nur ein paar Dinge hinzufügen. Ich möchte nur darauf hinweisen, dass die Antwort von @Grijesh nicht den minimalen DFA ergibt. Während die Antwort sicherlich der richtige Weg ist, um einen DFA zu erhalten, müssen Sie, wenn Sie den minimalen DFA benötigen, in Ihren Divisor schauen.

Wie zum Beispiel bei Binärzahlen beträgt die Mindestanzahl der erforderlichen Zustände n + 1, wenn der Divisor eine Potenz von 2 (dh 2 ^ n) ist. Wie würden Sie einen solchen Automaten entwerfen? Sehen Sie sich nur die Eigenschaften von Binärzahlen an. Für eine Zahl, sagen wir 8 (das ist 2 ^ 3), haben alle ihre Vielfachen die letzten 3 Bits als 0. Zum Beispiel ist 40 in binär 101000. Damit eine Sprache eine durch 8 teilbare Zahl akzeptiert, brauchen wir nur eine Automat, der sieht, ob die letzten 3 Bits 0 sind, was wir in nur 4 Zuständen anstelle von 8 Zuständen tun können. Das ist die halbe Komplexität der Maschine.

Tatsächlich kann dies auf jede Basis erweitert werden. Wenn wir für ein ternäres Basisnummernsystem beispielsweise einen Automaten für die Teilbarkeit mit 9 entwerfen müssen, müssen wir nur sehen, ob die letzten 2 Zahlen der Eingabe 0 sind. Dies kann wiederum in nur 3 Zuständen erfolgen.

Wenn der Divisor nicht so besonders ist, müssen wir nur die Antwort von @ Grijesh durchgehen. Wie zum Beispiel in einem binären System, wenn wir die Teiler von 3 oder 7 oder vielleicht 21 nehmen, müssen wir nur so viele Zustände haben. Für jede ungerade Zahl n in einem Binärsystem benötigen wir n Zustände, um die Sprache zu definieren, die alle Vielfachen von n akzeptiert. Wenn andererseits die Zahl gerade, aber keine Zweierpotenz ist (nur bei Binärzahlen), müssen wir die Zahl durch 2 teilen, bis wir eine ungerade Zahl erhalten, und dann können wir die minimale Anzahl von Zuständen durch finden Addiere die ungerade erzeugte Zahl und die Häufigkeit, mit der wir durch 2 geteilt haben.

Wenn wir zum Beispiel die Mindestanzahl von Zuständen eines DFA finden müssen, der alle durch 20 teilbaren Binärzahlen akzeptiert, tun wir Folgendes:

20/2 = 10 
10/2 = 5

Daher lautet unsere Antwort 5 + 1 + 1 = 7. (Die 1 + 1, weil wir die Zahl 20 zweimal geteilt haben).

Question 4

Sie können DFA mithilfe einfacher modularer Arithmetik erstellen. Wir können weine Folge von k-ary-Zahlen anhand einer folgenden Regel interpretieren

V[0] = 0
V[i] = (S[i-1] * k) + to_number(str[i])

V[|w|]ist eine Zahl, wdie darstellt. Wenn Sie diese Regel ändern, um sie zu finden w mod N, wird die Regel zu dieser.

V[0] = 0
V[i] = ((S[i-1] * k) + to_number(str[i])) mod N

und jedes V[i]ist eine von einer Zahl von 0 bis N-1, die jedem Zustand in DFA entspricht. Wir können dies als Zustandsübergang verwenden.

Siehe ein Beispiel.

k = 2, N = 5

| V | (V*2 + 0) mod 5     | (V*2 + 1) mod 5     |
+---+---------------------+---------------------+
| 0 | (0*2 + 0) mod 5 = 0 | (0*2 + 1) mod 5 = 1 |
| 1 | (1*2 + 0) mod 5 = 2 | (1*2 + 1) mod 5 = 3 |
| 2 | (2*2 + 0) mod 5 = 4 | (2*2 + 1) mod 5 = 0 |
| 3 | (3*2 + 0) mod 5 = 1 | (3*2 + 1) mod 5 = 2 |
| 4 | (4*2 + 0) mod 5 = 3 | (4*2 + 1) mod 5 = 4 |

k = 3, N = 5

| V | 0 | 1 | 2 |
+---+---+---+---+
| 0 | 0 | 1 | 2 |
| 1 | 3 | 4 | 0 |
| 2 | 1 | 2 | 3 |
| 3 | 4 | 0 | 1 |
| 4 | 2 | 3 | 4 |

Jetzt können Sie ein sehr einfaches Muster sehen. Sie können tatsächlich einen DFA-Übergang erstellen, indem Sie einfach sich wiederholende Zahlen von links nach rechts, von oben nach unten, von 0 nach N-1 schreiben.

Answer 1

74

Ich muss lernen, wie man einen DFA so entwirft, dass er bei einer beliebigen Zahl 'n' binäre Zeichenfolgen {0, 1} akzeptiert, deren dezimale Äquivalentzahl durch 'n' teilbar ist.

Es wird verschiedene DFAs für verschiedene 'n' geben, aber kann jemand einen grundlegenden Ansatz nennen, dem ich folgen sollte, um mit einer beliebigen Zahl 0 <n <10 fortzufahren.

regex automata dfa Naveen
quelle

denn selbst ndas ist trivial, oder?

Akonsu

1

Verzeihung @akonsu Ich habe das nicht verstanden.

Naveen

Verwenden Sie hierfür keine regulären Ausdrücke. Analysieren Sie einfach den String mod n.

Raymond Chen

@Naveen Ich meine, eine durch eine gerade teilbare Binärzeichenfolge nmuss log(n)nachgestellte Nullen haben.

Akonsu

@akonsu okay, und was ist mit Primzahlen unter 10.

Naveen

Answer 2

denn selbst ndas ist trivial, oder?

Akonsu

Answer 3

1

Verzeihung @akonsu Ich habe das nicht verstanden.

Naveen

Answer 4

Verwenden Sie hierfür keine regulären Ausdrücke. Analysieren Sie einfach den String mod n.

Raymond Chen

Answer 5

@Naveen Ich meine, eine durch eine gerade teilbare Binärzeichenfolge nmuss log(n)nachgestellte Nullen haben.

Akonsu

Answer 6

@akonsu okay, und was ist mit Primzahlen unter 10.

Naveen

Answer 7

Im Folgenden habe ich eine Antwort für ngleich 5 geschrieben, aber Sie können denselben Ansatz anwenden, um DFAs für jeden Wert nund jedes Positionsnummernsystem zu zeichnen , z. B. binär, ternär ...

Zuerst den Begriff 'Vollständiger DFA' verwenden. Ein DFA , der für die vollständige Domäne in δ: Q × Σ → Q definiert ist, wird als 'Vollständiger DFA' bezeichnet. Mit anderen Worten können wir sagen; Im Übergangsdiagramm des vollständigen DFA fehlt keine Kante (z. B. ist von jedem Zustand in Q für jedes Sprachsymbol in Σ eine ausgehende Kante vorhanden). Hinweis: Manchmal definieren wir partielle DFA als δ ⊆ Q × Σ → Q (Lesen: Wie liest „δ: Q × Σ → Q“ in der Definition einer DFA ).

Design DFA akzeptiert Binärzahlen, die durch die Zahl 'n' teilbar sind:

Schritt 1 : Wenn Sie eine Zahl ω durch dividieren, nkann die Erinnerung entweder 0, 1, ..., (n - 2) oder (n - 1) sein. Wenn der Rest ist 0, bedeutet dies, dass ω durch nsonst nicht teilbar ist . In meinem DFA gibt es also einen Zustand q _r , der einem Restwert entspricht r, wobei 0 <= r <= (n - 1)und die Gesamtzahl der Zustände in DFA ist n.
Nach der Verarbeitung einer Zahlenfolge ω über Σ impliziert der Endzustand q _r , dass ω% n => r (% Erinnerungsoperator).

In allen Automaten ist der Zweck eines Zustands wie ein Speicherelement. Ein Zustand in einem Atomata speichert einige Informationen wie den Schalter des Lüfters, die erkennen können, ob sich der Lüfter im Zustand "Aus" oder "Ein" befindet. Für n = 5 entsprechen fünf Zustände in DFA fünf Erinnerungsinformationen wie folgt:

Zustand q ₀ erreicht, wenn Erinnerung 0 ist. Zustand q ₀ ist der Endzustand (akzeptierender Zustand). Es ist auch ein Ausgangszustand.
Der Zustand q ₁ erreicht, wenn die Erinnerung 1 ist, einen nicht endgültigen Zustand.
Zustand q _2, wenn Erinnerung 2 ist, ein nicht endgültiger Zustand.
Zustand q _3, wenn Erinnerung 3 ist, ein nicht endgültiger Zustand.
Zustand q _4, wenn Erinnerung 4 ist, ein nicht endgültiger Zustand.

Unter Verwendung der obigen Informationen können wir mit dem Zeichnen des Übergangsdiagramms TD von fünf Zuständen wie folgt beginnen:

Abbildung 1

Also 5 Zustände für 5 Restwerte. Nach der Verarbeitung einer Zeichenfolge ω, wenn der Endzustand zu q _{0 wird} , bedeutet dies, dass das Dezimaläquivalent der Eingabezeichenfolge durch 5 teilbar ist. In der obigen Abbildung ist q ₀ als Endzustand als zwei konzentrische Kreise markiert.
Zusätzlich habe ich eine Übergangsregel δ definiert: (q ₀ , 0) → q ₀ als Selbstschleife für das Symbol '0'im Zustand q ₀ , weil das Dezimaläquivalent einer Zeichenfolge nur aus '0'0 besteht und 0 durch teilbar ist n.

Schritt 2 : TD oben ist unvollständig; und kann nur Strings von '0's verarbeiten. Fügen Sie nun einige weitere Kanten hinzu, damit die Zeichenfolgen der nachfolgenden Zahlen verarbeitet werden können. Die folgende Tabelle zeigt neue Übergangsregeln, die im nächsten Schritt hinzugefügt werden können:

┌───────────────────────────────────────┐
│ Zahl │ Binär │ Rest (% 5) │ Endzustand │
├───────────────────────────────────────┤
│Ein │1 │1 │q ₁        │
├───────────────────────────────────────┤
WoZwei │10 │2 │q ₂        │
├───────────────────────────────────────┤
HreDrei │11 │3 │q ₃        │
├───────────────────────────────────────┤
OurVier │100 │4 │q ₄        │
└───────────────────────────────────────┘

Um eine binäre Zeichenfolge '1'zu verarbeiten, sollte es eine Übergangsregel δ geben: (q ₀ , 1) → q ₁
Zwei: - Die binäre Darstellung ist '10', der Endzustand sollte q _{2 sein} , und um zu verarbeiten '10', müssen wir nur eine weitere Übergangsregel hinzufügen δ: (q ₁ , 0) → q ₂
Pfad : → (q ₀ ) ─1 → ( q ₁ ) ─0 → (q ₂ )
Drei: - Binär ist der Endzustand '11'q ₃ , und wir müssen eine Übergangsregel δ hinzufügen: (q ₁ , 1) → q ₃
Pfad : → (q ₀ ) ─1 → (q ₁ ) ─1 → (q ₃ )
Viertens: - Im Binärzustand '100'ist der Endzustand q ₄ . TD verarbeitet bereits die Präfixzeichenfolge '10'und wir müssen nur eine neue Übergangsregel δ hinzufügen: (q ₂ , 0) → q ₄
Pfad : → (q ₀ ) ─ 1 → (q ₁ ) ─ 0 → (q ₂ ) ─ 0 → (q ₄ )

Figur 2

Schritt 3 : Fünf = 101 Das
obige Übergangsdiagramm in Abbildung 2 ist noch unvollständig und es fehlen viele Kanten. Für ein Beispiel ist kein Übergang für δ definiert: (q ₂ , 1) - ? . Und die Regel sollte vorhanden sein, um Strings wie zu verarbeiten '101'.
Weil '101'= 5 durch 5 teilbar ist, und um zu akzeptieren '101', füge ich δ hinzu: (q ₂ , 1) → q ₀ in der obigen Abbildung-2.
Pfad: → (q ₀ ) ─1 → (q ₁ ) ─0 → (q ₂ ) ─1 → (q ₀ )
Mit dieser neuen Regel wird das Übergangsdiagramm wie folgt:

Figur 3

Unten in jedem Schritt wähle ich die nächste nachfolgende Binärzahl aus, um eine fehlende Kante hinzuzufügen, bis ich TD als 'vollständigen DFA' erhalte.

Schritt 4 : Sechs = 110.

Wir können '11'TD in Abbildung 3 wie folgt verarbeiten : → (q ₀ ) ─11 → (q ₃ ) ─0 → ( ? ). Da 6% 5 = 1 ist, bedeutet dies, eine Regel δ hinzuzufügen: (q ₃ , 0) → q ₁ .

Figur 4

Schritt 5 : Sieben = 111

┌─────────────────────────────────────────────────── ─┬────────────┐
│ Zahl │ Binär │ Rest (% 5) │ Endzustand │ Pfad        │ Hinzufügen        │
├─────────────────────────────────────────────────── ─┼────────────┤
│Seven │111 │7% 5 = 2 │q ₂        │ q ₀ ─ 11 → q ₃   │ q ₃ ─ 1 → q ₂     │
└─────────────────────────────────────────────────── ─┴────────────┘

Abbildung 5

Schritt 6 : Acht = 1000

┌─────────────────────────────────────────────────┬ ─────────┐
│ Zahl │ Binär │ Rest (% 5) │ Endzustand │ Pfad      │ Hinzufügen      │
├─────────────────────────────────────────────────┼ ─────────┤
Ight Acht %1000 │8% 5 = 3 │q ₃        │q ₀ ─100 → q ₄ │ q ₄ ─0 → q ₃   │
└─────────────────────────────────────────────────┴ ─────────┘

Abbildung 6

Schritt 7 : Neun = 1001

┌─────────────────────────────────────────────────┬ ─────────┐
│ Zahl │ Binär │ Rest (% 5) │ Endzustand │ Pfad      │ Hinzufügen      │
├─────────────────────────────────────────────────┼ ─────────┤
│Nein │1001 │9% 5 = 4 │q ₄        │q ₀ ─100 → q ₄ │ q ₄ ─1 → q ₄   │
└─────────────────────────────────────────────────┴ ─────────┘

Abbildung 7

In TD-7 beträgt die Gesamtzahl der Kanten 10 == Q × Σ = 5 × 2. Und es ist ein vollständiger DFA, der alle möglichen binären Zeichenfolgen akzeptieren kann, deren Dezimaläquivalent durch 5 teilbar ist.

Design DFA akzeptiert ternäre Zahlen, die durch die Zahl n teilbar sind:

Schritt-1 Verwenden Sie genau wie für binär Abbildung-1.

Schritt 2 Fügen Sie Null, Eins, Zwei hinzu

┌────────────────────────────────────────────────── ─────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │    Hinzufügen         │
├────────────────────────────────────────────────── ─────┤
EroZero │0 │0 │q0 │ δ: (q0,0) → q0 │
├────────────────────────────────────────────────── ─────┤
NeEin │1 │1 │q1 │ δ: (q0,1) → q1 │
├────────────────────────────────────────────────── ─────┤
WoZwei │2 │2 │q2 │ δ: (q0,2) → q3 │
└────────────────────────────────────────────────── ─────┘

Abbildung 8

Schritt 3 Fügen Sie drei, vier, fünf hinzu

┌────────────────────────────────────────────────── ────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │   Hinzufügen         │
├────────────────────────────────────────────────── ────┤
HreDrei │10 │3 │q3 │ δ: (q1,0) → q3 │
├────────────────────────────────────────────────── ────┤
OurVier │11 │4 │q4 │ δ: (q1,1) → q4 │
├────────────────────────────────────────────────── ────┤
IveFive │12 │0 │q0 │ δ: (q1,2) → q0 │
└────────────────────────────────────────────────── ────┘

Abbildung 9

Schritt 4 Fügen Sie sechs, sieben, acht hinzu

┌────────────────────────────────────────────────── ────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │   Hinzufügen         │
├────────────────────────────────────────────────── ────┤
│Six │20 │1 │q1 │ δ: (q2,0) → q1 │
├────────────────────────────────────────────────── ────┤
│Seven │21 │2 │q2 │ δ: (q2,1) → q2 │
├────────────────────────────────────────────────── ────┤
│ Acht │22 │3 │q3 │ δ: (q2,2) → q3 │
└────────────────────────────────────────────────── ────┘

Abbildung 10

Schritt 5 Fügen Sie neun, zehn, elf hinzu

┌────────────────────────────────────────────────── ────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │   Hinzufügen         │
├────────────────────────────────────────────────── ────┤
IneNein │100 │4 │q4 │ δ: (q3,0) → q4 │
├────────────────────────────────────────────────── ────┤
│Ten │101 │0 │q0 │ δ: (q3,1) → q0 │
├────────────────────────────────────────────────── ────┤
LeEleven │102 │1 │q1 │ δ: (q3,2) → q1 │
└────────────────────────────────────────────────── ────┘

Abbildung 11

Schritt 6 Addiere zwölf, dreizehn, vierzehn

┌─────────────────────────────────────────────────── ─────┐
│ Dezimal │ Ternär │ Rest (% 5) │ Endzustand │   Hinzufügen         │
├─────────────────────────────────────────────────── ─────┤
Zwölf wel110 │2 │q2 │ δ: (q4,0) → q2 │
├─────────────────────────────────────────────────── ─────┤
│Dreißig│111 │3 │q3 │ δ: (q4,1) → q3 │
├─────────────────────────────────────────────────── ─────┤
Our Vierzehn│112 │4 │q4 │ δ: (q4,2) → q4 │
└─────────────────────────────────────────────────── ─────┘

Abbildung 12

Die Gesamtzahl der Kanten im Übergangsdiagramm in Abbildung 12 beträgt 15 = Q × Σ = 5 * 3 (ein vollständiger DFA). Und dieser DFA kann akzeptieren, dass alle Zeichenfolgen über {0, 1, 2} bestehen. Diese Dezimaläquivalente sind durch 5 teilbar.
Wenn Sie bei jedem Schritt feststellen, gibt es in der Tabelle drei Einträge, da ich bei jedem Schritt alle möglichen ausgehenden Flanken aus einem Zustand hinzufüge um einen vollständigen DFA zu erstellen (und ich füge eine Kante hinzu, damit q _r state für den Rest erhalten wird r)!

Denken Sie daran, dass die Vereinigung zweier regulärer Sprachen ebenfalls eine reguläre ist. Wenn Sie einen DFA entwerfen müssen, der binäre Zeichenfolgen akzeptiert, ist dieses Dezimaläquivalent entweder durch 3 oder 5 teilbar. Zeichnen Sie dann zwei separate DFAs für teilbar durch 3 und 5, und vereinigen Sie dann beide DFAs, um das Ziel-DFA zu erstellen (für 1 <= n <= 10) Sie müssen 10 DFAs vereinen).

Wenn Sie aufgefordert werden, DFA zu zeichnen, das binäre Zeichenfolgen so akzeptiert, dass das Dezimaläquivalent durch 5 und 3 teilbar ist, suchen Sie nach DFA, das durch 15 teilbar ist (aber was ist mit 6 und 8?).

Hinweis: Mit dieser Technik gezeichnete DFAs werden nur dann minimiert, wenn es keinen gemeinsamen Faktor zwischen Zahl nund Basis gibt, z. B. gibt es im ersten Beispiel keinen zwischen 5 und 2 oder im zweiten Beispiel zwischen 5 und 3, daher werden beide oben konstruierten DFAs minimiert DFAs. Wenn Sie mehr über mögliche Mini-Zustände für Zahlen nund Basis blesen möchten, lesen Sie das Papier: Teilbarkeit und Zustandskomplexität .

^{Unten habe ich ein Python-Skript hinzugefügt. Ich habe es zum Spaß geschrieben, während ich die Python-Bibliothek pygraphviz gelernt habe. Ich füge es hinzu. Ich hoffe, es kann irgendwie für jemanden hilfreich sein.}

Entwerfen Sie den DFA für die durch die Zahl 'n' teilbaren Zeichenfolgen der Basis 'b':

Wir können also den obigen Trick anwenden, um DFA zu zeichnen, um Zahlenfolgen in jeder Basis zu erkennen, 'b'die durch eine bestimmte Zahl teilbar sind 'n'. In diesem DFA ist die Gesamtzahl der Zustände n(für nReste) und die Anzahl der Kanten sollte gleich 'b' * 'n' sein - das ist vollständig. DFA: 'b' = Anzahl der Symbole in der Sprache des DFA und 'n' = Anzahl der Staaten.

Mit dem obigen Trick habe ich unten ein Python-Skript geschrieben, um DFA für die Eingabe baseund zu zeichnen number. Im Skript divided_by_Nfüllt die Funktion die Übergangsregeln von DFA base * numberschrittweise aus. In jeder Schrittnummer konvertiere ich mit der Funktion numin eine Zahlenfolge . Um zu vermeiden, dass jede Zahlenfolge verarbeitet wird, habe ich eine temporäre Datenstruktur verwendet . In jedem Schritt wird der Endzustand für die Zahlenzeichenfolge ausgewertet und gespeichert , um im nächsten Schritt verwendet zu werden.num_sbaseN()lookup_tablenum_slookup_table

Für den Übergangsgraphen von DFA habe ich eine Funktion draw_transition_graphmit der Pygraphviz-Bibliothek geschrieben (sehr einfach zu bedienen). Um dieses Skript verwenden zu können, müssen Sie es installieren graphviz. Um dem Übergangsdiagramm farbige Kanten hinzuzufügen, generiere ich zufällig Farbcodes für jede Symbolfunktion 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)

Führ es aus:

~/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

Ausgabe:

DFA akzeptiert Zahlenfolgen in Basis 4, die durch 5 teilbar sind

In ähnlicher Weise geben Sie base = 4 und number = 7 ein, um zu generieren - dfa akzeptiert Zahlenzeichenfolge in base '4', die durch '7' teilbar sind.
Versuchen Sie, filenamezu .pngoder zu wechseln .jpeg.

_{Verweist auf
diejenigen, die ich zum Schreiben dieses Skripts verwende: ➊ Funktion baseNvon "Ganzzahl in eine Zeichenfolge in einer bestimmten numerischen Basis in Python

konvertieren " ➋ So installieren Sie "pygraphviz": "Python sieht pygraphviz nicht"

➌ So lernen Sie die Verwendung von Pygraphviz: "Python- FSM "

➍ So generieren Sie zufällige Hex-Farbcodes für jedes Sprachsymbol: " Wie würde ich einen zufälligen Hexdigit-Code-Generator mit .join und for-Schleifen erstellen? "}

Answer 8

5

Referenzierten hier in der Überprüfung , ob eine Zahl ist durch 9 teilbar .

Trashgod

Answer 9

1

Um eine alternative Perspektive zu erhalten, könnte man modulare Arithmetik lesen.

Bitte helfen Sie

Answer 10

4

Wie kann man diese Lösung beweisen?

Tim Hsu

Answer 11

1

Ich habe mich auch gefragt, ob jemand Verweise auf Ressourcen liefern kann, die einen Beweis liefern.

Juzer Ali

Answer 12

@JuzerAli das ist mein eigener Trick, du wirst in keinem Buch eine Erklärung finden.

Grijesh Chauhan

Answer 13

Ich weiß, dass ich ziemlich spät dran bin, aber ich wollte der bereits korrekten Antwort von @Grijesh nur ein paar Dinge hinzufügen. Ich möchte nur darauf hinweisen, dass die Antwort von @Grijesh nicht den minimalen DFA ergibt. Während die Antwort sicherlich der richtige Weg ist, um einen DFA zu erhalten, müssen Sie, wenn Sie den minimalen DFA benötigen, in Ihren Divisor schauen.

Wie zum Beispiel bei Binärzahlen beträgt die Mindestanzahl der erforderlichen Zustände n + 1, wenn der Divisor eine Potenz von 2 (dh 2 ^ n) ist. Wie würden Sie einen solchen Automaten entwerfen? Sehen Sie sich nur die Eigenschaften von Binärzahlen an. Für eine Zahl, sagen wir 8 (das ist 2 ^ 3), haben alle ihre Vielfachen die letzten 3 Bits als 0. Zum Beispiel ist 40 in binär 101000. Damit eine Sprache eine durch 8 teilbare Zahl akzeptiert, brauchen wir nur eine Automat, der sieht, ob die letzten 3 Bits 0 sind, was wir in nur 4 Zuständen anstelle von 8 Zuständen tun können. Das ist die halbe Komplexität der Maschine.

Tatsächlich kann dies auf jede Basis erweitert werden. Wenn wir für ein ternäres Basisnummernsystem beispielsweise einen Automaten für die Teilbarkeit mit 9 entwerfen müssen, müssen wir nur sehen, ob die letzten 2 Zahlen der Eingabe 0 sind. Dies kann wiederum in nur 3 Zuständen erfolgen.

Wenn der Divisor nicht so besonders ist, müssen wir nur die Antwort von @ Grijesh durchgehen. Wie zum Beispiel in einem binären System, wenn wir die Teiler von 3 oder 7 oder vielleicht 21 nehmen, müssen wir nur so viele Zustände haben. Für jede ungerade Zahl n in einem Binärsystem benötigen wir n Zustände, um die Sprache zu definieren, die alle Vielfachen von n akzeptiert. Wenn andererseits die Zahl gerade, aber keine Zweierpotenz ist (nur bei Binärzahlen), müssen wir die Zahl durch 2 teilen, bis wir eine ungerade Zahl erhalten, und dann können wir die minimale Anzahl von Zuständen durch finden Addiere die ungerade erzeugte Zahl und die Häufigkeit, mit der wir durch 2 geteilt haben.

Wenn wir zum Beispiel die Mindestanzahl von Zuständen eines DFA finden müssen, der alle durch 20 teilbaren Binärzahlen akzeptiert, tun wir Folgendes:

20/2 = 10 
10/2 = 5

Daher lautet unsere Antwort 5 + 1 + 1 = 7. (Die 1 + 1, weil wir die Zahl 20 zweimal geteilt haben).

Answer 14

Sir, im letzten Beispiel zur Teilbarkeit durch 20, was ist, wenn die Frage nach einem Rest K anstelle von Rest 0 fragt, wenn durch 20 geteilt wird? Würde sich die Antwort ändern?

Vinay Yadav

Answer 15

Sie können DFA mithilfe einfacher modularer Arithmetik erstellen. Wir können weine Folge von k-ary-Zahlen anhand einer folgenden Regel interpretieren

V[0] = 0
V[i] = (S[i-1] * k) + to_number(str[i])

V[|w|]ist eine Zahl, wdie darstellt. Wenn Sie diese Regel ändern, um sie zu finden w mod N, wird die Regel zu dieser.

V[0] = 0
V[i] = ((S[i-1] * k) + to_number(str[i])) mod N

und jedes V[i]ist eine von einer Zahl von 0 bis N-1, die jedem Zustand in DFA entspricht. Wir können dies als Zustandsübergang verwenden.

Siehe ein Beispiel.

k = 2, N = 5

| V | (V*2 + 0) mod 5     | (V*2 + 1) mod 5     |
+---+---------------------+---------------------+
| 0 | (0*2 + 0) mod 5 = 0 | (0*2 + 1) mod 5 = 1 |
| 1 | (1*2 + 0) mod 5 = 2 | (1*2 + 1) mod 5 = 3 |
| 2 | (2*2 + 0) mod 5 = 4 | (2*2 + 1) mod 5 = 0 |
| 3 | (3*2 + 0) mod 5 = 1 | (3*2 + 1) mod 5 = 2 |
| 4 | (4*2 + 0) mod 5 = 3 | (4*2 + 1) mod 5 = 4 |

k = 3, N = 5

| V | 0 | 1 | 2 |
+---+---+---+---+
| 0 | 0 | 1 | 2 |
| 1 | 3 | 4 | 0 |
| 2 | 1 | 2 | 3 |
| 3 | 4 | 0 | 1 |
| 4 | 2 | 3 | 4 |

Jetzt können Sie ein sehr einfaches Muster sehen. Sie können tatsächlich einen DFA-Übergang erstellen, indem Sie einfach sich wiederholende Zahlen von links nach rechts, von oben nach unten, von 0 nach N-1 schreiben.

Design-DFA akzeptiert binäre Zeichenfolgen, die durch eine Zahl 'n' teilbar sind.

Antworten:

Design DFA akzeptiert Binärzahlen, die durch die Zahl 'n' teilbar sind:

Design DFA akzeptiert ternäre Zahlen, die durch die Zahl n teilbar sind:

Entwerfen Sie den DFA für die durch die Zahl 'n' teilbaren Zeichenfolgen der Basis 'b':