In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add a new top symbol to the stack. A deterministic pushdown automaton is effectively a particular type of pushdown automaton, namely ones that have at most one transition for the same combination of input symbol, state, and top stack symbol.

PropertyValue
dbpprop:abstract
  • In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add a new top symbol to the stack. A deterministic pushdown automaton is effectively a particular type of pushdown automaton, namely ones that have at most one transition for the same combination of input symbol, state, and top stack symbol. Technically however, the notion of determinism for pushdown automata is more complicated than for finite automata as the transition is determined by both state and top stack symbol. This means that if we omit the stack from a deterministic pushdown automaton we usually end up with a nondeterministic finite automaton. The term "pushdown" refers to the fact that the stack can be regarded as being "pushed down" like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A stack automaton, by contrast, does allow operations on other elements, and stack automata can recognize a strictly larger set of languages than pushdown automata. A deterministic context-free language is a language recognized by some deterministic pushdown automaton. Not all context-free languages are deterministic. This is unlike the situation for deterministic finite automata, which are also a subset of the nondeterministic finite automata but can recognize the same class of languages (as demonstrated by the subset construction).
  • Deterministyczny automat ze stosem (DPDA, ang. deterministic pushdown automaton) to automat ze stosem, którego funkcja przejść spełnia dodatkowy warunek: Dla każdego <math>q \in Q, a \in \Sigma, x \in \Phi</math>, mamy <math>\sharp \delta(q,a,x) \leqslant 1</math>. Dla każdego <math>q \in Q, x \in \Phi</math>, jeśli <math>\delta(q,\epsilon,x) \not= \empty</math>, to dla każdego <math>a \in \Sigma</math> zachodzi <math>\delta(q,a,x)= \empty</math>. Innymi słowy, deterministyczny automat ze stosem ma możliwość co najwyżej jednego przejścia z dowolnej konfiguracji <math>(q,a,x) \in Q \times (\Sigma \cup \left \{ \epsilon \right \}) \times \Phi</math> oraz jeżeli jest określone przejście dla pewnego stanu i symbolu na stosie pod wpływem słowa pustego <math>\epsilon</math>, to wówczas jest ono jedynym możliwym przejściem dla tego układu w tym automacie.
  • 在自动机理论中，确定下推自动机是可以使用了持有数据的栈的确定有限状态自动机。术语“下推”来自原型机械自动机物理上接触穿孔卡片来阅读其内容的下推动作。术语“确定下推自动机”(DPDA)当前指称识别确定上下文无关语言的抽象计算设备。 确定下推自动机是减弱版本的下推自动机。
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add a new top symbol to the stack. A deterministic pushdown automaton is effectively a particular type of pushdown automaton, namely ones that have at most one transition for the same combination of input symbol, state, and top stack symbol.
  • Deterministyczny automat ze stosem (DPDA, ang. deterministic pushdown automaton) to automat ze stosem, którego funkcja przejść spełnia dodatkowy warunek: Dla każdego <math>q \in Q, a \in \Sigma, x \in \Phi</math>, mamy <math>\sharp \delta(q,a,x) \leqslant 1</math>.
  • 在自动机理论中，确定下推自动机是可以使用了持有数据的栈的确定有限状态自动机。术语“下推”来自原型机械自动机物理上接触穿孔卡片来阅读其内容的下推动作。术语“确定下推自动机”(DPDA)当前指称识别确定上下文无关语言的抽象计算设备。 确定下推自动机是减弱版本的下推自动机。
rdfs:label
  • Deterministic pushdown automaton
  • Deterministyczny automat ze stosem
  • 确定下推自动机
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of