Ist {a ^ n (a + b) ^ n | n> 0} eine deterministische CFL?

$L = \{ a^n (a+b)^n | n>0\}$

Ein Buch, das ich lese, sagt es ist, aber wenn man bedenkt, dass wir nicht wissen können, wo der zweite Teil beginnen wird, und es könnte auch mit einem beginnen, wie können wir dies dann mit einem DPDA akzeptieren? Wie können wir nach dem Lesen des ersten Teils ( ) sicher sein, dass es das Ende des ersten Teils ist oder wenn wir nicht berücksichtigen, dass der zweite Teil auch mit $a^n$ $a?$

Ist das deterministisch?

formal-languages automata context-free pushdown-automata John P.
quelle

Antworten:

Sie müssen das Ende des "ersten Teils" nicht bestimmen.

Hinweis ist genau der Satz von Zeichenfolgen, die die folgenden drei Einschränkungen erfüllen: $L$

Seine Länge ist gerade.
Es enthält nur und . $a$ $b$
Das erste erscheint in der zweiten Hälfte. $b$

Die Einschränkungen 1 und 2 sind leicht zu überprüfen. Um die Einschränkung 3 zu überprüfen, kann der DPDA jedes Mal, wenn er ein Zeichen liest, ein Symbol auf seinen Stapel verschieben, bis das erste erscheint (ausgenommen), und dann jedes Mal, wenn er ein Zeichen liest, ein Symbol einfügen. Die Einschränkung 3 ist genau dann erfüllt, wenn das anfängliche Stapelsymbol während des Popping-Vorgangs nie gelesen wird. $b$

xskxzr
quelle

Vielen Dank für die Antwort. Also sollten wir in der DPDA jedes Mal, wenn wir ein Zeichen lesen, einen Ball drücken, bis wir das erste b erreichen, aber auf diese Weise wird die Zeichenfolge aaab nicht akzeptiert, oder? denn wenn wir das erste b erreichen, haben wir 3 Bälle und wir werden nur 1 Ball platzen lassen und der Stapel ist nicht leer, vorausgesetzt wir akzeptieren ohne den leeren Stapel, wann werden wir dann in den Endzustand gehen? Wenn der Stapel nicht leer ist und keine Eingabe mehr verfügbar ist?

John P

@JohnP Es tut mir leid, dass ich die formale Beschreibung eines PDA nicht gelesen habe, daher kann die Antwort vor dem Bearbeiten verwirrend sein. Jetzt habe ich die Antwort geändert, um sie mit der formalen Definition in Wikipedia kompatibel zu machen . Wenn der Automat das anfängliche Stapelsymbol liest, wandelt er sich in einen speziellen Zustand um, der "Zurückweisen" darstellt (dann Schleife für die restlichen Eingaben), und alle anderen Zustände akzeptieren Zustände (mit Ausnahme des Startzustands, da ).

n > 0

$n>0$

xskxzr

Ich bin nicht sicher, wie alle Einschränkungen überprüft werden können, ohne den Determinismus zu verlieren. Können Sie Übergangsfunktionen andeuten oder mitteilen?

Herr Sigma.

@ Rohith. Erstens ist es in dem Zustand A und , wenn die Eingabe , drückt ein Symbol. Wenn die Eingabe , wechseln Sie zu Status B und setzen Sie ein Symbol. In Zustand B wird jedes Mal, wenn oder angezeigt wird, ein Symbol angezeigt.

a

$a$

b

$b$

a

$a$

b

$b$

xskxzr

Wann soll ich anfangen zu knallen, wenn ?

w = a^{2 n}

$w=a^{2n}$

Herr Sigma.

Falls es klarer ist, hier ist eine CFG, die der DPDA von xskxzr entspricht:

\begin{aligned} S & \to ϵ \\ S & \to B \\ S & \to a a S \\ B & \to a b \\ B & \to a B a \\ B & \to a B b \end{aligned}

$\begin{align} S&\to \epsilon \\ S&\to B \\ S&\to a a S \\ B&\to a b \\ B&\to a B a \\ B&\to a B b \\ \end{align}$

Das etwas einfachere CFG unten ist für Eingaben, die nur aus einer geraden Zahl von s bestehen, nicht eindeutig , funktioniert jedoch weiterhin mit dem LALR (1) -Algorithmus unter Verwendung des "Standard" -Konfliktlösungsalgorithmus: "Bei Mehrdeutigkeit Verschiebung": $a$

\begin{aligned} S & \to B \\ S & \to a a S \\ B & \to ϵ \\ B & \to a B a \\ B & \to a B b \end{aligned}

$\begin{align} S&\to B \\ S&\to a a S \\ B&\to \epsilon \\ B&\to a B a \\ B&\to a B b \\ \end{align}$

Rici
quelle