Automat ze stosem
Z Wikipedii
W teorii obliczeń, automat ze stosem (PDA, ang. pushdown automata) to automat skończony który może dodatkowo korzystać ze stosu do przechowywania danych. Domyślnie przyjmuje się że ten automat jest automatem niedeterministycznym. Takie automaty są równoważne pod względem siły wyrazu gramatykom bezkontekstowym, rozpoznając języki bezkontekstowe. Jeśli nie dopuszcza się możliwości niedeterminizmu, otrzymuje się nieznacznie słabszy model obliczeń nazywany deterministycznymi automatami ze stosem.
Wyposażenie automatu skończonego w dwa stosy zamiast jednego, daje model obliczeń równoważny maszynie Turinga.
[edytuj] Definicja
Automat ze stosem definiuje się jako siódemkę (Q,Σ,Φ,σ,s,Ω,F), gdzie:
- Q jest skończonym zbiorem stanów
- Σ jest skończonym alfabetem symboli wejściowych
- Φ jest skończonym alfabetem symboli stosowych
- σ jest skończonym zbiorem dopuszczalnych przejść
jest stanem początkowym- Ω jest (opcjonalnym) początkowym elementem na stosie
jest zbiorem stanów końcowych
W literaturze spotyka się dwa kryteria akceptacji wejściowego ciągu: akceptacja przez pusty stos i akceptacja przez stan końcowy. Łatwo pokazać że te dwa kryteria są równoważne: stan końcowy może w pętli zawsze czyścić stos do końca, a automat może łatwo wykryć pusty stos i wejść w stan końcowy gdy odczyta unikalny symbol umieszczany tam wyłącznie w stanie początkowym.
