automa pushdown, sono possibili due lingue (condizione OR)

Question

Nei compiti a casa dobbiamo costruire un automa pushdown per 2 lingue, ma a mio parere si tratta di due esercizi per i quali l'automa è lo stesso per entrambi.

A quanto ho capito, possiamo costruire un automa pushdown non deterministico, e ogni volta che leggiamo il carattere a, possiamo inserire una singola A o due volte A - a "discrezione" dell'automa.

Successivamente, viene creato uno stato per il carattere b, che ogni volta che legge A lo estrae dalla pila. In questo modo, l'automa sa come gestire sia le lingue in cui la quantità di a è uguale alla quantità di b, sia le lingue in cui come a è il doppio della quantità di b.

Ho ragione? Oppure mi sfugge qualcosa?

In caso contrario, mi piacerebbe capire come affrontare la condizione "o" nel primo esercizio.

Grazie.

Answer 1

Da $L_2\ne L_3$, chiaramente non possono essere accettati dallo stesso automa pushdown. Sembra che tu abbia in mente un automa che riconosce$L_3$. Probabilmente il modo più semplice per progettarne uno da riconoscere$L_2$, è progettare due automi pushdown deterministici, uno per $\{a^nb^n:n\in\Bbb N\}$ e uno per $\{a^{2n}b^n:n\in\Bbb N\}$. Quindi uniscili in un unico automa pushdown che ha transizioni$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ e $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, dove $q_0$ è lo stato iniziale del PDA combinato, $Z$ è il simbolo dello stack iniziale e $q_1$ e $q_2$sono gli stati iniziali dei due automi pushdown sussidiari. In altre parole, la prima cosa che fa il PDA combinato è "scegliere" se cercare una parola del tipo$a^nb^n$ o una parola del genere $a^{2n}b^n$, e quindi persegue quella scelta in modo deterministico.