Zustandsmaschinen verstehen

Eine Einführung in Informatikkonzepte

Die Informatik ermöglicht es uns zu programmieren, aber es ist möglich, viel zu programmieren, ohne die zugrunde liegenden Konzepte der Informatik zu verstehen.

Das ist nicht immer schlecht. Wenn wir programmieren, arbeiten wir auf einer viel höheren Abstraktionsebene.

Wenn wir ein Auto fahren, beschäftigen wir uns nur mit zwei oder drei Pedalen, einer Schaltung und einem Lenkrad. Sie können ein Auto sicher bedienen, ohne eine klare Vorstellung davon zu haben, wie es funktioniert.

Wenn Sie ein Auto jedoch an den Grenzen seiner Möglichkeiten betreiben möchten, müssen Sie viel mehr über Automobile wissen als nur die drei Pedale, die Schaltung und das Lenkrad.

Gleiches gilt für die Programmierung. Ein Großteil der täglichen Arbeit kann mit wenig oder keinem Verständnis der Informatik erledigt werden. Sie müssen die Computertheorie nicht verstehen, um ein Kontaktformular in PHP zu erstellen.

Wenn Sie jedoch Code schreiben möchten, der ernsthafte Berechnungen erfordert, müssen Sie etwas mehr darüber wissen, wie Berechnungen unter der Haube funktionieren.

Der Zweck dieses Artikels besteht darin, einige grundlegende Hintergrundinformationen für die Berechnung bereitzustellen. Wenn Interesse besteht, werde ich vielleicht einige fortgeschrittenere Themen behandeln, aber jetzt möchte ich die Logik hinter einem der einfachsten abstrakten Rechengeräte betrachten - einer endlichen Zustandsmaschine .

Finite-State-Maschinen

Eine endliche Zustandsmaschine ist eine mathematische Abstraktion, die zum Entwerfen von Algorithmen verwendet wird.

Einfacher ausgedrückt liest eine Zustandsmaschine eine Reihe von Eingaben. Wenn eine Eingabe gelesen wird, wechselt sie in einen anderen Status. Jeder Status gibt an, in welchen Status für einen bestimmten Eingang gewechselt werden soll. Das klingt kompliziert, ist aber sehr einfach.

Stellen Sie sich ein Gerät vor, das ein langes Stück Papier liest. Auf jeden Zentimeter Papier ist ein einzelner Buchstabe gedruckt - entweder der Buchstabe 'a' oder der Buchstabe 'b'.

Wenn die Zustandsmaschine jeden Buchstaben liest, ändert sie den Zustand. Hier ist eine sehr einfache Zustandsmaschine:

Die Kreise sind „ Zustände “, in denen sich die Maschine befinden kann. Die Pfeile sind die Übergänge . Wenn Sie sich also im Zustand s befinden und ein 'a' lesen, wechseln Sie in den Zustand q . Wenn Sie ein 'b' lesen, bleiben Sie im Zustand s .

Wenn wir also mit s beginnen und das Papierband oben von links nach rechts lesen, lesen wir das 'a' und gehen zum Zustand q über .

Dann lesen wir 'b' und kehren zu Zustand s zurück .

Ein weiteres 'b' hält uns auf s , gefolgt von einem 'a' - was uns zurück in den q- Zustand bringt . Einfach genug, aber worum geht es?

Nun, es stellt sich heraus, dass Sie ein Band durch die Zustandsmaschine laufen lassen und etwas über die Buchstabenfolge erzählen können, indem Sie den Zustand untersuchen, in dem Sie sich befinden.

Wenn wir in unserer obigen einfachen Zustandsmaschine mit dem Zustand s enden , muss das Band mit einem Buchstaben 'b' enden. Wenn wir im Zustand q enden , endet das Band mit dem Buchstaben 'a'.

Das mag sinnlos klingen, aber es gibt eine Menge Probleme, die mit dieser Art von Ansatz gelöst werden können. Ein sehr einfaches Beispiel wäre zu bestimmen, ob eine HTML-Seite diese Tags in dieser Reihenfolge enthält:

