Algorithmus zum Testen, ob eine Sprache regulär ist

Gibt es einen Algorithmus / ein systematisches Verfahren, um zu testen, ob eine Sprache regulär ist?

Mit anderen Worten, wenn eine Sprache in algebraischer Form angegeben ist (denken Sie an etwas wie $L=\{a^n b^n : n \in \mathbb{N}\}$ ), testen Sie, ob die Sprache regulär ist oder nicht. Stellen Sie sich vor, wir schreiben einen Webdienst, der den Schülern bei all ihren Hausaufgaben hilft. Der Benutzer gibt die Sprache an und der Webdienst antwortet mit "normal", "nicht regulär" oder "Ich weiß nicht". (Wir möchten, dass der Webdienst so selten wie möglich mit "Ich weiß nicht" antwortet.) Gibt es einen guten Ansatz, um dies zu automatisieren? Ist das nachvollziehbar? Ist es entscheidbar (dh kann garantiert werden, dass wir niemals mit "Ich weiß nicht" antworten müssen)? Gibt es einigermaßen effiziente Algorithmen zur Lösung dieses Problems und die Möglichkeit, für viele / die meisten Sprachen, die in der Praxis wahrscheinlich auftreten, eine andere Antwort als "Weiß nicht" zu liefern?

Die klassische Methode, um zu beweisen, dass eine Sprache nicht regelmäßig ist, ist das Pump-Lemma. Es sieht jedoch so aus, als ob irgendwann manuelle Einsichten erforderlich sind (z. B. um das zu pumpende Wort auszuwählen), sodass mir nicht klar ist, ob dies in etwas Algorithmisches umgewandelt werden kann.

Eine klassische Methode, um zu beweisen, dass eine Sprache regulär ist, wäre die Verwendung des Myhill-Nerode-Theorems, um einen Automaten mit endlichen Zuständen abzuleiten. Dies scheint ein vielversprechender Ansatz zu sein, erfordert jedoch die Fähigkeit, grundlegende Operationen an Sprachen in algebraischer Form auszuführen. Mir ist nicht klar, ob es eine systematische Möglichkeit gibt, alle erforderlichen Operationen symbolisch für Sprachen in algebraischer Form auszuführen.

Um diese Frage gut zu stellen, müssen wir entscheiden, wie der Benutzer die Sprache spezifiziert. Ich bin offen für Vorschläge, aber ich denke so etwas:

L = {E : S}

$L = \{E : S\}$

Dabei ist ein Wortausdruck und ein System linearer Ungleichungen über die Längenvariablen mit den folgenden Definitionen: $E$ $S$

Jedes von ist ein Wortausdruck. (Dies sind Variablen , die auf ein beliebiges Wort in nehmen .) $x,y,z,\dots$ $\Sigma^*$
Jedes von ist ein Wortausdruck. (Hier steht für die Umkehrung der Zeichenfolge .) $x^r,y^r,z^r,\dots$ $x^r$ $x$
Jedes von ist ein Wortausdruck. (Implizit ist , also stellen ein einzelnes Symbol im zugrunde liegenden Alphabet dar.) $a,b,c,\dots$ $\Sigma=\{a,b,c,\dots\}$ $a,b,c,\dots$
Jedes von ist ein Wortausdruck, wenn eine ist. $a^\eta,b^\eta,c^\eta,\dots$ $\eta$
Die Verkettung von Wortausdrücken ist ein Wortausdruck.
Jedes von ist eine Längenvariable. (Dies sind Variablen, die eine beliebige natürliche Zahl annehmen können.) $m,n,p,q,\dots$
Jeder von Ist eine Längenvariable. (Diese repräsentieren die Länge eines entsprechenden Wortes.) $|x|,|y|,|z|,\dots$

Dies scheint breit genug zu sein, um viele der Fälle zu behandeln, die wir in Lehrbuchübungen sehen. Natürlich können Sie jede andere Textmethode zur Angabe einer Sprache in algebraischer Form ersetzen, wenn Sie einen besseren Vorschlag haben.

