Kann ein regulärer Ausdruck unendlich sein?

Ich weiß, dass Sprachen, die mit regulären Ausdrücken definiert werden können und die durch DFA / NFA (endliche Automaten) erkennbar sind, gleichwertig sind. Auch für die Sprache existiert kein DFA $\{0^n1^n|n \ge 0\}$ . Trotzdem kann es mit regulären Ausdrücken (im Übrigen kann jede nicht reguläre Sprache verwendet werden) als $\{ \epsilon \} \cup \{01\} \cup \{0011\}......$ . Wir wissen jedoch, dass jede Sprache, die einen regulären Ausdruck hat, einen DFA hat, der ihn erkennt (Widerspruch zu meiner früheren Aussage). Ich weiß, dass dies eine triviale Sache ist, aber beinhaltet die Definition des regulären Ausdrucks die Bedingung, dass er endlich sein sollte?

formal-languages regular-languages regular-expressions Sashas
quelle

⊊

$\subsetneq$

Nur eine Randnotiz: Wenn wir die Anforderung, dass DFA / NFA endlich ist, fallen lassen , können wir einen Automaten erstellen, der akzeptiert .

{0^{n} 1^{n} ∣ n \geq 0}

$\{0^n1^n\mid n\geq0\}$

Aus terminologischer Sicht ist das Wort "Automaten" der Plural von "Automaten". Es gibt kein Wort "Automaten" - Sie können es nicht pluraler machen, als es bereits ist. (Automaten sind korrekt als Possessiv, aber nicht als Plural)

Chasly aus Großbritannien

Antworten:

Wenn reguläre Ausdrücke unendlich sein könnten , wäre jede Sprache regulär gewesen.

In Anbetracht der Sprache können wir immer den regulären Ausdruck definieren, der genau definiert . (Beispiel: Der reguläre Ausdruck definiert .) $L=\{w_1, w_2, \ldots\}$ $R = w_1 + w_2 + \cdots$ $L$
$R_1 = \epsilon+0+1+00+01+10+11+\cdots$ $L_1=\{0,1\}^*$

Wir wissen, dass einige Sprachen nicht regulär sind, daher zeigt dies, dass unendliche reguläre Ausdrücke eine größere Klasse von Sprachen beschreiben als endliche reguläre Ausdrücke.

Ran G.
quelle

Ich liebe diese Antwort, weil sie nicht nur besagt, dass unendliche reguläre Ausdrücke unterschiedlich sind, sondern dass das Konzept insgesamt nicht aussagekräftig ist.

Jmite

Eine prägnantere Aussage zu dem Punkt, den ich in meinem zweiten Absatz begraben habe, und daher klarer.

Davislor

Aber es endet mit einer reinen Tautologie. Warum betrachten wir dann nicht alle Sprachen als regulär, wenn sie diese Form haben? Die Dinge, die wir mit Regexen machen, funktionieren nicht mehr. Wir können eine Zustandsmaschine nicht mit einem induktiven Algorithmus erstellen, da sie niemals beendet wird und unendliche Zustände aufweist. Wir können nicht mit allem in der Liste vergleichen und ablehnen, wenn nichts übereinstimmt. Und wir können die Liste sowieso nicht physisch darstellen. (Die Listen, die wir vom Computer erstellen können, sind die entscheidenden Sprachen.) Wir können Dinge beweisen, indem wir die Tatsache verwenden, dass jede Sprache diese Form hat, aber nicht die Art von Dingen, die wir über Regexe kennen.

Davislor

@jmite "ist nicht sinnvoll" oder ein Sonderfall?

BAR

@BAR ist nicht aussagekräftig, da in der durch unendliche reguläre Ausdrücke beschriebenen Klasse über nur die Menge aller Sprachen ist. Wir bekommen keine Sprachklasse wie bei endlichen REs, CFGs oder sogar Turing-Maschinen.

Σ

$\Sigma$

2^{Σ}

$2^{\Sigma}$

Jmite

Ja, es muss endlich sein. Stellen Sie sich vor, Sie haben unendlich viele mögliche Übereinstimmungen und Ihre Eingabe ist 011. Würdest du es jemals ablehnen können? Würden Ihnen jemals die Streichhölzer ausgehen, um sie zu überprüfen?

Gibt es eine Sprache, die nach dieser Definition nicht regelmäßig wäre ? Was ist mit der Menge aller Programm- und Eingabepaare, sodass das angegebene Programm bei der angegebenen Eingabe anhält?

Wenn Sie ein Programm hätten, das die Zeichenfolgen in einer Sprache in lexikografischer Reihenfolge auflistet -

Aktualisieren

Um ein wenig anhand des Feedbacks in den Kommentaren zu verdeutlichen, ist der Grund, warum nicht jede Sprache dieses Formulars regelmäßig ist, per Definition. Wenn Sie zum Beispiel den Beweis von Kleenes Theorem nachschlagen, hängt dies davon ab, dass ein regulärer Ausdruck endlich sein muss, um zu beweisen, dass er eine endliche Zustandsmaschine erzeugt.

