Diese Finite-State-Maschine (FSM) akzeptiert binäre Zahlen, die durch drei teilbar sind. In der Theorie sind die Zustände gleich dem Wert n mod 3, aber wie funktioniert das für Binärzahlen Was ich nicht bekomme, ist, wie die Übergänge zusammenkommen, weil ein neuer Eingang 0 oder 1 nicht bedeutet, dass eine feste Zahl nur dem Gesamtbild hinzugefügt wird N. Können Sie mir bitte helfen zu verstehen, dass Danke im Voraus die Zustände A, B und C den Eingängen entsprechen, die zu 0,1 und 2 Mod 3 kongruent sind. Angenommen, der Eingang stellt bisher ein Vielfaches von 3 dar, so dass du im Zustand A bist. A 0 multipliziert die aktuelle Zahl mit 2, also ist es noch ein Vielfaches von 3 und du bist immer noch in Zustand A. A 1 multipliziert es mit 2 und Fügt 1 hinzu und macht es kongruent zu 1 mod 3 und setzt dich in den Zustand B. Wenn die aktuelle Zahl kongruent zu 1 mod 3 ist, bist du in Zustand B. Ein Eingang von 0 verdoppelt die Zahl, so dass es kongruent zu 2 mod 3 und nehmen Sie geben an C. Eine Eingabe von 1, auf der anderen Seite, verdoppelt die Zahl, macht es kongruent zu 2 mod 3, und fügt dann 1, so dass es ein Vielfaches von 3 und sendet Sie an Staat A. In der gleichen Weise Sie Kann analysieren, was passiert, wenn die aktuelle Zahl kongruent zu 2 mod 3 ist und youre im Zustand C: Verdoppelung der Zahl macht es kongruent zu 4 und damit zu 1 mod 3 und bewegt dich zu B und verdoppelt es und das Hinzufügen eines lässt Sie herein Zustand C. So sind die drei Zustände wirklich richtig verbunden. All dies kocht auf das, was ich sehe Ted hat in seiner Antwort gegeben: Wenn man ein bisschen b liest, verwandelt man die aktuelle Nummer eins nach links, die es mit 2 multipliziert, und dann fügt man hinzu, dass die FSM den Effekt nachahmt Von dieser Operation auf den Rückstand der Zahl mod 3. beantwortet 3. Mai 12 um 7:14 Hier ist ein weiterer, mehr pedantisch, Ansatz: Lassen Sie die Zahl n Summe dk 2k. Definiere rk 2k bmod 3 und bemerke, dass rk2, wenn k ungerade ist, und rk 1, wenn k gerade ist. Also n bmod 3 sum dk rk bmod 3.Dies ist der Schlüssel zum Erstellen eines Zustandsdiagramms mit den Binärziffern d0. D als Eingänge Um die Summe zu berechnen, muss man die vorhandene Summe (Modulo 3 natürlich) verfolgen und ob der Index ungerade oder gerade ist (um den Wert von rk zu kennen). So ist der Zustand Raum mal. Es ist einfach, das Zustandsdiagramm mit akzeptierenden Zuständen (0, ungerade) und (0, gerade) zu erstellen. Beginne mathbb amp mathbb, dk0 ampmathbb, dk1 hline (0, ungerade) amp (0, gerade) amp (1, gerade) (0, gerade) amp (0, ungerade) amp (2, ungerade) (1, ungerade) amp (1, ungerade) amp (1, ungerade) amp (1, ungerade) amp (0, ungerade) (2, ungerade) amp (2, gerade) Amp (2, ungerade) amp (1, ungerade) Ende Der Fang ist, dass es 6 Zustände gibt, nicht 3 wie im Diagramm oben. Wenn wir jedoch den FSM-Tabellenfüllungsalgorithmus anwenden (zB siehe Hopcroft, Motwani, Ullman, Einführung in die Automaten-Theorie, Sprachen und Berechnungen), um ununterscheidbare Zustände zu finden, finden wir die folgenden Paare nicht unterscheidbar: Die daraus resultierende FSM ist identisch mit der FSM oben, mit der Zustandskennung A sim, B sim und C sim. Antwortete 3. Mai 12 um 20:06 Isn39t dies das Gegenteil rk1 wenn k ist sogar. Und rk 2, wenn k ungerade ist. (ZB k1: rk (21 mod 3) 2 während k2: rk (22 mod 3) 1) ndash Dor Sep 25 15 um 17:32 Dor: Vielen Dank für das Fangen dieses ndash copper. hat Sep 25 15 um 17:50 Deine Antwort 2017 Stack Exchange, IncIm Arbeit an einem Problem für eine Klasse gesetzt, und dachte an eine Frage im Zusammenhang mit dem, was ich arbeitete. Gibt es eine minimale Anzahl von Zuständen, die ein endlicher Automaten haben muss, um binäre Strings zu akzeptieren, die Zahlen darstellen, die durch eine ganze Zahl n teilbar sind. In einem früheren Problemsatz war ich in der Lage, eine DFA zu konstruieren, die binäre Strings, die durch 3 mit 3 Zuständen teilbar sind, akzeptierte . Ist das ein Zufall, oder gibt es etwas, das dem allgemeinen Problem der Erkennung von Strings unterteilt ist, die durch n, die eine minimale Anzahl von Staaten, die ich verspreche, dass dies nicht beantworten eine Hausaufgabe Frage für mich. ) Gefragt Jan 29 12 bei 0:35 HuckBennett Ich stimme mit Kaveh, dass diese Frage auf cstheory geschlossen werden sollte, meist um konsistent zu sein. Allerdings bin ich auch mit dir einverstanden: das ist eine lustige Frage und wenn du zum ersten Mal DFAs siehst, ist es definitiv eins, dass du dich selbst fragen solltest. Ich denke, das OP sollte versuchen, etwas Spaß zu haben, die Antwort für sich selbst auszuprobieren und dann math. SE für mehr Info zu konsultieren. Ndash Artem Kaznatcheev 9830 Jan 29 12 at 6:10 Dies ist keine Hausaufgabe (obwohl es von einer Hausaufgabe inspiriert ist), es ist eine interessante Frage, ich glaube, es ist ein bekanntes Ergebnis und die Antwort auf die Frage erschien in einer Forschungszeitschrift. Ich sehe nicht, warum es geschlossen sein sollte. Die obere Grenze war Hausaufgaben, und ist in der Tat einfach, aber die Frage war über die untere Grenze. Ndash Peter Shor Jan 29 12 at 13: 43 Ich studiere regelmäßige Ausdrücke und fand ein interessantes Übungsproblem online, das das Schreiben eines regulären Ausdrucks beinhaltet, um alle Binärzahlen zu erkennen, die durch 3 (und nur solche Zahlen) teilbar sind. Um ehrlich zu sein, bat das Problem, eine DFA für ein solches Szenario zu konstruieren, aber ich dachte, dass es gleichermaßen möglich sein sollte, mit regulären Ausdrücken zu arbeiten. Ich weiß, dass Theres eine kleine Regel an Ort und Stelle, um herauszufinden, ob eine binäre Zahl durch 3 teilbar ist: nehmen Sie die Anzahl der Eins an sogar Stellen in der Ziffer und subtrahieren durch die Anzahl der Eins an ungeraden Stellen in der Ziffer - wenn dies gleich Null ist , Die Zahl ist durch 3 teilbar (Beispiel: 110 - 1 im geraden 2 Slot und 1 im ungeraden 1 Slot). Allerdings habe ich einige Schwierigkeiten, diese an einen regulären Ausdruck anzupassen. Die nächste Ive kommen, ist zu erkennen, dass die Zahl 0 sein kann, also wäre das der erste Zustand. Ich habe auch gesehen, dass alle Binärzahlen, die durch 3 teilbar sind, mit 1 beginnen, also wäre das der zweite Zustand, aber ich bin von dort stecken. Könnte jemand helfen, gefragt Mar 11 13 um 1:50 Nach dem, was Oli Charlesworth sagt, können Sie DFA für die Teilbarkeit der Basis-B-Nummer durch einen bestimmten Divisor d bauen. Wo die Staaten im DFA den Rest der Division darstellen. Für Ihren Fall (Basis 2 - Binärzahl, Divisor d 3 10): Beachten Sie, dass die DFA oben akzeptiert leere Zeichenfolge als Zahl teilbar durch 3. Dies kann leicht durch Hinzufügen eines weiteren Zwischenzustandes vorne: Umwandlung in theoretischen regulären Ausdruck behoben werden Kann mit dem normalen Prozess durchgeführt werden. Umwandlung in praktische Regex in Aromen, die rekursive Regex unterstützt kann leicht gemacht werden, wenn Sie die DFA haben. Dies ist für den Fall von (Basis b 10, d 7 10) in dieser Frage von CodeGolf. SE gezeigt. Breaking it down, können Sie sehen, wie es gebaut wird. Die Atomgruppierung (oder eine nicht rückläufige Gruppe oder eine Gruppe, die sich besitzergreifend verhält) wird verwendet, um sicherzustellen, dass nur die leere Zeichenfolgen-Alternative übereinstimmt. Dies ist ein Trick zu emulieren (DEFINE) in Perl. Dann entsprechen die Gruppen A bis G dem Rest von 0 bis 6, wenn die Nummer durch 7 geteilt wird. Antwort von Mar 11 13 um 6:44 Ich habe einen anderen Weg zu diesem Problem und ich denke das ist einfacher zu verstehen. Wenn wir eine Zahl um 3 teilen, können wir drei Reste haben: 0,1,2. Wir können eine Zahl beschreiben, die durch 3 mit dem Ausdruck 3t teilbar ist (t ist eine natürliche Zahl). Wenn wir nach einer Binärzahl 0 addieren, deren Rest 0 ist, wird die aktuelle Dezimalzahl verdoppelt. Denn jede Ziffer bewegt sich in eine höhere Position. 3t 2 6t, das ist auch durch 3 teilbar. Wenn wir eine 1 nach einer Binärzahl addieren, deren Rest 0 ist, wird die tatsächliche Dezimalzahl verdoppelt plus 1. Weil jede Ziffer in eine höhere Position bewegt wird, gefolgt von einem 1 3t 2 1. Der Rest ist 1. Wenn wir eine 1 nach einer Binärzahl addieren, deren Rest 1 ist. Die tatsächliche Dezimalzahl wird plus eins verdoppelt, und der Rest ist 0 (3t 1) 2 1 6t 3 ist dies durch teilbar 3. Wenn wir eine 0 nach einer Binärzahl addieren, deren Rest 1 ist. Die tatsächliche Dezimalzahl wird verdoppelt. Und der Rest wird 2 (3t 1) 2 6t 2. Wenn wir eine 0 nach einer Binärzahl hinzufügen, deren Rest ist 2. Der Rest wird 1. (3t 2) 2 3t 4 3 (2t 1) 1 Wenn wir eine 1 nach einer Binärzahl addieren, deren Rest 2 ist, dann bleibt der Rest 2. (3t 2) 2 1 t 5 3 (2t 1) 2. Egal wieviel 1 du zu einer Binärzahl addierst, deren Rest 2 ist, wird der Rest 2 für immer sein. (3 (t 1) 2) 2 1 3 (t 2) 5 3 (t 3) 2 beantwortet 6. November 15 um 20:45 Binäre Zahlen teilbar durch 3 fallen in 3 Kategorien: Zahlen mit zwei aufeinanderfolgenden 1s oder zwei 1s getrennt durch Eine gerade Anzahl von 0s. Effektiv hebt sich jedes Paar aus. (Z. B. 11, 110, 1100,1001,10010, 1111) (dezimal: 3, 6, 12, 9, 18, 15) Zahlen mit drei 1s, jeweils getrennt durch eine ungerade Anzahl von 0s. Diese Drillinge brechen sich auch aus. (Z. B. 10101, 101010, 1010001, 1000101) (dezimal: 21, 42, 81, 69) Eine Kombination der ersten beiden Regeln (auch ineinander) (ex 1010111, 1110101, 1011100110001) (dezimal: 87, 117 , 5937) Also ein regulärer Ausdruck, der diese drei Regeln berücksichtigt, ist einfach: bedeutet, dass die vorherige Zahlgruppe optional ist, gibt eine Auswahl von Optionen auf beiden Seiten innerhalb der Klammern an. Below, ich habe eine Antwort für n gleich 5 geschrieben, aber du kannst dich bewerben Gleicher Ansatz, um DFAs für jeden Wert von n und jedes Positionsnummernsystem zu zeichnen, zB binär, ternär. Zuerst lehnen Sie den Begriff Complete DFA, A DFA definiert auf komplette Domain in: Q Q heißt Complete DFA. Mit anderen Worten, wir können im Übergangsdiagramm der vollständigen DFA sagen, dass es keine fehlende Flanke gibt (z. B. aus jedem Zustand in Q gibt es eine ausgehende Flanke, die für jedes Sprachsymbol vorhanden ist). Anmerkung: Irgendwann definieren wir partielle DFA als Q Q (Lesen: Wie lautet: Q Q in der Definition eines DFA einlesen). Design DFA akzeptiert Binärzahlen, dividierbar nach Nummer n: Schritt 1. Wenn Sie eine Zahl durch n teilen, dann kann die Erinnerung entweder 0, 1. (n - 2) oder (n - 1) sein. Wenn der Rest 0 ist, bedeutet das, dass er durch n nicht teilbar ist. Also, in meinem DFA gibt es einen Zustand q r, der einem Restwert r entsprechen würde. Wobei 0 lt (n - 1) ist. Und die Gesamtzahl der Zustände in DFA ist n. Nach dem Bearbeiten einer Zahlenfolge über, ist der Endzustand q r impliziert, dass n r (Erinnerungsoperator). In jedem Automaten ist der Zweck eines Zustands wie Speicherelement. Ein Zustand in einer Atomata speichert einige Informationen wie Fans wechseln, die sagen können, ob der Lüfter in aus oder in auf Zustand ist. Für n 5 sind fünf Zustände in DFA, die fünf Erinnerungsinformationen entsprechen, wie folgt: Zustand q 0 erreicht, wenn die Erinnerung 0 ist. Zustand q 0 ist der Endzustand (Annahmezustand). Es ist auch ein Anfangszustand. Staat q 1 erreicht, wenn die Erinnerung 1 ist, ein Nicht-Endzustand. Staat q 2 Wenn die Erinnerung 2 ist, ist ein Nicht-Endzustand. Staat q 3 Wenn die Erinnerung 3 ist, ist ein Nicht-Endzustand. Staat q 4 wenn die Erinnerung 4 ist, ein Nicht-Endzustand. Mit Hilfe von Informationen können wir beginnen, Übergangsdiagramm TD von fünf Zuständen wie folgt zu zeichnen: Also, 5 Zustände für 5 Restwerte. Nach dem Verarbeiten eines Strings, wenn der Endzustand q 0 wird, bedeutet das Dezimaläquivalent des Eingangsstrings, der durch 5 teilbar ist. In der obigen Abbildung ist q 0 als endgültiger Zustand als zwei konzentrischer Kreis markiert. Zusätzlich habe ich eine Übergangsregel definiert: (q 0 0) q 0 als Selbstschleife für Symbol 0 im Zustand q 0. Das ist, weil dezimales Äquivalent eines Strings aus nur 0 0 ist und 0 eine durch n teilbare ist. Schritt 2 . TD oben ist unvollständig und kann nur Strings von 0 s verarbeiten. Fügen Sie jetzt noch weitere Kanten hinzu, damit es nachfolgende Zahlenstränge verarbeiten kann. Überprüfen Sie die Tabelle unten, zeigt neue Übergangsregeln, die im nächsten Schritt hinzugefügt werden können: Um den binären String 1 zu verarbeiten, sollte es eine Übergangsregel geben: (q 0. 1) q 1 Zwei: - binäre Darstellung ist 10. Endzustand sollte q 2 sein . Und zu verarbeiten 10. Wir müssen nur noch eine Übergangsregel hinzufügen: (q 1. 0) q 2 Pfad. (Q 0) 1 (q 1) 0 (q 2) Drei: - In binär ist es 11. Endzustand q 3. Und wir müssen eine Übergangsregel hinzufügen: (q 1. 1) q 3 Pfad. (Q 0) 1 (q 1) 1 (q 3) Vier: - im Binär 100. Der Endzustand ist q 4. TD verarbeitet bereits Präfix String 10 und wir müssen nur eine neue Übergangsregel hinzufügen: (q 2. 0) q 4 Pfad. (Q 0) 1 (q 1) 0 (q 2) 0 (q 4) Schritt 3 Fünf 101 Über dem Übergangsdiagramm in Abbildung 2 ist noch unvollständig und es gibt viele fehlende Kanten, für ein Beispiel ist kein Übergang definiert für: (q 2. 1) -. Und die Regel sollte vorhanden sein, um Strings wie 101 zu verarbeiten. Weil 101 5 durch 5 teilbar ist und 101 zu akzeptieren, füge ich hinzu: (q 2 1) q 0 in oben 2 - 2. Pfad: (q 0) 1 (q 1) 0 (q 2) 1 (q 0) mit dieser neuen Regel wird das Übergangsdiagramm wie folgt: In jedem Schritt sehe ich die nächste nachfolgende Binärzahl aus, um eine fehlende Kante hinzuzufügen, bis ich komme TD als komplettes DFA. Wir können 11 in der vorliegenden TD in Abbildung 3 als: (q 0) 11 (q 3) 0 () verarbeiten. Weil 6 5 1 das bedeutet, eine Regel hinzuzufügen: (q 3 0) q 1. Schritt-6 Hinzufügen Zwölf, Dreizehn, Vierzehn Gesamtzahl der Kanten im Übergangsdiagramm Abbildung 12 sind 15 Q 5 3 (eine komplette DFA). Und diese DFA kann akzeptieren, alle Strings bestehen über diese dezimale Äquivalent ist durch 5 teilbar. Wenn Sie bei jedem Schritt bemerken, in Tabelle gibt es drei Einträge, da bei jedem Schritt füge ich alle möglichen ausgehenden Kante aus einem Staat, um eine komplette DFA (und Ich füge eine Kante hinzu, so dass qr Zustand für Rest ist r) Um weitere hinzuzufügen, beachten Sie die Vereinigung von zwei regelmäßigen Sprachen sind auch regelmäßig. Wenn du ein DFA entwerfen musst, das binäre Strings akzeptiert, ist dieses dezimale Äquivalent entweder durch 3 oder 5 teilbar, dann zeichne zwei getrennte DFAs für teilbar durch 3 und 5 und dann Union beide DFAs, um Ziel DFA zu konstruieren (für 1 lt n lt 10 du hast Um 10 DFAs zu vereinigen). Wenn Sie gebeten werden, DFA zu zeichnen, die binäre Zeichenfolgen akzeptiert, so dass Dezimaläquivalent durch 5 und 3 teilbar ist, dann sind Sie auf der Suche nach DFA von teilbaren durch 15 (aber was ist mit 6 und 8). Anmerkung: DFAs, die mit dieser Technik gezeichnet werden, werden DFA nur minimiert, wenn es keinen gemeinsamen Faktor zwischen der Nummer n und der Basis gibt, z. B. Es gibt keine Zwischen 5 und 2 im ersten Beispiel oder zwischen 5 und 3 im zweiten Beispiel, daher sind beide DFAs, die oben konstruiert wurden, minimierte DFAs. Wenn Sie interessiert sind, lesen Sie weiter über mögliche Mini-Staaten für die Nummer n und Basis b lesen Papier: Teilbarkeit und State Complexity. Unten habe ich ein Python-Skript hinzugefügt, ich habe es für Spaß beim Lernen Python Bibliothek pygraphviz geschrieben. Ich füge es hinzu Ich hoffe es kann für jemanden in irgendeiner Zeit hilfreich sein. Design DFA für Basis b Nummer Strings teilbar durch Nummer n: So können wir über Trick anwenden, um DFA zu zeichnen, um Nummernstrings in jeder Basis zu erkennen, die diese eine gegebene Zahl n teilbar sind. In diesem DFA ist die Gesamtzahl der Zustände n (für n Reste) und die Anzahl der Kanten sollte gleich b n mdash sein, die vollständig ist DFA: b Anzahl der Symbole in der Sprache der DFA und n Anzahl der Zustände. Mit über Trick, unten habe ich ein Python Script geschrieben, um DFA für Eingabe Basis und Nummer zu zeichnen. Im Skript füllt die Funktion dividbyN DFAs Übergangsregeln in Basisnummernschritten. In jedem Schritt-num, konvertiere ich num in Nummer String Nums mit FunktionsbasisN (). Um die Verarbeitung jedes Ziffernstrings zu vermeiden, habe ich eine temporäre Datenstruktur aussieht. In jedem Schritt wird der Endzustand für Zahlenstring-Numer ausgewertet und im nächsten Schritt nachträglich gespeichert. Für Übergangsgraph von DFA habe ich eine Funktion Drawtransitiongraph mit Pygraphviz Bibliothek geschrieben (sehr einfach zu bedienen). Um dieses Skript zu verwenden, müssen Sie graphviz installieren. Um bunte Kanten im Übergangsdiagramm hinzuzufügen, generiere ich zufällig Farbcodes für jedes Symbol getcolordict Funktion. In ähnlicher Weise geben Sie die Basis 4 und die Nummer 7 ein, um - dfa zu akzeptieren, die Ziffernfolge in der Basis 4 zu akzeptieren, die durch 7 Btw teilbar sind, versuchen Sie, den Dateinamen auf. png oder. jpeg zu ändern.
Comments
Post a Comment