Kann eine FSA zählen?

11

Dies kann eine dumme Frage sein. Es scheint klar zu sein, dass eine FSA, da sie endlich ist, nur die Anzahl der Symbole in ihrer Eingabezeichenfolge bis zu einer durch die Anzahl ihrer Zustände begrenzten Anzahl zählen kann. Nehmen wir nun an, wir statten die FSA mit Ausgabefunktionen (z. B. Druckfunktionen) aus. Es wäre dann sehr einfach, eine Maschine zu konstruieren, die in der Lage ist, ein Symbol für jedes gelesene Symbol zu drucken. Würde das als Zählen gelten? Wenn nicht, warum nicht?

Um es stattdessen in FSTs auszudrücken: Ich gehe davon aus, dass es nicht möglich ist, eine FST zu konstruieren, die in der Lage ist, eine Zeichenfolge beliebiger Länge einer binären Darstellung (dh einer Zahl im Zahlensystem der Basis 2) ihrer Länge zuzuordnen. Aber es ist natürlich trivial, eine FST zu konstruieren, die in der Lage ist, eine Zeichenfolge beliebiger Länge einer Zeichenfolge der genannten Nullen (oder Einsen) derselben Länge zuzuordnen. Aber das könnte als Zählen gelten, nicht wahr? Weil die FST eine Darstellung der Länge ihrer Eingabe erstellt. Eine etwas seltsame Darstellung, aber immer noch eine Darstellung, nicht wahr?

Torbjörn
quelle
1
Sie stellen also wirklich die Frage "Was zählt?" Das klingt für mich nicht nach Informatik. Es wäre Informatik, wenn Ihre Frage lautete: "Kann eine FSA für diese Definition des Zählens zählen?".
Sasho Nikolov

Antworten:

8

Diese Frage ist etwas vage, daher hier eine vage Antwort: Das Übersetzen von Unary in Unary zählt nicht genau, da die Maschine "am Ende" nicht "weiß", wie groß die Eingabe war.

Sie erkennen dies natürlich, weshalb Sie die Tatsache in Frage stellen, dass es tatsächlich zählt.

Das Übersetzen von unär nach binär scheint jedoch eine weitaus fortgeschrittenere Operation zu sein, da es nicht nur Zählen, sondern auch Arithmetik beinhaltet.

Vielleicht ist der genauere Begriff, den man betrachten muss, anstatt zu zählen, der Vergleich . Das heißt, wenn zwei Zahlen (unär) und 1 m gegeben sind , bestimmen Sie, ob n = m ist .1n1mn=m

Die Fähigkeit, diesen Vergleich durchzuführen, führt zur berühmten nicht regulären Sprache . Und die Unfähigkeit einer NFA zu zählen macht diese Sprache unregelmäßig.{anbn:n0}

Interessanterweise ist diese Sprache eine CFL. Tatsächlich kann das entsprechende Automatenmodell - PDAs - nur einen begrenzten Vergleich durchführen.

Wenn Sie über das Vergleichen sprechen, geben Wandler Ihnen keine zusätzliche Leistung mehr, sodass die Frage in diesem Sinne gelöst ist.

Ein zusätzlicher Hinweis: Ganz informell kann die Möglichkeit, zwei Zahlen zu vergleichen, häufig zur Simulation einer 2-Zähler-Maschine Minsky Machine verwendet werden , die TMs entspricht.

Shaull
quelle
4

Nr endliche Automaten zählen nicht. Sie mögen Dinge tun, die so aussehen, aber sie können nicht zählen. Sie können sogar ein paar (fest verdrahtete) Berechnungen durchführen (z. B. feststellen, ob eine Binärzahl durch drei teilbar ist ), aber das zählt nicht.

Eine kleine Geschichte. Sie befinden sich auf einem großen rechteckigen Platz in einer berühmten Stadt. Die Einheimischen sagen Ihnen, dass der Platz tatsächlich quadratisch ist. Wenn Sie zählen können, überprüfen Sie, ob die horizontale und vertikale Anzahl der Kacheln übereinstimmt, indem Sie die Kacheln entlang der Seiten des Quadrats zählen. Wenn Sie nicht zählen können, können Sie den Anspruch dennoch überprüfen: Beginnen Sie an einer Ecke und gehen Sie diagonal. Wenn Sie genau die gegenüberliegende Ecke erreichen, haben Sie ein Quadrat.

