Unäre Sprachen, die von deterministischen Gegenautomaten erkannt werden

2dcas (bidirektionale deterministische Ein-Zähler-Automaten) (Petersen, 1994) können die folgende unäre Sprache erkennen:

P O W E R = {0^{2^{n}} ∣ n \geq 0} .

$\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation}$

Gibt es eine andere nichttriviale Sprache, die von 2dca erkannt wird?

Beachten Sie, dass noch nicht bekannt ist, ob 2dca . $\mathtt{SQUARE} = \lbrace 0^{n^2} \mid n \geq 0 \rbrace$

DEFINITION: Ein 2dca ist ein deterministischer endlicher Zwei-Wege-Automat mit einem Zähler. Ein 2dca kann testen, ob der Wert des Zählers Null ist oder nicht, und den Wert des Zählers in jedem Schritt um 1 erhöhen oder verringern.

fl.formal-languages automata-theory counter-automata Abuzer Yakaryilmaz
quelle

Könnten Sie einen Link zu einer Definition einer 2DCA hinzufügen?

Suresh Venkat

@SureshVenkat: Ich habe eine Referenz und auch eine Definition hinzugefügt.

Abuzer Yakaryilmaz

@AbuzerYakaryilmaz: für jedes festgelegte

erkennt es

k

$k$

{0^{k^{n}} : n \geq 0}

$\{0^{k^n} : n \geq 0\}$

Marzio De Biasi

@MarzioDeBiasi: Der Algorithmus für

kann leicht verallgemeinert werden , um

, wobei

. Daher sind diese Sprachen für mich ziemlich trivial.

P O W E R

$\mathtt{POWER}$

P O W E R_{k} = {0^{k^{n}} ∣ n \geq 0}

$\mathtt{POWER_k} = \{0^{k^n} \mid n \geq 0\}$

k \geq 3

$k \geq 3$

Abuzer Yakaryilmaz

Hm, in der Tat denke ich, dass ich auf diese Weise zu der gleichen Beobachtung komme, die Marzio bereits gemacht hat, also nichts Neues in dem, was ich gesagt habe. Ich bin jedoch immer noch daran interessiert, ob wir den Endmarker mehr als eine begrenzte Anzahl von Malen lesen müssen.

Domotorp

Antworten:

Dies ist nur eine Idee, die mir beim Lesen von Marvin L. Minsky, "Rekursive Unlösbarkeit des Post'schen Tag-Problems und anderer Themen in der Theorie der Turing-Maschinen", in den Sinn gekommen ist. insbesondere der berühmte Satz Ia:

Theorem Ia: Wir können jede partielle rekursive Funktion durch ein Programm darstellen, das mit zwei ganzen Zahlen und indem wir Anweisungen der folgenden Formen verwenden: (i) ADDIERE 1 zu und gehe zu ( ii) SUBTRAKTIERE 1 von , wenn und gehe zu , andernfalls gehe zu Das heißt, wir können ein solches Programm konstruieren, das mit beginnt $f(n)$ $S_1$ $S_2$ $I_j$
$S_j$ $I_{j_1}$
$S_j$ $S_j \neq 0$ $I_{j_1}$ $I_{j_2}$
und und endet schließlich mit und $S_1 = 2^n$ $S_2 = 0$ $S_1 = 2^{f(n)}$ $S_2 = 0$

Wenn Sie einen Zwei-Wege-DFA mit einem Zähler über einem (halb-) unendlichen Band haben, dessen Eingabe unär gegeben ist: dann kann der DFA: $\$1^{2^n}000...$

lese die unäre Eingabe (und speichere sie im Zähler);
Bearbeiten Sie den Teil des Bandes und verwenden Sie den Abstand von der s als zweiten Zähler. $0^\infty$ $1$

So kann eine Turing-Maschine mit zwei Zählern simuliert werden.

$f(n)$ $T(n)$ $\$1^m\$ \;$ $m = 2^n3^{T'(n)}$ $T'(n) \gg T(n)$

lese die unäre Eingabe (und speichere sie im Zähler);
kehre zum Symbol ganz links zurück;
$2^n$ $q_{z_0}, q_{z_1}, q_{z_2}$ $q_{z_0}$ $q_{z_1}$ $q_{z_2}$
$2^n$
$2^{f(n)}$ $T'(n)$ $\$$

Mit der oben beschriebenen speziellen Eingabecodierung, die genügend Platz auf dem endlichen Band bietet, kann ein Zweiwege-DFA mit einem Zähler und einem unären Alphabet jede rekursive Funktion berechnen.

$T'(n) \gg T(n)$ $k \gg 2$ $1^m$ $m = 2^n k^n$

Marzio De Biasi
quelle

-1

Mit nicht-trivial meine ich eine Sprache L, die von einem 1dca nicht akzeptiert werden kann. Hier scheint eine solche Sprache zu sein:

MITTE = {w | w ist über {0,1} * und w = x1y für einige x, y, so dass | x | = | y |}

Diese Sprache kann von 1dca nicht akzeptiert werden, kann aber von 1nca akzeptiert werden. Es kann von einem 2dca akzeptiert werden. Details bleiben als Übung.

user14004
quelle

$ 1^{n} $

$\$1^n\$$