Ich hatte noch keine Zeit, über Ihre Wahl der Sprachausdrücke nachzudenken. Welche Arten von Sprachen werden ungefähr behandelt? Wenn Sie die Einschränkung hinzufügen, dass eine Wortvariable nur einmal vorkommt, sind alle diese Sprachen kontextfrei?

Gilles 'SO - hör auf böse zu sein'

Vielleicht können Sie versuchen,

selbst mit einer Grammatik zu schreiben ? Wie

und

Ist es kurz und bündig, was Sie beschreiben?

E

$E$

E ::= c^{η} ∣ x ∣ E E ∣ E^{r}

$E ::= c^η ∣ x ∣ EE ∣ E^r$

η ::= n ∣ | x |

$η ::= n ∣ |x|$

jmad

Sie können

ausdrücken, sodass dies weit über kontextfreie Sprachen hinausgeht. Trotzdem vermute ich, dass das Problem mindestens so schwer ist wie die Entscheidung, ob eine kontextfreie Grammatik eine reguläre Sprache definiert.

{a^{n} b^{n} c^{n} ∣ n \in N}

$\{a^nb^nc^n \mid n\in\mathbb{N}\}$

Gilles 'SO - hör auf böse zu sein'

@jmad, ja, das wäre absolut vernünftig. Ich bin nicht an diese Wahl der Sprachausdrücke gebunden: Sie können gerne etwas anderes wählen, wenn Sie etwas anderes finden, das angemessener ist. Gilles, toller Anstellwinkel! (Für Zuschauer sind Ergebnisse bekannt, die zeigen, dass es unentscheidbar ist, zu testen, ob eine beliebige kontextfreie Grammatik eine reguläre Sprache definiert.) Wenn das Problem unentscheidbar ist, würde ich vorschlagen, das Problem zu optimieren, damit der Webdienst antworten kann "Ich ziehe nicht an 't know', und fragen Sie dann nach einem Algorithmus, der so selten wie möglich auf "Ich weiß nicht" antwortet.

Diese Klasse ist nicht unter Kleene Stern geschlossen, oder? Können Sie ausgewogene Klammern ausdrücken?

Gilles 'SO - hör auf böse zu sein'

Antworten:

Die Antwort ist nein. Die Entscheidung, ob eine bestimmte kontextfreie Grammatik eine reguläre Sprache erzeugt, ist ein unentscheidbares Problem.

Update . Ich habe diese negative Antwort auf die allgemeine Frage gegeben

Testen Sie anhand einer in algebraischer Form angegebenen Sprache, ob die Sprache regulär ist oder nicht

da kontextfreie Sprachen Lösungen algebraischer Gleichungen in Sprachen sind: siehe Kapitel II, Sätze 1.4 und 1.5 im Buch von J. Berstel Transductions and Context-Free Languages .

Dieselbe Frage ist jedoch für deterministische kontextfreie Sprachen zu entscheiden, ein nicht triviales Ergebnis aufgrund von Stearns [1] und verbessert durch Valiant [2]:
[1] RE Stearns, Ein Regelmäßigkeitstest für Pushdown-Maschinen, Information und Kontrolle 11 323- 340 (1967). DOI: 10.1016 / S0019-9958 (67) 90591-8.
[2] LG Valiant. Regelmäßigkeit und damit verbundene Probleme für deterministische Pushdown-Automaten J. ACM 22 (1975), S. 1–10.

Es gibt ein weiteres positives Ergebnis, das näher an den im zweiten Teil der Frage angegebenen Spezifikationen liegt. Denken Sie daran, dass die semilinearen Teilmengen von genau die Mengen sind, die in der Presburger-Arithmetik definiert werden können. Es gibt auch die rationalen Teilmengen von . Insbesondere ist eine durch lineare Ungleichungen definierte Teilmenge von rational. Bei einer rationalen Teilmenge von ist es nun entscheidbar, ob die Sprache $\mathbb{N}^k$ $\mathbb{N}^k$ $\mathbb{N}^k$ $R$ $\mathbb{N}^k$ ist regulär. In der Tat ist bekannt [Ginsburg-Spanier], dass genau dann regulär ist, wenn eine erkennbare Teilmenge von und es entscheidend ist [Ginsburg-Spanier], ob eine gegebene rationale Teilmenge von erkennbar ist.

