Deterministyczny automat ze stosem
Deterministyczny automat ze stosem (DPDA, ang. deterministic pushdown automaton) – automat ze stosem, którego funkcja przejść spełnia dodatkowy warunek:
- Dla każdego mamy
- Dla każdego jeśli to dla każdego zachodzi
Innymi słowy, deterministyczny automat ze stosem ma możliwość co najwyżej jednego przejścia z dowolnej konfiguracji oraz jeżeli jest określone przejście dla pewnego stanu i symbolu na stosie pod wpływem słowa pustego to wówczas jest ono jedynym możliwym przejściem dla tego układu w tym automacie.
- p
- d
- e
Teoria automatów: języki formalne i gramatyki formalne
Hierarchia Chomsky’ego |
|
---|---|
Gramatyka formalna |
|
Język formalny |
|
Minimalny automat akceptujący |
|