Die Zustandsmaschine kann in einen Zustand wechseln, der anzeigt, dass sie das HTML-Tag gelesen hat, eine Schleife ausführen, bis sie zum Head-Tag gelangt, eine Schleife, bis sie zum Head-Close-Tag gelangt, und so weiter.

Wenn es erfolgreich in den Endzustand gelangt, haben Sie diese bestimmten Tags in der richtigen Reihenfolge.

Finite-State-Maschinen können auch verwendet werden, um viele andere Systeme darzustellen - wie die Mechanik einer Parkuhr, einer Pop-Maschine, einer automatisierten Gaspumpe und allerlei anderer Dinge.

Deterministische endliche Zustandsmaschinen

Die Zustandsmaschinen, die wir bisher betrachtet haben, sind alle deterministische Zustandsmaschinen. In jedem Zustand gibt es nur einen Übergang für eine zulässige Eingabe. Mit anderen Worten, es kann nicht zwei Pfade geben, die aus einem Zustand herausführen, wenn Sie den Buchstaben 'a' lesen. Das klingt zunächst albern, um diese Unterscheidung überhaupt zu treffen.

Was nützt eine Reihe von Entscheidungen, wenn dieselbe Eingabe dazu führen kann, dass mehr als ein Zustand erreicht wird? Sie können einem Computer nichts sagen, if x == truedann ausführen doSomethingBigoder ausführen doSomethingSmall, oder ?

Nun, Sie können eine Art mit einer Zustandsmaschine.

Die Ausgabe einer Zustandsmaschine ist ihr Endzustand. Es durchläuft die gesamte Verarbeitung, und dann wird der Endzustand gelesen und anschließend eine Aktion ausgeführt. Eine Zustandsmaschine nicht tut alles , wie es von Staat zu Staat bewegt.

Es verarbeitet, und wenn es zu Ende ist, wird der Zustand gelesen und etwas Äußeres löst die gewünschte Aktion aus (z. B. das Ausgeben einer Getränkedose). Dies ist ein wichtiges Konzept, wenn es um nicht deterministische Finite-State-Maschinen geht.

Nicht deterministische endliche Zustandsmaschinen

Nicht deterministische Finite-State-Maschinen sind Finite-State-Maschinen, bei denen eine bestimmte Eingabe aus einem bestimmten Zustand zu mehr als einem anderen Zustand führen kann.

Nehmen wir zum Beispiel an, wir möchten eine endliche Zustandsmaschine erstellen, die Buchstabenfolgen erkennen kann, die:

  • Beginnen Sie mit dem Buchstaben 'a'
  • und dann folgen null oder mehr Vorkommen des Buchstabens 'b'
  • oder null oder mehr Vorkommen des Buchstabens 'c'
  • werden durch den nächsten Buchstaben des Alphabets beendet.

Gültige Zeichenfolgen wären:

  • abbbbbbbbc
  • abbbc
  • acccd
  • acccccd
  • ac (null Vorkommen von b)
  • ad (null Vorkommen von c)

Es erkennt also den Buchstaben 'a', gefolgt von null oder mehr des gleichen Buchstabens von 'b' oder 'c', gefolgt vom nächsten Buchstaben des Alphabets.

Eine sehr einfache Möglichkeit, dies darzustellen, ist eine Zustandsmaschine, die wie die folgende aussieht. Ein Endzustand von t bedeutet, dass die Zeichenfolge akzeptiert wurde und mit dem Muster übereinstimmt.

Sehen Sie das Problem? Von Startpunkt s wissen wir nicht, welchen Weg wir einschlagen sollen. Wenn wir den Buchstaben 'a' lesen, wissen wir nicht, ob wir in den Zustand q oder r gehen sollen.

Es gibt verschiedene Möglichkeiten, um dieses Problem zu lösen. Eine davon ist das Zurückverfolgen. Sie nehmen einfach alle möglichen Pfade und ignorieren oder verlassen diejenigen, bei denen Sie stecken bleiben.

So funktionieren im Grunde die meisten Schachcomputer. Sie betrachten alle Möglichkeiten - und alle Möglichkeiten dieser Möglichkeiten - und wählen den Weg, der ihnen die meisten Vorteile gegenüber ihrem Gegner bietet.

