Wie man intuitiv fühlt, dass eine Sprache regelmäßig ist

9

Wie kann ich bei einer Sprache direkt sagen, ohne auf die Produktionsregeln zu achten, dass diese Sprache nicht regulär ist?L={anbncn}

Ich könnte Pumping Lemma gebrauchen, aber einige Leute sagen nur mit Blick auf die Grammatik, dass dies keine reguläre ist. Wie ist es möglich?

Doniyor
quelle
1
Jeder kann sich jede Sprache ansehen und einfach sagen, dass sie nicht regelmäßig ist. Ich bin mir nicht sicher, ob die Intuition an sich hier genauso eine Rolle spielt wie die Erfahrung. Dies ist eine ziemlich einfache Sprache (obwohl sie nicht regelmäßig ist), die beim Studium formaler Sprachen unvermeidlich ist. Sobald Ihnen gesagt wurde, dass es nicht regelmäßig ist und Sie bewiesen haben, dass es nicht regelmäßig ist, wenn Sie eine gültige Proof-Technik verwenden, benötigen Sie normalerweise keinen Proof, um andere Leute zu überzeugen, da sie es alle selbst bewiesen haben, als sie in die eingeführt wurden Gegenstand.
Patrick87
Ja, aber manchmal folgen sie in Vorlesungen nur einigen trockenen mathematischen Beweisen, aber es fehlen ihnen wirklich intuitive Erklärungen mit wirklich einfachen Beispielen
Doniyor
Vergiss . Haben Sie jemals das Gefühl gehabt, dass a n b n nicht regelmäßig ist? anbncnanbn
Uday Reddy
2
Mit Blick auf eine Grammatik und zu verkünden , weil die Grammatik die nicht regelmäßig ist Sprache nicht regulär ist , ist ein Irrtum. Es gibt viele nicht reguläre Grammatiken für reguläre Sprachen. In acht nehmen! Die Entscheidung, ob eine Grammatik regelmäßig ist, ist jedoch einfach. Überprüfen Sie einfach die Produktionen.
Raphael
Es gibt eine ähnliche Frage auf math.SE .
Raphael

Antworten:

11

Die Haupteigenschaft von DFAs / NFAs ist der Mangel an unbegrenztem Speicher. Wenn Sie sich eine Sprache ansehen und der einzige Algorithmus (der später in einen endlichen Automaten übersetzt werden sollte), den Sie sich vorstellen können, erfordert diese Eigenschaft, dh Sie glauben, dass jeder Algorithmus, der sie erkennt, sich an eine beliebige große Anzahl von Dingen erinnern muss (wie in Ihrem Beispiel) dann ist diese Sprache wahrscheinlich nicht regulär.n

Natürlich sollten Sie immer daran denken, dass mathematische Intuition falsch sein kann, und der einzige Weg, sich Ihrer Intuition sicher zu sein, besteht darin, sie zu beweisen.

EDIT: Ich werde die letzte Frage in den Kommentaren hier wegen Platzmangels beantworten.

Ihr redet von unbegrenztem Gedächtnis, was der Grund ist, warum es nicht regelmäßig ist. aber ein ^ nb ^ m kann auch unbegrenztes Gedächtnis haben, wenn ich will, nicht wahr? das gibt mir immer noch keinen Frieden.

Das Problem ist nicht, wie groß die Wörter werden können (normalerweise werden Sie auf unendlich viele reguläre Sprachen stoßen, weil jede endliche Sprache regulär ist, und das ist ziemlich langweilig), sondern wie sehr sich das EDA daran erinnern muss.
Im Beispiel muss man sich nicht an m , n erinnern . Der Algorithmus muss nur sicherstellen, dass sie positiv sind und dass das Wort richtig geordnet ist. Dies ist eine endliche Liste, und jedes der Elemente in der Liste benötigt eine konstante Speichermenge. Vergleichen Sie dies mit a n b n , für das ein einfacher Alogrithmus erforderlich ist, um sich daran zu erinnern, dass die Anzahl von a gleich der Anzahl von b istambnm,n
anbnab's. Dies erfordert unbegrenzten Speicher. Wenn ich mir eine Sprache anschaue und sehe, dass jeder Algorithmus, den ich mir vorstellen kann, unbegrenztes Gedächtnis benötigt, wird meine Intuition, dass die Sprache nicht regelmäßig ist, stärker. Wenn ich in angemessener Zeit keinen "intelligenten" Algorithmus finden kann (der eine konstante Menge an Speicher benötigt) (wie viel Zeit angemessen ist, liegt bei Ihnen), werde ich versuchen zu beweisen, dass die Sprache nicht regelmäßig ist.
Hoffe das macht es etwas klarer.

