Beweis der Nichtregelmäßigkeit, basierend auf der Kolmogorov-Komplexität

8

Im Unterricht zeigte uns unser Professor drei Methoden zum Nachweis der Nichtregelmäßigkeit:

  1. Myhill-Nerode-Theorem
  2. Pumping Lemma für reguläre Sprachen
  3. Beweis der Nichtregelmäßigkeit, basierend auf der Kolmogorov-Komplexität

Jetzt habe ich die ersten beiden, Myhill-Nerode-Theorem und Pumping-Lemma, gut verstanden und konnte auch die Übungen zu den ersten beiden Methoden machen. Aber den dritten habe ich nicht verstanden. Die Definition der dritten Methode lautet wie folgt:

Sei L ( Σ b o o l ) eine reguläre Sprache. Sei L x = { y ( Σ b o o l ) | x y L } für jedes x ( Σ b o o l ) . Dann existiert eine Konstante c , so dass für alle x , y ( Σ b o L(Σbool) Lx={y(Σbool)|xyL} x(Σbool) c x,y(Σbool)

 K(y)log2(n+1)+c

wenn y das n-te Wort in der Sprache L x ist . y Lx

Jetzt verstehe ich nicht, wie ich diesen Satz verwenden soll, um zu beweisen, dass eine Sprache nicht regelmäßig ist. Ich verstehe das Konzept nicht wirklich. Wir haben die Kolmogorov-Komplexität zuvor verwendet, um die Länge des kürzesten Computerprogramms eines Objekts zu bestimmen. Wie beweist man mit diesem Satz die Unregelmäßigkeit? Und was ist der Gedanke dahinter?

Vielen Dank!

gammaALpha
quelle

Antworten:

8

Meines Wissens ist dies kein "klassischer" Ansatz zur Charakterisierung regulärer Sprachen.

Dieser Ansatz wird in "Ein neuer Ansatz zur formalen Sprachtheorie durch Kolmogorov-Komplexität" von Ming Li und Paul MB Vitanyi diskutiert (siehe Abschnitt 3.1).

L

L={1p|p is prime}

xΣLx={y|xy=1pp is prime}x=1ppky1Lxy1=1pppk+1K(y1)cn=1cL

xS={y1x|x=1p for prime p y1x is the first string in Lx}cSS={1pk+1pk|k1}pkkSL

Ariel
quelle
2
Ich wusste nichts von dieser Technik. Möchten Sie eine Antwort auf unsere Referenzfrage hinzufügen ?
Raphael
1
Ja, ich kann später eine hinzufügen. Ich muss allerdings zugeben, dass auch ich diese Technik nicht kannte, sondern nur auf dieses Papier gestoßen bin, nachdem ich die Frage von op nachgeschlagen hatte. Ich bin mir nicht sicher, wie beliebt (im Vergleich zu anderen Methoden) diese Technik war. Das Papier in Arxiv wurde tatsächlich 1995 in SIAM veröffentlicht, ist also nicht so neu, wie ich zuerst dachte (immer noch interessanter und origineller Ansatz).
Ariel
 1pp Lx y1=1pp
1
x=1pLxy1x=1pppxy1x=1p+(pp)=1pxy1xy1x
3

Lww={www{0,1}}

Ich gebe Ihnen einen sehr informellen Beweis in der Hoffnung, dass er Ihnen helfen kann, die Rolle der Kolmogorov-Komplexität besser zu verstehen.

DLDx=yzyxLDz

LwwDww

y|y|=n|D|

x=yzyDwwqizx=yzyz=ww

 Let y = 10110
       y   z
 x = 10110 0  >> rejected
 x = 10110 1  >> accepted  (w=101, |y|>|z|)
 x = 10110 00 >> rejected
 x = 10110 01 >> rejected
 ....
 x = 10110 10110 >> accepted  (w=10110,  |y|=|z| !!!)
 ....
 x = 10110 1101101 >> accepted (w=101101, |z|<|y|

z|y|z=y

Dwwqiy|y|Dww2|y|z=y

=|Dww|+logi+logy+c

|Dww|Dwwlogiqilogyyc

yy<|y|y

Vor
quelle
Ich wusste nichts von dieser Technik. Möchten Sie eine Antwort auf unsere Referenzfrage hinzufügen ?
Raphael