Die andere Möglichkeit besteht darin, die nicht deterministische Maschine in eine deterministische Maschine umzuwandeln.

Eines der interessanten Attribute einer nicht deterministischen Maschine ist, dass es einen Algorithmus gibt, mit dem jede nicht deterministische Maschine in eine deterministische Maschine umgewandelt werden kann. Es ist jedoch oft viel komplizierter.

Zum Glück ist das obige Beispiel nur geringfügig komplizierter. Tatsächlich ist dieses so einfach, dass wir es ohne die Hilfe eines formalen Algorithmus in eine deterministische Maschine in unserem Kopf verwandeln können.

Die Maschine unten ist eine deterministische Version der nicht deterministischen Maschine oben. In der Maschine unten wird ein Endzustand von t oder v durch eine beliebige Zeichenfolge erreicht, die von der Maschine akzeptiert wird.

Das nicht deterministische Modell hat vier Zustände und sechs Übergänge. Das deterministische Modell hat sechs Zustände, zehn Übergänge und zwei mögliche Endzustände.

Das ist nicht viel mehr, aber die Komplexität wächst normalerweise exponentiell. Eine nicht deterministische Maschine mittlerer Größe kann eine absolut große deterministische Maschine erzeugen .

Reguläre Ausdrücke

Wenn Sie irgendeine Art von Programmierung durchgeführt haben, sind Sie wahrscheinlich auf reguläre Ausdrücke gestoßen. Reguläre Ausdrücke und endliche Zustandsmaschinen sind funktional äquivalent. Alles, was Sie akzeptieren oder mit einem regulären Ausdruck abgleichen können, kann mit einer Zustandsmaschine akzeptiert oder abgeglichen werden.

Zum Beispiel könnte das oben beschriebene Muster mit dem regulären Ausdruck abgeglichen werden: a(b*c|c*d)

Reguläre Ausdrücke und endliche Zustandsmaschinen haben ebenfalls die gleichen Einschränkungen. Insbesondere können beide nur Muster abgleichen oder akzeptieren, die mit endlichem Speicher verarbeitet werden können.

Also, welche Art von Mustern können sie nicht übereinstimmen? Angenommen, Sie möchten nur Zeichenfolgen von 'a' und 'b' abgleichen, wobei eine Anzahl von 'a' gefolgt von einer gleichen Anzahl von 'b' vorhanden ist. Oder n 'a gefolgt von n ' b, wobei n eine Zahl ist.

Beispiele wären:

  • ab
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbb

Auf den ersten Blick scheint dies eine einfache Aufgabe für eine Finite-State-Maschine zu sein. Das Problem ist, dass Ihnen schnell die Zustände ausgehen oder Sie eine unendliche Anzahl von Zuständen annehmen müssen - zu diesem Zeitpunkt ist es keine endliche Zustandsmaschine mehr .

Angenommen, Sie erstellen eine endliche Zustandsmaschine, die bis zu 20 'a' gefolgt von 20 'b' s akzeptieren kann. Das funktioniert einwandfrei, bis Sie eine Zeichenfolge von 21 'a gefolgt von 21' b erhalten. An diesem Punkt müssen Sie Ihre Maschine neu schreiben, um eine längere Zeichenfolge zu verarbeiten.

Für jede Zeichenfolge, die Sie erkennen können, gibt es eine, die nur ein wenig länger ist und die Ihr Computer nicht erkennen kann, weil der Speicher knapp wird.

Dies ist als Pumping Lemma bekannt, das im Grunde sagt: "Wenn Ihr Muster einen Abschnitt hat, der wiederholt werden kann (wie der obige), dann ist das Muster nicht regelmäßig."

Mit anderen Worten, es kann weder ein regulärer Ausdruck noch eine endliche Zustandsmaschine konstruiert werden, die alle Zeichenfolgen erkennt, die mit dem Muster übereinstimmen.

Wenn Sie genau hinschauen, werden Sie feststellen, dass diese Art von Muster, bei dem jedes 'a' ein passendes 'b' hat, HTML sehr ähnlich sieht. Innerhalb eines beliebigen Paares von Tags können Sie eine beliebige Anzahl anderer übereinstimmender Paare von Tags haben.

