Ist regelmäßig?

Ich habe vor einigen Wochen meine Theorie der Rechenprüfungen abgelegt, und dies war eine der Fragen:

Angenommen, die Sprache $L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$

Ist L regelmäßig? Wenn ja, geben Sie einen regulären Ausdruck oder einen Automaten dafür an.

Nachdem ich ihn nach der Prüfung kurz nach der Antwort gefragt habe, scheint sie wirklich regelmäßig zu sein (ich glaube, er sagte, der Ausdruck sei einfach $(a^*b^*)^*$ ). Ich kann jedoch nicht verstehen, warum das so ist. So wie ich es sehe, verkettet es sich $a^nb^m$ r wie folgt:

$a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$ ,

Dies ist nicht regelmäßig, da ein Automat nicht jedes Mal n und m abrufen kann. Wo bin ich hier schuld?

EDIT: Ich habe wieder mit dem Professor gesprochen, er gab zu, dass es ein Fehler war. Die Sprache ist in der Tat nicht regelmäßig.

formal-languages regular-languages regular-expressions Exci
quelle

Sie sollten Ihren Lehrer fragen, ob die Sprache mit der Sprache . Wenn er "Ja" sagt, dann sag ihm, dass ich dir gesagt habe, dass seine Frage schlecht formuliert ist.

L

$L$

K = {a^{n_{1}} b^{m_{1}} a^{n_{2}} b^{m_{2}} \dots a^{n_{r}} b^{n_{r}} ∣ r \geq 0, a_{1}, \dots, a_{r} \geq 0, b_{1}, \dots, b_{r} \geq 0}

$K = \lbrace a^{n_1} b^{m_1} a^{n_2} b^{m_2} \cdots a^{n_r} b^{n_r} \mid r \geq 0, a_1, \ldots, a_r \geq 0, b_1, \ldots, b_r \geq 0\rbrace$

Andrej Bauer

Das scheint der einzige Weg zu sein, wie es regelmäßig sein könnte, und tatsächlich ist dies das, was ich ursprünglich hastig gedacht und tatsächlich in Betracht gezogen habe (a b ) *, aber es dann gelöscht habe, als ich realisierte, dass n und m gleich bleiben (oder sollten ..) und gab eine Pump-Lemma-Ablehnung für r = 2, die dasselbe für größeres r gilt (wahrscheinlich auch nicht genau eine vollständige Lösung, aber es scheint in die richtige Richtung zu gehen). Unnötig zu sagen, ich habe 0 für diese Frage. Ich werde versuchen, ihn zu kontaktieren.

Ich würde die Frage sicherlich so verstehen, wie Sie es ursprünglich getan haben.

Andrej Bauer

Sehen Sie hier , um weitere Möglichkeiten zu zeigen , dass eine Sprache nicht regulär ist.

Raphael

Sie könnten das auch mit Hilfe von Pumping Lemma beweisen

SAHIL THUKRAL

Antworten:

Die Sprache ist nicht regulär, wie mit der Nerode-Methode bewiesen werden kann. Betrachten Sie die folgenden Wörter für . Dann , sondern für , . Daher muss sich jeder Automat für nach dem Lesen jedes in einem anderen Zustand befinden , was seiner Endlichkeit widerspricht. $L$ $w_n = a^n b$ $n \in \mathbb{N}$ $w_n^2 \in L$ $n \neq m$ $w_n w_m \notin L$ $L$ $w_n$

Yuval Filmus
quelle

In Ihrem Kommentar weisen Sie darauf hin, dass Sie (Zitat) "eine Pump-Lemma-Ablehnung für , wobei dasselbe für größeres ". $r=2$ $r$

Dies kann in der Tat durch Anwenden einer Verschlusseigenschaft formalisiert werden. Die regulären Sprachen sind unter Kreuzung geschlossen. Wenn also regulär ist, dann wäre dies , wodurch und effektiv gesetzt werden . $L$ $L\cap a^*ba^*b = \{ a^n b a^n b \mid n\ge 0\}$ $r=2$ $m=1$

Hendrik Jan.
quelle

Lieber Leser, bitte nehmen Sie nicht weg "wenn

nicht regulär ist, dann ist

hier" - denn das ist einfach falsch!

L

$L$