In Ihrem Beispiel testet die fsa, ob eine Zeichenfolge die gleiche Anzahl von 's und b ' s hat, indem diese Zahlen auf zwei verschiedene Ausgabebänder verteilt werden. Ein anderes Gerät muss den endgültigen Vergleich durchführen, es sei denn, Sie haben einen Trick, um die Buchstaben a und b paarweise zu behandeln und gegeneinander zu drücken. Wie auf dem Platz.abab

Jetzt ein formelleres Modell zum Vergleichen. Nach dem Chomsky-Schützenberger-Theorem ist jede kontextfreie Sprache eine Umkehrung einer endlichen Zustandsübertragung T der Dyck-Sprache D 2 auf zwei Klammerpaaren L = T - 1 ( D 2 ) (es wird nicht so angegeben wie auf Wikipedia, aber du musst mir glauben). Nun kann der Finite-State-Wandler T seine kontextfreie Sprache L wie folgt "akzeptieren" (für jede Sprache seinen eigenen Wandler). Bei Eingabe transformiert T den String in die (erratene) Reihe von Pops und Pushs des pda fürLTD2L=T1(D2)TLT , dann teste, ob das Ergebnis ein Pushdown-Verhalten ist, dh das Ergebnis ist eine Zeichenfolge in D 2 . (Technische Details weggelassen, aber dies ist wie im Ch-Sch-Theorem behauptet: man hat w T - 1 ( D 2 ) wenn T ( w ) D 2 )LD2wT1(D2)T(w)D2

Mein Punkt hier ist, dass einige "Berechnungen" vom Wandler durchgeführt werden, aber im Test mit viel Leistung verborgen ist . Ebenso Ihr Beispiel, bei dem zwei Buchstaben auf zwei Bändern sortiert sind. D2

Hendrik Jan.
quelle
Ich kann einen DFA konstruieren, der zwischen und 2 n zählt ! (für feste n ) oder auch in N . Das ist mehr als jeder menschliche oder echte Computer schafft. Wie würden Sie das Zählen nennen? 02n!nN
Raphael
@ Raphael. Sicher. Und leicht größere Zahlen als das. Hören Sie auf zu lehren, dass kontextfreie Sprachen leistungsfähiger sind als normale Sprachen: Sie sind gleich (zumindest für Zeichenfolgen mit einer Länge von höchstens ). Nur ein Scherz. Wenn man sich auf solche echten Computersprachen bezieht, ist alles ein endlicher Zustand, nicht wahr? Endliche Automaten zählen nicht! Sie unterscheiden nur eine endliche Anzahl von Zuständen, obwohl diese Anzahl sehr groß sein kann. 2n!
Hendrik Jan
Aber wie FSAs normalerweise präsentiert werden, dürfen sie nur "Ja" (akzeptiert) oder "Nein" (nicht akzeptiert) sagen. Vor diesem Hintergrund konnte niemand eine FSA konstruieren, die zählt. Wenn wir zulassen, dass es den (Nummer des) Zustands meldet (z. B. druckt), in dem es sich befindet, wenn es beendet wird, kann es zählen, aber nur bis zu einer Grenze, die durch die Anzahl der Zustände gegeben ist. Wenn wir jedoch zulassen, dass es gedruckt wird, ist es trivial, eine FSA mit einem einzelnen Status zu erstellen, die jedes Mal 1 druckt, wenn ein Symbol aus der Eingabezeichenfolge gelesen wird, und so die Anzahl in der Tally-Darstellung angibt. Was ist los mit dieser Idee?
Torbjörn
Und wenn wir das Berichten / Drucken vergessen und stattdessen in internen Darstellungen denken, kann eine FSA die Symbole in einer Zeichenfolge zählen, aber nicht in einer willkürlich langen. Die Einzelstaat-FSA kann dann natürlich überhaupt nicht zählen.
Torbjörn
k
1

@Shaull: Danke für deine Antwort! Ich bin neu bei StackExchange und weiß nicht, wie ich eine Antwort kommentieren soll. Deshalb schreibe ich stattdessen eine Antwort, in der Hoffnung, dass mir vergeben wird.

Hmm, es scheint mir, dass ein Hirte zählt, der seine Schafe zählt, indem er für jedes Schaf, das er sieht, eine Markierung auf einen Zettel schreibt, oder ein Gefangener, der die Tage zählt, an denen er im Gefängnis war, indem er Markierungen an die Wand schreibt. Warum zählen n Markierungen auf einem Zettel oder an einer Wand nicht als Darstellung der Zahl n? Wird das nicht als Tally-Repräsentation bezeichnet? AFAICS ist einer binären Darstellung in keiner Weise unterlegen, außer dass sie mehr Platz benötigt.

