automat przesuwający, możliwe są dwa języki (warunek LUB)
W zadaniu domowym musieliśmy zbudować automat przesuwający dla 2 języków, ale moim zdaniem są to dwa ćwiczenia, dla których automat jest taki sam dla obu.

Jak rozumiem, możemy zbudować niedeterministyczny automat przesuwający w dół i za każdym razem, gdy czytamy znak a, możemy wstawić jedno A lub dwa A - według „uznania” automatu.
Następnie dla postaci b budowany jest stan, który za każdym razem, gdy czyta A, wyciąga go ze stosu. W ten sposób automat wie, jak obsłużyć oba języki, w których liczba a jest równa liczbie b, a także języki, w których wartość „a” jest dwa razy większa niż liczba b.
Czy mam rację? A może coś mi brakuje?
Jeśli nie, chciałbym zrozumieć, jak radzić sobie z warunkiem „lub” w pierwszym ćwiczeniu.
Dziękuję Ci.
Odpowiedzi
Od $L_2\ne L_3$, wyraźnie nie mogą być zaakceptowane przez ten sam automat przesuwający. Wygląda na to, że masz na myśli automat, który rozpoznaje$L_3$. Prawdopodobnie najłatwiejszy sposób zaprojektowania takiego do rozpoznania$L_2$, to zaprojektować dwa deterministyczne automaty przesuwające, jeden dla $\{a^nb^n:n\in\Bbb N\}$ i jeden dla $\{a^{2n}b^n:n\in\Bbb N\}$. Następnie połącz je w jeden automat przesuwający z przejściami$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ i $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, gdzie $q_0$ to stan początkowy połączonego PDA, $Z$ jest początkowym symbolem stosu, a $q_1$ i $q_2$są stanami początkowymi dwóch pomocniczych automatów przesuwających w dół. Innymi słowy, pierwszą rzeczą, jaką robi połączony PDA, jest „wybór”, czy szukać słowa tego typu$a^nb^n$ lub słowo tego typu $a^{2n}b^n$, a następnie dąży do tego wyboru w sposób deterministyczny.