L^{'} \supset L

$L' \supset L$

Raphael

@ Raphael Richtig. Die korrekte Implikation wäre also "wenn

nicht regulär ist, dann ist

", wobei

regulär ist.

L \cap R

$L\cap R$

L

$L$

R

$R$

Hendrik

Natürlich. Ich befürchtete, dass Anfänger "effektiv einstellen ..." lesen und dies anwenden könnten, ohne die Verschlusseigenschaften zu verwenden.

Raphael

Die Sprache: {(a ⁿ b ^m ) ^r | n, m, r≥0} ist nicht regulär, da der Automat / die Maschine zwar die erste Folge von Buchstaben 'a' und dann die Buchstaben 'b' liest, aber zählen muss, wie oft er den Buchstaben 'a' und gelesen hat die Häufigkeit, mit der der Buchstabe 'b' in der ersten Sequenz gelesen wurde, um den Wert von n und m zu kennen .

Wenn r> 1 ist, wird eine andere gleiche Folge von Buchstaben 'a' und Buchstaben 'b' erwartet.

Wenn der Automat / die Maschine nicht weiß, wie viele Buchstaben 'a' und 'b' er in der ersten Sequenz gelesen hat , kennt er auch den Wert von n und m nicht und kann daher nicht sagen, ob Die anderen Sequenzen vom vorletzten bis zum letzten sind Wörter, die der ersten Sequenz entsprechen.

Es ist jedoch bekannt, dass nur eine Turing-Maschine die Werte von n und m zählen und kennen und die obige Sprache erkennen kann, so dass die obige Sprache nicht nur nicht regulär ist, sondern auch nicht kontextfrei, dh auch nicht kontextfrei nicht vorhanden Kellerautomaten , diese Sprache zu erkennen und sie nicht existiert kontextfreie Grammatik , dass jeder von dieser kontextfreien Grammatik abgeleiteten Wortes in der obigen Sprache.

Da die Tatsache, dass sowohl der deterministische endliche Automat als auch der endliche Pushdown-Automat die Werte von n und m im Gegensatz zur Turing-Maschine nicht zählen und kennen , können sie die obige Sprache nicht erkennen und daher ist die obige Sprache nicht kontextfrei und ist nicht regelmäßig.

Gegenbeispiel zu der Annahme, dass die obige Sprache regulär ist:

Für n = 3 ∧ m = 5 ∧ r = 2 ist das folgende Wort in der obigen Sprache:

aaabbbbbaaabbbbb

Aber das folgende Wort ist nicht in der Sprache:

aaabbbbbaaaaabbb, weil n, m und r nicht existieren , also:

(a ⁿ b ^m ) ^r = aaabbbbbaaaaabbb, denn um die erste Folge von Buchstaben 'a' und dann die Buchstaben 'b' zu erfüllen, muss wahr sein, dass n = 3 ∧ m = 5 ist und dass wir 2 Folgen von Buchstaben sehen ' a 'und dann Buchstaben' b ', dann r = 2 , aber wenn n = 3 ∧ m = 5 ∧ r = 2, dann (a ⁿ b ^m ) ^r = (a ³ b ⁵ ) ² = (aaabbbbb) ² = aaabbbbbaaabbbbb ≠ aaabbbbbaaaaabbb, weil ihre Suffixe unterschiedlich sind, dh aaabbbbb ≠ aaaaabbb, obwohl ihre Präfixe für r = 1 gleich aaabbbbb sind.

Der "beste" deterministische endliche Automat, der für diese Sprache gebaut werden kann, ist der deterministische endliche Automat, der den regulären Ausdruck (a * b *) * erkennt , aber die obige Sprache nicht erkennt, weil er sagt, dass beide Wörter aaabbbbbaaabbbbb und aaabbbbbaaaaabbb sind in der Sprache und dies ist nicht wahr, weil aaabbbbbaaabbbbb in der Sprache ist, aber aaabbbbbaaaaabbb ist nicht in der Sprache.

Selbst ein endlicher Pushdown-Automat kann nicht sagen, ob beide Wörter in der Sprache sind oder nicht, also kann nur die Turing-Maschine.

In der zweiten Sequenz stellte die Turing-Maschine fest, dass n = 5 ∧ m = 3 ist, und dies widerspricht, dass in der ersten Sequenz n = 3 ∧ m = 5 gefunden wurde , sodass das zweite Wort nicht in der Sprache ist , aber im ersten Wort findet sich kein Widerspruch.

Beide Sequenzen erfüllen n = 3 ∧ m = 5 , daher sagt die Turing-Maschine, dass das erste Wort in der Sprache ist.

Nur Turing-Maschinen können, wenn sie die Werte von n und m zählen und sich merken, indem sie ihren Wert auf das Band schreiben und später lesen.

Farewell Stack Exchange
quelle