Ich nehme an, dass "wissen" für Sie bedeutet, dass es am Ende eine interne Darstellung der Zählung gibt. Dann ist es natürlich offensichtlich, dass eine FSA von FST die Länge einer beliebigen Zeichenfolge nicht berechnen kann. Wenn wir jedoch kein Wissen in diesem Sinne benötigen, sondern nur verlangen, dass die FSA oder FST das Ergebnis einem externen Beobachter mitteilen kann, scheint es mir in Ordnung zu sein, die Zählung in einem Tally-Format darzustellen.

Wenn ein FSA sowohl mit inkrementellen Ein- als auch Ausgängen ausgestattet ist, sollte er im Prinzip in der Lage sein, seine externe Umgebung als Lese- / Schreibspeicher zu verwenden und somit so leistungsfähig wie eine Turing-Maschine zu sein. Richtig?

Vielen Dank, dass Sie den Fall des Vergleichs angesprochen haben. Nun scheint es so zu sein, dass wir, wenn wir die Anforderung einer internen Darstellung aufheben und nur verlangen, dass die Maschine das Ergebnis einem externen Beobachter präsentieren kann, leicht ein FSM erstellen könnten, das eine Art von erzeugen könnte grafische Darstellung des Ergebnisses. Angenommen, der FSM hat beim Lesen "aaaaaabbbbbb" geschrieben

000000
000000

Da die Balken gleich lang sind, hat der FSM die Zeichenfolge "aaaaaabbbbbb" akzeptiert. Zwei gleich lange Balken bedeuten "Ja", unterschiedliche Längen bedeuten "Nein".

Ich denke, ich verbiege die Regeln, aber das ist es, was ich will, da ich an den mehr oder weniger impliziten Annahmen interessiert bin, die auf dem Gebiet der mathematischen Linguistik gemacht werden.

Torbjörn
quelle
FSAWOC{an|n is prime }
Ich denke, der Unterschied zwischen den Beispielen, die Sie geben, und der FST-Ausgabe besteht darin, dass der Hirte die Zeilen lesen kann, nachdem sie geschrieben wurden, während ein FSM dies nicht kann. Gleiches gilt für den Vergleich.
Shaull
Sie können einen Kommentar abgeben, indem Sie auf den Link "Kommentar hinzufügen" unter einem Beitrag klicken.
Raphael
Jede FSA, die zum Zählen einer Herde konstruiert wurde, kann diese Herde zählen. Keine konstruierte FSA kann eine Herde zählen. Die grundlegende Frage ist, ob der Hirte nur weit genug zählen kann, um zumindest seine eigene Herde zu zählen, oder ob er die gesamte Bandbreite der natürlichen Zahlen nutzen kann. Nach meiner Erfahrung müssen wir Menschen irgendwann in unserem Mathematikunterricht explizit den Übergang zwischen den beiden Fähigkeiten vollziehen.
Reinierpost
1

FSMs können innerhalb eines endlichen Bereichs / einer endlichen Anzahl von Schritten "zählen", die durch Zustandsübergänge angezeigt werden . Sie können jedoch nicht über eine endliche Anzahl von Schritten hinaus zählen.

In gewisser Weise kann eine FSA-ähnliche Maschine zählen. Eine eng verwandte Maschine wird als Finite-State-Transducer bezeichnet . Der Wandler kann tatsächlich im Sinne eines "leitungsgebundenen" Eingangs und Ausgangs zählen. Ein einzelner Wandler kann eine Eingangssequenz (etwa binär) aufnehmen und in eine inkrementierte Ausgangssequenz "umwandeln". dann "verkettet" man die (identischen) Count-by-1-Wandler, wobei jeder seinen Eingang um 1 erhöht und ausgibt. Es ist auch wie ein rudimentärer "Streaming-Algorithmus" .

vzn
quelle
Weitere Details: Der Wandler kann die Arbeit in der Reihenfolge "lsb" auf "msb" erhöhen, dh "Least Sig Bit" auf "Most Sig Bit" unter Verwendung einer Logik ähnlich der des EE- Volladdierers .
vzn
fyi Finite-State-Wandler scheinen nicht viel untersucht worden zu sein. Es gibt eine weitere interessante Anwendung für die Collatz-Vermutung , eine Maschine zu erstellen, die Iterationen berechnet. Alle, die sich für weitere Theorie / Diskussion interessieren, kontaktieren mich bitte im Chat oder auf meinem Blog .
vzn