Pushdown-Automat, zwei Sprachen sind möglich (ODER-Bedingung)

Question

In den Hausaufgaben mussten wir einen Pushdown-Automaten für 2 Sprachen bauen, aber meiner Meinung nach sind dies zwei Übungen, bei denen der Automat für beide gleich ist.

So wie ich es verstehe, können wir einen nicht deterministischen Pushdown-Automaten bauen, und jedes Mal, wenn wir das Zeichen a lesen, können wir entweder ein einzelnes A oder zweimal A einfügen - nach dem Ermessen des Automaten.

Als nächstes wird ein Zustand für das Zeichen b erstellt, der jedes Mal, wenn er A liest, aus dem Stapel gezogen wird. Auf diese Weise weiß der Automat, wie er mit beiden Sprachen umgeht, bei denen die Menge von a gleich der Menge von b ist, und auch mit Sprachen, bei denen wie a die doppelte Menge von b ist.

Habe ich recht? Oder fehlt mir etwas?

Wenn nicht, würde ich gerne verstehen, wie man in der ersten Übung mit dem „oder“ umgeht.

Vielen Dank.

Answer 1

Schon seit $L_2\ne L_3$Sie können eindeutig nicht von demselben Pushdown-Automaten akzeptiert werden. Es hört sich so an, als hätten Sie einen Automaten im Sinn, der erkennt$L_3$. Wahrscheinlich der einfachste Weg, einen zu erkennen$L_2$ist es, zwei deterministische Pushdown-Automaten zu entwerfen, eine für $\{a^nb^n:n\in\Bbb N\}$ und eine für $\{a^{2n}b^n:n\in\Bbb N\}$. Kombinieren Sie sie dann zu einem einzigen Pushdown-Automaten mit Übergängen$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ und $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, wo $q_0$ ist der Ausgangszustand des kombinierten PDA, $Z$ ist das anfängliche Stapelsymbol und $q_1$ und $q_2$sind die Ausgangszustände der beiden Tochter-Pushdown-Automaten. Mit anderen Worten, das erste, was der kombinierte PDA tut, ist die Auswahl, ob nach einem Wort dieses Typs gesucht werden soll$a^nb^n$ oder ein Wort des Typs $a^{2n}b^n$und dann verfolgt es diese Wahl deterministisch.