Wie komplex ist der Zustand der Kopiersprache?

Es sei eine Zahl angegeben. Betrachten Sie die folgende Sprache $n$ . $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$

In Worten ist die Menge von Kopierzeichenfolgen der Länge . $L_n$ $2n$

Betrachten Sie die folgenden Zustandskomplexitätsfunktionen so, dass die Anzahl der Zustände in den kleinsten Pushdown-Automaten ist, die . $s$ $s(n)$ $L_n$

Frage: Können Sie formal eine sinnvolle Untergrenze für ? $s(n)$

Meine Vermutung: . $s(n) = 2^{\Theta(n)}$

Bekannte Obergrenze: . $s(n) \leq \mathrm{poly}(n) \cdot 2^{\frac{n}{2}}$

Regeln:

(1) Das Stapelalphabet muss binär sein.

(2) Das Eingabeband ist einseitig und kann bei keinem Eingabezeichen anhalten.

fl.formal-languages automata-theory grammars context-free Michael Wehar
quelle

Ich habe derzeit keine aussagekräftige Untergrenze. Mir scheint, Sie können möglicherweise eine Untergrenze für die Anzahl der Variablen nachweisen, die Sie für ein CFG benötigen, das die Sprache erkennt. Obwohl ich mir dessen nicht einmal ganz sicher bin.

Michael Wehar

Meine Intuition ist, dass Sie beim Verschieben von Zeichen vom Eingabeband auf den Stapel auf ein Problem stoßen. Wenn Sie diese Bits später jemals abrufen möchten, müssen Sie alle Bits wegwerfen, die Sie darüber geschoben haben. Mit anderen Worten, es scheint, dass der Stapel Ihnen nicht hilft, denn je mehr Sie darauf drücken, desto mehr müssen Sie später vergessen.

Michael Wehar

Anmerkung: Für DFAs (Automaten ohne Stapel) können Sie eine untere Grenze für die Komplexität des exponentiellen Zustands nachweisen.

Michael Wehar

{0^{k} 1^{l} 0^{k} 1^{l}}

$\{0^k1^l0^k1^l\}$

(n + 3) 2^{n / 2}

$(n+3)2^{n/2}$

Antworten:

Die von Yuval beschriebene Technik:

Gibt es eine CFG mit Polynomgröße, die diese endliche Sprache beschreibt?

(Sie können auch lesen: Untergrenzen für die Größe von CFGs für bestimmte endliche Sprachen )

$G$ $L_n$ $w\in \{0,1\}^n$ $A(w)$ $s(w)$ $ww$ $n/2$ $n$ $p(w)$ $ww$ $n/2$ $w,w'$ $A(w)=A(w')$ $p(w)=p(w')$ $2^{n/2}$ $A(w)$ $p(w)$ $2^{\Theta(n)}$

$2^{\Theta(n)}$ $L_n$

Joseph Stack
quelle

Super, nochmals vielen Dank! Ich sehe jetzt und werde darüber nachdenken, um zu bestätigen. :)

Michael Wehar

[n, 2 n]

$[n,2n]$

[n / 2, n]

$[n/2,n]$

(A (w), p (w))

$(A(w),p(w))$

A (w)

$A(w)$

w w

$ww$

p (w)

$p(w)$

Siehe auch Satz 7 in meinem Artikel : cs.toronto.edu/~yuvalf/CFG-LB.pdf .

Yuval Filmus

@YuvalFilmus Es ist auch erwähnenswert, dass Andras einige Zeit damit verbracht hat, die oberen und unteren Grenzen in Einklang zu bringen. Mein Freund Pepe und ich haben eine allgemeine Klasse endlicher Sprachen definiert und die Technik auf sie angewendet. Wir haben aber nie etwas geschrieben. Wenn Sie jemals Probleme damit haben, sind wir gerne bereit, zusammenzuarbeiten. Danke noch einmal.

Michael Wehar