filipg/amu_automata_2011 — Issue #100: Zaimplementować nierekurencyjny, stosowy algorytm sprawdzania, czy automat niedeterministyczny akceptuje dany napis
Author: filipg
Created: 2011-10-19 06:25:06+00:00
State: open

Klasa ma nazywać się `AutomatonByStack`, interfejs analogiczny jak opisano w zadaniu #99 (z tym, że tym razem *NIE* powinno dojść do przepełnienia stosu). Podobnie jak rozwiązanie zadania #99 klasa nie powinna uwzględniać epsilon-przejśc.

Pseudokod algorytmu

01. q := stan początkowy
02. w := napis wejściowy
03. odłóż na stosie parę [q,w]
04. dopóki stos jest niepusty
05. zdejmij ze stosu element - parę [r, v]
06. jeśli napis v jest pusty wtedy
07. jeśli stan r jest stanem akceptującym zwróć TRUE
08. w przeciwnym razie
09. a := pierwszy symbol napisu v
10. u := reszta napisu v (bez pierwszego symbolu)
11. dla każdego przejścia od stanu r przez symbol a
12. p := stan docelowy danego przejścia
13. odłóż na stosie [p,u]
14. zwróć FALSE