automate pushdown, deux langues sont possibles (condition OR)

Question

En devoirs, nous avons pu construire un automate pushdown pour 2 langues, mais à mon avis, ce sont deux exercices pour lesquels l'automate est le même pour les deux.

Si je comprends bien, nous pouvons construire un automate de refoulement non déterministe, et chaque fois que nous lisons le caractère a, nous pouvons insérer un seul A ou deux fois A - à la «discrétion» de l'automate.

Ensuite, un état est construit pour le caractère b, qui chaque fois qu'il lit A il le sortira de la pile. De cette façon, l'automate sait gérer les deux langues où la quantité de a est égale à la quantité de b, et aussi les langues où comme a est deux fois la quantité de b.

Ai-je raison? Ou est-ce que je manque quelque chose?

Sinon, j'aimerais bien comprendre comment gérer la condition «ou» dans le premier exercice.

Je vous remercie.

Answer 1

Depuis $L_2\ne L_3$, ils ne peuvent clairement pas être acceptés par le même automate de refoulement. On dirait que vous avez en tête un automate qui reconnaît$L_3$. Probablement le moyen le plus simple d'en concevoir un pour reconnaître$L_2$, consiste à concevoir deux automates de refoulement déterministes, un pour $\{a^nb^n:n\in\Bbb N\}$ et un pour $\{a^{2n}b^n:n\in\Bbb N\}$. Ensuite, combinez-les en un seul automate pushdown qui a des transitions$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ et $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, où $q_0$ est l'état initial du PDA combiné, $Z$ est le symbole initial de la pile, et $q_1$ et $q_2$sont les états initiaux des deux automates de refoulement subsidiaires. En d'autres termes, la première chose que fait le PDA combiné est de `` choisir '' s'il faut rechercher un mot du type$a^nb^n$ ou un mot du type $a^{2n}b^n$, puis il poursuit ce choix de manière déterministe.