L. (R.) = {u_{1}^{n_{1}} \dots u_{k}^{n_{k}} ∣ (n_{1}, . . ., n_{k}) \in R.}}

$L(R) = \{ u_1^{n_1} \dotsm u_k^{n_k} \mid (n_1, ...,n_k) \in R \}$

L (R)

$L(R)$

R

$R$

N^{k}

$\mathbb{N}^k$

N^{k}

$\mathbb{N}^k$

S. Ginsburg und EH Spanier., Halbgruppen, Presburger Formeln und Sprachen , Pacific J. Math. 16 (1966), 285 & ndash; 296.

S. Ginsburg und EH Spanier. Begrenzte reguläre Sets , Proc. der amerikanischen Mathematik. Soc. 17 , 1043–1049 (1966).

Dies löst nicht den zweiten Teil der Frage, der aufgrund der Wortvariablen möglicherweise unentscheidbar ist, aber es gibt zunächst ein vernünftiges Fragment.

J.-E. Stift
quelle

(a) Pedantic nit: Mir ist nicht klar, ob die obige algebraische Syntax allgemein genug ist, um alle kontextfreien Grammatiken auszudrücken (wie Gilles und ich in den Kommentaren angedeutet haben), daher ist nicht ganz klar, ob dieses bestimmte Ergebnis hier gilt . (b) Wichtiger: Bitte betrachten Sie die Problemstellung als entsprechend optimiert, damit der Webdienst mit "Ich weiß nicht" antworten kann, und wir möchten einen Algorithmus finden, der so selten mit "Ich weiß nicht" antwortet wie möglich. Ich habe dies zuvor in den Kommentaren vorgeschlagen. Ich werde die Frage bearbeiten, um dies in der Frage selbst klarer zu machen.

Ich vermute, dass Sie den Beweis anpassen können, aber das Ergebnis folgt nicht. Ich denke, es gibt kontextfreie Sprachen, die in diesem Formalismus nicht ausgedrückt werden können: Wie drücken Sie beispielsweise ausgewogene Klammern aus? Die Sprachklasse ist unter Kleene Star nicht geschlossen, oder?

Gilles 'SO - hör auf böse zu sein'

@ Gilles, ja, darüber habe ich nachgedacht. Mir ist nicht sofort klar, wie ich den Beweis anpassen soll. Der Standardbeweis dafür, dass es unentscheidbar ist, ob eine kontextfreie Grammatik regulär ist, ist der Satz von Greibach. Für mich sieht es jedoch nicht so aus, als würde diese Sprachklasse die Prämissen von Greibachs Theorem erfüllen (es ist unwahrscheinlich, dass sie unter Verkettung mit regulären Mengen geschlossen und unter Vereinigung geschlossen wird). Vielleicht gibt es einen anderen Beweisansatz, mit dem ich nicht vertraut bin. Ich stimme zu, es ist nicht klar, wie man die Sprache ausgewogener Klammern in dieser algebraischen Form ausdrückt.

Habe gerade die Referenzen hinzugefügt.

J.-E.

Ihr Beitrag beantwortet die Frage nicht, da er eine andere Sprachklasse anspricht. Die hier erlaubten algebraischen Formen (mit einem einzigen Wortausdruck) sind (soweit wir das beurteilen können) nicht so allgemein wie die algebraischen Formen, die zum Ausdrücken beliebiger kontextfreier Sprachen erforderlich sind. Es könnte der Fall sein, dass für den Schnittpunkt der beiden das Problem entscheidbar ist.

Gilles 'SO - hör auf böse zu sein'