Abschlussprüfung unter Umkehrung der von Min-Heap-Automaten akzeptierten Sprachen

Dies ist eine Folgefrage von diesem .

In einer früheren Frage zu exotischen Zustandsautomaten haben sich Alex ten Brink und Raphael mit den Rechenfähigkeiten einer besonderen Art von Zustandsautomaten befasst: Min-Heap-Automaten. Sie konnten zeigen, dass die Menge der von solchen Maschinen akzeptierten Sprachen ( ) weder eine Teilmenge noch eine Obermenge der Menge der kontextfreien Sprachen ist. In Anbetracht der erfolgreichen Lösung und des offensichtlichen Interesses an dieser Frage stelle ich weiterhin mehrere Anschlussfragen.$HAL$

Es ist bekannt, dass die regulären Sprachen unter einer Vielzahl von Operationen geschlossen werden (wir beschränken uns möglicherweise auf grundlegende Operationen wie Vereinigung, Schnittmenge, Ergänzung, Differenz, Verkettung, Kleene-Stern und Umkehrung), während die kontextfreien Sprachen unterschiedliche Schließungen aufweisen Eigenschaften (diese sind unter Vereinigung, Verkettung, Kleene-Stern und Umkehrung geschlossen).

Ist HAL wegen Stornierung geschlossen?

Betrachte die Sprache (wobei # 0 ( x ) die Anzahl der Nullen in x angibt ).

Mit einer HAL-Maschine ist es einfach, zu bestimmen. Beachten Sie , dass die Maschine zwei Eigenschaften verfolgen muss: die Anzahl der Nullen in x vs y und die Länge von x , y (vs z ). Es kann a für jede in x angezeigte Null in den Heap schieben (und später für jede in y angezeigte Null popen ). Zusätzlich wird für jedes Bit in x , y gedrückt (und später für jedes Bit in z ). Da alle s den Haufen runtergeschoben werden, stören sie die Zählung nicht. Die $L_{\times 2}$$x$$y$$x,y$$z$0$x$0$y$1$x,y$1$z$10$\bot$ dient als Begrenzer und kann praktisch ignoriert werden.

Sei nun , die umgekehrte Sprache. Das heißt, L = { z ⊥ y y x ∣ x , y , z ∈ { 0 , 1 } , # 0 ( x ) = # 0 ( y )  und  | x | + | y | = z } Wir werden zeigen, dass keine HAL-Maschine L entscheiden kann .$L = L_{\times 2}^R$

Die Intuition ist die folgende. Wie oben muss die Maschine sowohl die Länge von als auch die Anzahl der Nullen in x , y verfolgen . In diesem Fall müssen sie jedoch gleichzeitig verfolgt werden . Dies kann nicht über einen Heap erfolgen. Im Detail enthält der Heap nach dem Lesen von z Informationen über die Länge von | x | + | y | . Beim Lesen von y muss die Maschine auch die Anzahl der Nullen in y auf dem Haufen halten . Diese Informationen können jedoch nicht mit den Informationen interferieren, die der Heap bereits über die erwartete Länge von $z$$x,y$$z$$|x|+|y|$$y$$y$$x$sein. Sehr intuitiv ist entweder die Information über die Anzahl der Nullen "unter" der Information über die Länge von , und dann können wir nicht darauf zugreifen, während wir x lesen , oder es ist "über" dieser Information, wodurch letzterer unzugänglich wird, oder Zwei Informationen werden "gemischt" und werden bedeutungslos.$x$$x$

Formal werden wir eine Art "Pumping" -Argument verwenden. Das heißt, wir nehmen eine sehr lange Eingabe und zeigen, dass sich der "Zustand" der Maschine während der Verarbeitung dieser Eingabe wiederholen muss, wodurch wir die Eingabe "ersetzen" können, sobald die Maschine ihren "Zustand" wiederholt.

$\varepsilon$$^1$$c$$c$

$H$$L$$4n$$|x|=|y|=n$$|z|=2n$$\bot$$z,y$$\#_0(y) = n/2$${n \choose n/2}$$x$$z\bot y \bot x \in L$

$z\bot y$$3nc$$\Gamma$${n \choose n/2}$$x's$$x_1,x_2$

1. $n/2$$x_1$$x_2$
2. $n/2$$x$$x_1$$x_2$$x_1,x_2$$n$$2^{0.8n}$$^2$$x_1,x_2$$(3.5cn)^{|\Gamma|}|Q|$$^3$

$z\bot y \bot x_1^px_2^s$$x_1^p$$x$$n/2$$x_2^s$$x_2$$x_1^px_2^s$$x_1$$x_2$$\#_0(y)$$x_1$$x_2$

$^1$
$^2$ ^{$x_1$$n/2$$n/4$$\log {n \choose k} \approx nH(k/n)$$H()$$H(1/4) \approx 0.81$${n \choose n/4} > 2^{0.8n}$$n$}
$^3$ ^{$\Gamma$$|\Gamma|^n$$n$$n$${n+1 \choose |\Gamma|-1}\approx n^{|\Gamma|}$$|\Gamma|$}