Warum definieren wir so „normale“ Sprache? Da jede formale Sprache eine Teilmenge der Zeichenketten eines Alphabets ist und jede Zeichenkette als Vereinigung von Singletons ausgedrückt werden kann, wäre reguläre Sprache nur ein Synonym für , wenn wir eine Reihe von Zeichenketten als „reguläre“ Sprache bezeichnen würden Sprache . Dies ist keine sehr nützliche Definition, zumal wir sie nicht in Hardware oder Software implementieren können. Wir können nirgendwo eine beliebige unendliche Liste speichern oder eine Maschine mit unendlichem Zustand erstellen.

Wie ich jedoch angedeutet habe, können Sie, wenn Sie die Möglichkeit haben, alle Zeichenfolgen in einer Sprache der Reihe nach aufzulisten, daraus eine Entscheidung treffen (akzeptieren Sie, wenn Sie genau diese Zeichenfolge sehen, lehnen Sie ab, wenn Sie auf eine Zeichenfolge stoßen, die nach der von Ihnen kommt suchen) und umgekehrt (für jede Zeichenfolge in der richtigen Reihenfolge, führen Sie sie durch den Entscheider und geben Sie sie genau dann aus, wenn sie akzeptiert wird). Wenn wir also jede aufzählbare Sprache als regulär betrachten würden , wäre jede entscheidbare Sprache „regulär“ und wir würden einen neuen Begriff für die Sprachen benötigen, die von endlichen Zustandsmaschinen erkannt werden, und ihre äquivalenten Codierungen als endliche Ausdrücke.

Davislor
quelle

Diese Antwort ist falsch. Die Tatsache allein, dass eine Repräsentation einer Sprache nicht dazu geeignet ist, einen algorithmischen Entscheider auf naive Weise aufzubauen, bedeutet nicht , dass diese Repräsentation falsch ist; Es könnte andere Ansätze geben. Tatsächlich hat jede entscheidbare Sprache eine Darstellung der Form, die Sasha vorschlägt! Kurz gesagt, Sie begehen den Irrtum "Ich kann nicht sehen, wie, also muss es unmöglich sein".

Raphael

@ Raphael: Bitte bedenken Sie die Auswirkungen Ihrer Aussage: " Jede entscheidbare Sprache hat eine Darstellung der Form, die Sasha vorschlägt!" Das ist in der Tat der Punkt, den ich in meiner Antwort angesprochen habe. Die Frage war, sind alle Sprachen dieser Form als regulär definiert? Ist jede entscheidbare Sprache regelmäßig? (Und, wie ich gezeigt habe, auch einige unentscheidbare?) Wäre das eine nützliche Definition von „normal“?

Davislor

Darüber hinaus war mein letzter Satz kein Hinweis darauf, dass eine Entscheidung für eine unendliche Liste der Zeichenfolgen nicht getroffen werden kann, sondern ein Hinweis darauf, wie dies getan werden kann: Wenn die Liste der Zeichenfolgen gut geordnet ist, können Sie eine sofort ablehnen wenn Sie in der Reihenfolge auf eine Zeichenfolge stoßen. Eine endliche Zustandsmaschine kann dies jedoch nicht tun, da sie nicht alle Zustände darstellen kann, die mit jeder Zeichenfolge in der unendlichen Liste verglichen wurden, und auch keine regulären Ausdrücke. Wenn sie könnten, wären sie mächtig genug, um alle entscheidenden Sprachen zu erkennen.

Davislor

Angenommen, reguläre Ausdrücke dürfen unendlich sein.

Somit ist die durch {ϵ} ∪ {01} ∪ {0011} ... definierte Sprache regulär. Für jede reguläre Sprache gibt es eine NFA. Eine Möglichkeit, diese NFA zu erhalten, besteht darin, individuelle NFAs für jede von {ϵ}, {01}, {0011} ... zu haben und diese mithilfe von ϵ-Übergängen zu kombinieren. Da es unendlich viele reguläre Ausdrücke gibt, müssen unendlich viele Sub-NFAs kombiniert werden. NFA kann jedoch nur eine begrenzte Anzahl von Zuständen haben (Definition von NFA).

Somit gibt es keine NFA, die eine Sprache definieren kann, die durch Vereinigung unendlicher regulärer Ausdrücke definiert ist, was impliziert, dass die Sprache nicht regulär ist.

Somit gibt es keinen regulären Ausdruck, der dieselbe Sprache definieren kann wie die Sprache, die durch die Vereinigung unendlicher regulärer Ausdrücke definiert wird.

Reguläre Ausdrücke können also nur endliche Ausdrücke haben.

Anurag Peshne
quelle

Ihre "unendlichen regulären Ausdrücke" definieren dann eine andere Klasse von Sprachen, keine regulären Sprachen. Tatsächlich sind sie in der Lage, jede Sprache zu definieren , und das ist absolut uninteressant (sie sind nicht endlich, daher schwer zu bearbeiten; und sie können alles tun, also nichts, was sie in Bezug auf Einschränkungen lernen könnten).

vonbrand