Boris Trayvas
quelle
Danke, mathematische Beweise bringen die Intuition, aber schauen Sie sich diese Produktionsregel an: S -> ab | aSb. Dies ist für ein ^ nb ^ n, das besagt, dass es auch nicht regelmäßig ist. aber a ^ mb ^ n ist regulär mit m, n> = 1. warum ist das? das sind eigentlich die gleiche Form, oder? Ich verstehe den Unterschied zwischen diesen beiden Sprachen nicht
Doniyor
1
Für a ^ nb ^ n müssen Sie zwei Dinge im Auge behalten: Erstens, dass die Anzahl von a gleich der Anzahl von b ist (dies ist der unmögliche Teil für DFAs), und zweitens, dass auf kein 'b' ein 'a' folgt '. Für a ^ mb ^ n ist der Wert von m, n egal. Sie kümmern sich nur darum, dass es mindestens ein 'a' und mindestens ein 'b' gibt und dass auf kein 'b' ein 'a' folgt. Informell gesehen müssen Sie sich nur an drei Dinge erinnern.
Boris Trayvas
Oh okay, jetzt habe ich es verstanden.
Doniyor
Die Reihenfolge ist also auch das Entscheidende, oder? wie aabbcc akzeptiert aber nicht aabcbc nur weil die bestellung nicht in ordnung ist. richtig?
Doniyor
1
"Die Haupteigenschaft regulärer Sprachen ist der Mangel an unbegrenztem Gedächtnis." - Ich weiß, was du meinst, aber dieser Satz macht keinen Sinn. "Sie glauben, dass jeder Algorithmus, der ihn erkennt, sich an eine beliebige große Anzahl von Dingen erinnern muss" - Dies ist zwar die einzige Intuition, die ich auch kenne, aber ihre Art ist sehr, sehr gefährlich; siehe hier .
Raphael
5

Ich könnte Pumping Lemma gebrauchen

Genau. Nachdem Sie das Pumping-Lemma oder eine der anderen Techniken einige Male (von Dutzenden) verwendet haben, werden Sie die Muster in Sprachen sehen, die verhindern, dass sie regelmäßig sind. ist eine sehr grundlegende, die Sie wahrscheinlich bereits gemeistert haben. Das ist also auch eine Frage der Erfahrung, nicht nur der Intuition.anbn

Ein guter Weg, um Ihre Intuition zu testen, ist das Betrachten dieser Sprachen:

  1. {xyyzx,y,z{a,b}+}
  2. {xyyzx,y,z{a,b}}
  3. {xyyzx,y,z{a,b,c}+}
  4. {xyyzx,y,z{a,b,c}}

Welche sind kontextfrei?

Raphael
quelle
1
Wenn jemand ähnlich schöne Beispiele für die Grenze der regulären Sprachen kennt, sagen Sie es bitte. Bitte verderben Sie die Antwort in den Kommentaren nicht.
Raphael
Raphael - tolle Arbeit! Vielen Dank, dass Sie Beispiele nennen und mich explizit testen.
Doniyor
@doniyor lassen Sie uns diese Diskussion im Chat fortsetzen
Raphael
4

Sie können tatsächlich entscheiden, ob eine Sprache regelmäßig ist, indem Sie ziemlich einfache Berechnungen durchführen, anstatt einen vollständigen Beweis zu erbringen. Sie müssen lediglich ein sehr leistungsfähiges Kriterium anwenden: Eine Sprache ist genau dann regulär, wenn sie endlich viele Quotienten hat.

LxxLwxwLL={anbn}aL={an1bn|n1}bL=akL={ankbn|nk}L

DDSaaLDS

James Koppel
quelle
b \ L bedeutet: Wenn ich das L durch b teile, bekomme ich eine leere Menge?. liegt es daran, dass ich das Wort tatsächlich von Anfang an lesen muss? und nicht von hinten?
Doniyor
1
bL=L/b
1
Hier ist ein gutes Dia-Deck, das Quotienten erklärt und erklärt, wie man DFAs daraus erstellt: cs.cmu.edu/~cdm/pdf/Minimization.pdf
James Koppel
oh okay, vielen Dank. Jetzt bekomme ich ein bisschen. mmm ... lassen Sie mich dies noch einmal für eine Weile studieren ...
Doniyor