Während Sie möglicherweise einen regulären Ausdruck oder eine endliche Zustandsmaschine verwenden können, um zu erkennen, ob eine HTML-Seite die ; Bei Elementen in der richtigen Reihenfolge können Sie keinen regulären Ausdruck verwenden, um festzustellen, ob eine gesamte HTML-Seite gültig ist oder nicht - da HTML kein reguläres Muster ist.ml>, ead>

Turingmaschinen

Woran erkennt man unregelmäßige Muster ?

Es gibt eine theoretische Vorrichtung, die einer Zustandsmaschine ähnlich ist und als Turingmaschine bezeichnet wird. Es ähnelt einer Finite-State-Maschine darin, dass es einen Papierstreifen hat, den es liest. Eine Turingmaschine kann jedoch das Papierband löschen und darauf schreiben.

Das Erklären einer Turing-Maschine wird mehr Platz beanspruchen als hier, aber es gibt einige wichtige Punkte, die für unsere Diskussion über endliche Zustandsmaschinen und reguläre Ausdrücke relevant sind.

Turingmaschinen sind rechnerisch vollständig - was bedeutet, dass alles, was berechnet werden kann, auf einer Turingmaschine berechnet werden kann.

Da eine Turingmaschine sowohl vom Papierband schreiben als auch lesen kann, ist sie nicht auf eine endliche Anzahl von Zuständen beschränkt. Es kann angenommen werden, dass das Papierband unendlich lang ist. Natürlich haben tatsächliche Computer nicht unendlich viel Speicher. Normalerweise enthalten sie jedoch genügend Speicher, sodass Sie die Grenze für die Art der von ihnen verarbeiteten Probleme nicht erreichen.

Turing Machines bieten uns ein imaginäres mechanisches Gerät, mit dem wir die Funktionsweise des Rechenprozesses visualisieren und verstehen können. Dies ist besonders nützlich, um die Grenzen der Berechnung zu verstehen. Wenn Interesse besteht, werde ich in Zukunft einen weiteren Artikel über Turingmaschinen schreiben.

Warum ist das wichtig?

Also, was ist der Punkt? Wie können Sie das nächste PHP-Formular erstellen?

Unabhängig von ihren Einschränkungen sind Zustandsautomaten ein sehr zentrales Konzept für die Datenverarbeitung. Insbesondere ist es wichtig, dass es für jede nicht deterministische Zustandsmaschine, die Sie entwerfen können, eine deterministische Zustandsmaschine gibt, die dasselbe tut.

Dies ist ein wichtiger Punkt, da Sie Ihren Algorithmus so entwerfen können, wie es am einfachsten zu bedenken ist. Sobald Sie einen funktionierenden Algorithmus haben, können Sie ihn in die effizienteste Form konvertieren.

Das Verständnis, dass endliche Zustandsmaschinen und reguläre Ausdrücke funktional gleichwertig sind, eröffnet einige unglaublich interessante Verwendungsmöglichkeiten für Engines für reguläre Ausdrücke - insbesondere, wenn es darum geht, Geschäftsregeln zu erstellen, die geändert werden können, ohne ein System neu zu kompilieren.

Eine Grundlage in der Informatik ermöglicht es Ihnen, ein Problem zu lösen, das Sie nicht lösen können, und zu argumentieren: „Ich weiß nicht, wie man X löst, aber ich weiß, wie man Y löst. Und ich weiß, wie man eine Lösung konvertiert für Y in eine Lösung für X. Deshalb weiß ich jetzt, wie man X löst. “

Wenn Ihnen dieser Artikel gefällt, könnte Ihnen mein YouTube-Kanal gefallen, auf dem ich gelegentlich Videos oder Cartoons zu bestimmten Aspekten der Softwareerstellung erstelle. Ich habe auch eine Mailingliste für Leute, die gelegentlich eine E-Mail wünschen, wenn ich etwas Neues produziere.

Ursprünglich veröffentlicht auf blog.markshead.com am 11. Februar 2018.