Przesuwanie/popping stack w odwrotnej kolejności w automatach ze stosem

Question

Więc uczę się na test, który wymyśliłem na automatach i językach bezkontekstowych i utknąłem na tej jednej konstrukcji.

Mam wszystkie części tego automatu całkowicie działa idealnie, z wyjątkiem jednej części, które wyjaśnię poniżej.

Językiem, który musi rozpoznać, jest: {x # y # z # w | x, y, z, w {0, 1} + zx ≠ w i y ≠ z}.

Więc problem, który mam, polega na porównaniu Xi do Wi, ponieważ elementy Wi nie są znane w chwili, gdy automat przechodzi do przetwarzania W, sposób, w jaki go zaprojektowałem.

Jeśli przechowuję zawartość X, gdy nadejdzie czas na wyskoczenie i porównanie każdego elementu z tymi w W, wyskoczą w odwrotnej kolejności i dlatego uznają 000111 i 111000 za ten sam ciąg, a PDA odrzuci , kiedy powinna wyraźnie zaakceptować (są to różne ciągi). To tylko jeden z przykładów, spowoduje to również niepoprawną analizę innych danych wejściowych.

Jeśli istnieje sposób na przesuwanie zawartości X na stos w odwrotnej kolejności, wyskakują w oryginalnej formie, co pozwala mi poprawnie porównać zawartość napisów.

Jeśli istnieje sposób na odwrócenie zawartości stosu po normalnym naciśnięciu, to również pozwoli mi dojść do rozwiązania.

Każda pomoc zostanie bardzo doceniona. Dzięki.

Answer 1

Rozwiązanie jest nieco trudne.

W rzeczywistości nie ma możliwości odwrócenia zawartości stosu w urządzeniu PDA. Chodzi o niedeterministyczną naturę npdy, która sprawia, że ​​problem ten można rozwiązać.

start z tej prostszej wersji

L = {x#w: x,w in {0,1}+ and x≠w}. 

Rozwiązanie:

Zacznij stan q. naciskasz $ dla każdej litery x til listu k'th (k nie jest ważne, wybrać k zakaz deterministyczny), a następnie zbadać list k'th i przejdź do q0 czy to lub przejść do q1 jeśli był to . Zignoruj ​​pozostałe x, aż osiągniesz #. Pop a $ dla każdej litery w, aż dotrzesz do dołu stosu (na przykład z). Sprawdź literę k'th w. Jeśli [byłaś na q0 a list nie był ] lub [byłaś na Q1 i list nie był ] zaakceptować.

To wszystko, czarodziejstwo!