Deterministic pushdown automaton (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages. Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top. A deterministic pushdown automaton has at most one legal transition for the same combination of input symbol, state, and top stack symbol. This is where it differs from the nondeterministic pushdown automaton. (en) 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. (pl) Na teoria dos autômatos, um autômato com pilha determinístico (APD) é uma variante de autômato com pilha . O APD aceita as ,um subconjunto próprio de . As transições da máquina são baseadas no estado atual e no símbolo de entrada, e também do símbolo mais alto na pilha. Os símbolos mais inferiores na pilha não estão visíveis e não provocam efeitos imediatos. As ações da máquina incluem colocar símbolo na pilha, retirá-lo da pilha ou substituir o topo da pilha. Um autômato com pilha determinístico tem no máximo uma transição possível para uma mesma combinação de símbolo de entrada, estado e símbolo no topo da pilha. Isto é o que o difere de um autômato com pilha não determinístico. (pt) 在自动机理论中，确定下推自动机是可以使用了持有数据的栈的确定有限状态自动机。术语“下推”来自原型机械自动机物理上接触穿孔卡片来阅读其内容的下推动作。术语“确定下推自动机”（DPDA）当前指称识别确定上下文无关语言的抽象计算设备。 确定下推自动机是减弱版本的下推自动机。 (zh) |
| dbo:wikiPageExternalLink | https://archive.org/details/logiclanguagemod00hamb/page/n289 |
| dbo:wikiPageID | 3972656 (xsd:integer) |
| dbo:wikiPageLength | 8891 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1099377665 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_set dbr:Pushdown_automaton dbr:Deterministic_context-free_language dbr:Empty_string dbr:Context-free_language dbr:Dana_S._Richards dbr:Gödel_Prize dbc:Automata_(computation) dbc:Formal_languages dbc:Models_of_computation dbr:Automata_theory dbr:Kleene_star dbr:Palindrome dbr:LL(1)_language dbr:Deterministic_context-free_languages |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:Reflist dbt:Formal_languages_and_grammars |
| dct:subject | dbc:Automata_(computation) dbc:Formal_languages dbc:Models_of_computation |
| gold:hypernym | dbr:Variation |
| rdf:type | yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo dbo:Food yago:Whole100003553 |
| rdfs:comment | 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. (pl) Na teoria dos autômatos, um autômato com pilha determinístico (APD) é uma variante de autômato com pilha . O APD aceita as ,um subconjunto próprio de . As transições da máquina são baseadas no estado atual e no símbolo de entrada, e também do símbolo mais alto na pilha. Os símbolos mais inferiores na pilha não estão visíveis e não provocam efeitos imediatos. As ações da máquina incluem colocar símbolo na pilha, retirá-lo da pilha ou substituir o topo da pilha. Um autômato com pilha determinístico tem no máximo uma transição possível para uma mesma combinação de símbolo de entrada, estado e símbolo no topo da pilha. Isto é o que o difere de um autômato com pilha não determinístico. (pt) 在自动机理论中，确定下推自动机是可以使用了持有数据的栈的确定有限状态自动机。术语“下推”来自原型机械自动机物理上接触穿孔卡片来阅读其内容的下推动作。术语“确定下推自动机”（DPDA）当前指称识别确定上下文无关语言的抽象计算设备。 确定下推自动机是减弱版本的下推自动机。 (zh) In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages. (en) |
| rdfs:label | Deterministic pushdown automaton (en) Deterministyczny automat ze stosem (pl) Autômato com pilha determinístico (pt) 确定下推自动机 (zh) |
| owl:sameAs | freebase:Deterministic pushdown automaton yago-res:Deterministic pushdown automaton wikidata:Deterministic pushdown automaton http://bs.dbpedia.org/resource/Deterministički_potisni_automat dbpedia-fa:Deterministic pushdown automaton dbpedia-hr:Deterministic pushdown automaton dbpedia-pl:Deterministic pushdown automaton dbpedia-pt:Deterministic pushdown automaton dbpedia-sr:Deterministic pushdown automaton dbpedia-zh:Deterministic pushdown automaton https://global.dbpedia.org/id/3VoVP |
| prov:wasDerivedFrom | wikipedia-en:Deterministic_pushdown_automaton?oldid=1099377665&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Deterministic_pushdown_automaton |
| is dbo:wikiPageDisambiguates of | dbr:DPA |
| is dbo:wikiPageRedirects of | dbr:Deterministic_pushdown_automata dbr:DPDA dbr:NDPDA |
| is dbo:wikiPageWikiLink of | dbr:Pushdown_automaton dbr:Richard_E._Stearns dbr:Deterministic_context-free_grammar dbr:Deterministic_context-free_language dbr:Context-free_grammar dbr:Context-free_language dbr:Equivalence_problem dbr:LL_parser dbr:Deterministic_pushdown_automata dbr:Polish_notation dbr:Gödel_Prize dbr:DPA dbr:Géraud_Sénizergues dbr:Automata_theory dbr:DPDA dbr:SC_(complexity) dbr:Nested_word dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Palindrome dbr:NDPDA |
| is foaf:primaryTopic of | wikipedia-en:Deterministic_pushdown_automaton |