This HTML5 document contains 167 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbthttp://dbpedia.org/resource/Template:
dbpedia-nohttp://no.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-fihttp://fi.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
dbpedia-hrhttp://hr.dbpedia.org/resource/
dbpedia-shhttp://sh.dbpedia.org/resource/
dbpedia-arhttp://ar.dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
n22https://
n10http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbpedia-mkhttp://mk.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
dbpedia-cshttp://cs.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n5https://www.elstel.org/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n20http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
n21http://www-igm.univ-mlv.fr/~berstel/Articles/
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-skhttp://sk.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbpedia-nlhttp://nl.dbpedia.org/resource/
yago-reshttp://yago-knowledge.org/resource/
n16https://global.dbpedia.org/id/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-cahttp://ca.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
n39http://bs.dbpedia.org/resource/
dbpedia-nnhttp://nn.dbpedia.org/resource/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-kohttp://ko.dbpedia.org/resource/
n41https://archive.org/details/
dbpedia-fahttp://fa.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
dbpedia-eshttp://es.dbpedia.org/resource/
owlhttp://www.w3.org/2002/07/owl#
dbpedia-kahttp://ka.dbpedia.org/resource/

Statements

Subject Item
dbr:Pushdown_automaton
rdf:type
yago:LivingThing100004258 yago:Organism100004475 yago:Object100002684 yago:WikicatModelsOfComputation yago:Person100007846 yago:Whole100003553 yago:YagoLegalActor yago:Worker109632518 yago:YagoLegalActorGeo yago:Model110324560 yago:CausalAgent100007347 yago:PhysicalEntity100001930 yago:Assistant109815790
rdfs:label
プッシュダウン・オートマトン Kellerautomat Zásobníkový automat أوتومات الدفع السفلي Автомат з магазинною пам'яттю Automate à pile Autòmat amb pila 푸시다운 자동 기계 Autómata con pila Stapelautomaat Automat ze stosem 下推自动机 Pushdown automaton Automa a pila Автомат с магазинной памятью Autômato com pilha
rdfs:comment
在自动机理论中，下推自动机（Pushdown automaton）是使用了包含数据的栈的有限自动机。 푸시다운 자동 기계(pushdown automaton, PDA)는 컴퓨터 과학에서 스택을 사용하는 자동 기계의 한 종류이다. 주로 기계에 의한 계산에 관련된 이론 분야에서 사용되며, 튜링 기계보다는 유한 상태 기계에 더 많이 사용된다. 또한 입력하면 형식 문법을 만들어 낼 수 있기 때문에, 구문 분석 디자인에도 사용된다. '푸시다운'이라는 용어는 스택이 어떤 작업이 한 요인 때문에 정지될 시 그 요인을 음식점의 식기 분출 기계처럼 밀어내리는 역할을 하는 것을 의미한다. Een stapelautomaat, ofwel een push-down-automaat (PDA), is een eindige automaat die gebruikmaakt van een stack. De klasse van formele talen die door stapelautomaten wordt geaccepteerd, is de klasse van contextvrije talen. Dat wil zeggen dat stapelautomaten even krachtig zijn als contextvrije grammatica's. В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний. Un automate à pile est une machine abstraite utilisée en informatique théorique et, plus précisément, en théorie des automates. Un automate à pile est une généralisation des automates finis : il dispose en plus d'une mémoire infinie organisée en pile (last-in/first-out ou LIFO). Un automate à pile prend en entrée un mot et réalise une série de transitions. Il effectue pour chaque lettre du mot une transition, dont le choix dépend de la lettre, de l'état de l'automate et du sommet de la pile ; il peut aussi modifier le contenu de la pile. Selon l'état de l'automate et de la pile à la fin du calcul, le mot est accepté ou refusé. Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen. Der Kellerautomat ist ein endlicher Automat, der um einen Kellerspeicher (a.g. Stack) erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine. Automat ze stosem (ang. pushdown automaton, PDA) – 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ę słabszy model automatu nazywany deterministycznym automatem ze stosem. Wyposażenie automatu skończonego w dwa stosy zamiast jednego, daje model obliczeń równoważny maszynie Turinga. Na teoria dos autômatos, um autômato com pilha é um autômato finito com uma memória auxiliar em forma de pilha. プッシュダウン・オートマトン（Pushdown Automaton）は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。 ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。 In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines (see ).Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design. Автома́т з магази́нною па́м'яттю (англ. pushdown automaton) — в теорії автоматів — скінченний автомат, що додатково використовує стек для зберігання станів. На відміну від скінченних автоматів, автомат з магазинною пам'яттю формально визначається як набір, де Автомат з магазинною пам'яттю може розпізнати будь-яку контекстно-вільну мову. في علم الحاسوب، الأوتومات الدفع السفلي أو باختصار "PDA" هو نموذج حاسوبي بسيط يقوم على فكرة بنية البيانات المكدس (stack)، حيث أنه يستخدمه بأنه ذاكرة اضافية يُخزن فيها النتائج غير نهائية ليُعيد استخدامها لاحقا ضمن العمليات المُتاحة لهذا النموذج. هنالك نوعان من أوتوماتات الدفع السفلي: أوتومات الدفع السفلي القطعي (DPA)، أوتومات الدفع السفلي غير القطعي (PDA). على خلاف النماذج الابسط أوتومات الدفع السفلي غير القطعي «اقوى» من قرينه القطعي، أي يوجد لغات التي يمكن تقريرها بواسطة PDA ولكن ليس بواسطة DPA . أوتومات الدفع السفلي عمليا هو أوتومات حالات محدودة مُزود بمكدس LIFO أي من يدخل اخرا يخرج أولا، أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 وقد كان المُكَّدس مستخدماً منذ زمن طويل، إلا أن أبحاثه نَظَّمت دمجه في أوتومات منتهي.ولعل أحد أهم المبرهنات في هذا المجال هي: لكل PDA يمكن بناء قواعد ح Zásobníkový automat (PDA z anglického pushdown automaton) je teoretický výpočetní model používaný v informatice pro studium vyčíslitelnosti a obecně formálních jazyků. Popisuje jednoduchý počítač, který má jako pracovní paměť vedle konečně stavové jednotky k dispozici zásobník. Zásobníkový automat dokáže rozpoznávat bezkontextové jazyky. Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky. Un automa a pila o (noto anche con la sigla PDA, dall'inglese pushdown automaton) è un tipo di macchina astratta, in particolare un automa la cui memoria di lavoro è costituita da una pila, una struttura dati i cui dati possono essere estratti in ordine necessariamente inverso rispetto a quello di inserimento.Un automa a pila è in grado di riconoscere ed accettare tutti i linguaggi che nella teoria delle grammatiche formali sono detti non contestuali, ovvero di tipo 2 secondo la classificazione gerarchica di Chomsky. Un autòmat amb pila és un tipus d'autòmat que utilitza una pila. Aquests autòmats s'utilitzen en teoria de la computabilitat i són més potents que un autòmat finit però menys capaços que una Màquina de Turing. Si en tot moment només és possible una i només una transició, llavors l'autòmat és un . En altre cas, és diu que l'autòmat és un autòmat amb pila general o no determinista. Els llenguatges que reconeixen els autòmats amb pila pertanyen al grup dels llenguatges lliures del context en la Jerarquia de Chomsky.
foaf:depiction
n10:Pushdown-step.svg n10:Pushdown-overview.svg n10:Pda-steps.svg n10:Pda-example.svg
dcterms:subject
dbc:Automata_(computation) dbc:Models_of_computation
dbo:wikiPageID
24510
dbo:wikiPageRevisionID
1095500677
dbo:wikiPageWikiLink
dbr:Theoretical_computer_science dbr:Context-sensitive_languages dbr:Deterministic_pushdown_automata dbr:String_(computer_science) dbr:DSPACE dbr:Ashok_K._Chandra dbr:Empty_string dbr:Stack_machine n20:Pushdown-overview.svg dbr:Theory_of_computation n20:Pushdown-step.svg dbr:Stack_(abstract_data_type) dbr:General_recursive_function dbr:Regular_language dbr:Transitive_closure dbr:Linear_bounded_automaton dbr:Recursively_enumerable dbr:Stack_(data_structure) dbr:Counter_automaton dbr:Automata_theory dbr:Parser dbr:If,_and_only_if dbr:Dexter_Kozen dbc:Automata_(computation) dbr:Deterministic_pushdown_automaton dbr:Finite-state_machine dbr:Deterministic_context-free_language dbr:Palindrome dbr:EXPTIME dbr:Turing_machine dbr:Nested_stack_automaton dbr:Larry_Stockmeyer dbr:NSPACE dbr:Conjunctive_grammar dbr:Context-free_language dbc:Models_of_computation dbr:Richard_J._Lipton dbr:Greibach_normal_form dbr:Queue_automaton dbr:Richard_E._Ladner dbr:Finite_automaton n20:Pda-example.svg n20:Pda-steps.svg dbr:Reflexive_closure dbr:Context-free_grammar
dbo:wikiPageExternalLink
n5:coan n21:1997CFLPDA.pdf n22:www.jflap.org n41:introductiontoth00sips
owl:sameAs
dbpedia-pt:Autômato_com_pilha yago-res:Pushdown_automaton n16:4uZp3 dbpedia-nl:Stapelautomaat dbpedia-ko:푸시다운_자동_기계 dbpedia-ru:Автомат_с_магазинной_памятью dbpedia-es:Autómata_con_pila dbpedia-ca:Autòmat_amb_pila dbpedia-ar:أوتومات_الدفع_السفلي dbpedia-pl:Automat_ze_stosem dbpedia-ka:Pushdown_Automata dbpedia-no:Pushdownautomat dbpedia-zh:下推自动机 dbpedia-cs:Zásobníkový_automat dbpedia-sh:Potisni_automat dbpedia-he:אוטומט_מחסנית dbpedia-uk:Автомат_з_магазинною_пам'яттю dbpedia-fr:Automate_à_pile dbpedia-fa:اتوماتون_پشته‌ای dbpedia-it:Automa_a_pila n39:Potisni_automat dbpedia-hr:Potisni_automat freebase:m.063x2 dbpedia-nn:Pushdownautomat dbpedia-ja:プッシュダウン・オートマトン dbpedia-sr:Потисни_аутомат wikidata:Q751443 dbpedia-fi:Pinoautomaatti dbpedia-sk:Zásobníkový_automat dbpedia-mk:Потисен_автомат dbpedia-de:Kellerautomat
dbp:wikiPageUsesTemplate
dbt:Tmath dbt:Rp dbt:Citation_needed dbt:Val dbt:Cite_book dbt:Short_description dbt:Ordered_list dbt:Automata_theory dbt:Reflist dbt:More_citations_needed dbt:Formal_languages_and_grammars dbt:Mvar dbt:Anchor
dbo:thumbnail
n10:Pushdown-overview.svg?width=300
dbo:abstract
Na teoria dos autômatos, um autômato com pilha é um autômato finito com uma memória auxiliar em forma de pilha. В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний. Automat ze stosem (ang. pushdown automaton, PDA) – 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ę słabszy model automatu nazywany deterministycznym automatem ze stosem. Wyposażenie automatu skończonego w dwa stosy zamiast jednego, daje model obliczeń równoważny maszynie Turinga. Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky. プッシュダウン・オートマトン（Pushdown Automaton）は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。 ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。 Zásobníkový automat (PDA z anglického pushdown automaton) je teoretický výpočetní model používaný v informatice pro studium vyčíslitelnosti a obecně formálních jazyků. Popisuje jednoduchý počítač, který má jako pracovní paměť vedle konečně stavové jednotky k dispozici zásobník. Zásobníkový automat dokáže rozpoznávat bezkontextové jazyky. في علم الحاسوب، الأوتومات الدفع السفلي أو باختصار "PDA" هو نموذج حاسوبي بسيط يقوم على فكرة بنية البيانات المكدس (stack)، حيث أنه يستخدمه بأنه ذاكرة اضافية يُخزن فيها النتائج غير نهائية ليُعيد استخدامها لاحقا ضمن العمليات المُتاحة لهذا النموذج. هنالك نوعان من أوتوماتات الدفع السفلي: أوتومات الدفع السفلي القطعي (DPA)، أوتومات الدفع السفلي غير القطعي (PDA). على خلاف النماذج الابسط أوتومات الدفع السفلي غير القطعي «اقوى» من قرينه القطعي، أي يوجد لغات التي يمكن تقريرها بواسطة PDA ولكن ليس بواسطة DPA . أوتومات الدفع السفلي عمليا هو أوتومات حالات محدودة مُزود بمكدس LIFO أي من يدخل اخرا يخرج أولا، أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 وقد كان المُكَّدس مستخدماً منذ زمن طويل، إلا أن أبحاثه نَظَّمت دمجه في أوتومات منتهي.ولعل أحد أهم المبرهنات في هذا المجال هي: لكل PDA يمكن بناء قواعد حرة السياق تنتج نفس اللغة. أهمية هذا الأوتومات تتبين من حقيقة انه يُستخدم كثيرا في عملية التجزئة (parsing) وخاصة انه أسهل للبرمجة من القواعد حرة السياق وقد تبين انهما ذوي قوة مضارعة. Un automa a pila o (noto anche con la sigla PDA, dall'inglese pushdown automaton) è un tipo di macchina astratta, in particolare un automa la cui memoria di lavoro è costituita da una pila, una struttura dati i cui dati possono essere estratti in ordine necessariamente inverso rispetto a quello di inserimento.Un automa a pila è in grado di riconoscere ed accettare tutti i linguaggi che nella teoria delle grammatiche formali sono detti non contestuali, ovvero di tipo 2 secondo la classificazione gerarchica di Chomsky. 푸시다운 자동 기계(pushdown automaton, PDA)는 컴퓨터 과학에서 스택을 사용하는 자동 기계의 한 종류이다. 주로 기계에 의한 계산에 관련된 이론 분야에서 사용되며, 튜링 기계보다는 유한 상태 기계에 더 많이 사용된다. 또한 입력하면 형식 문법을 만들어 낼 수 있기 때문에, 구문 분석 디자인에도 사용된다. '푸시다운'이라는 용어는 스택이 어떤 작업이 한 요인 때문에 정지될 시 그 요인을 음식점의 식기 분출 기계처럼 밀어내리는 역할을 하는 것을 의미한다. Un automate à pile est une machine abstraite utilisée en informatique théorique et, plus précisément, en théorie des automates. Un automate à pile est une généralisation des automates finis : il dispose en plus d'une mémoire infinie organisée en pile (last-in/first-out ou LIFO). Un automate à pile prend en entrée un mot et réalise une série de transitions. Il effectue pour chaque lettre du mot une transition, dont le choix dépend de la lettre, de l'état de l'automate et du sommet de la pile ; il peut aussi modifier le contenu de la pile. Selon l'état de l'automate et de la pile à la fin du calcul, le mot est accepté ou refusé. Les langages reconnus par les automates à piles sont exactement les langages algébriques, c'est-à-dire ceux engendrés par une grammaire algébrique. L'importance des automates à pile vient de leur emploi en analyse syntaxique des langages de programmation, et plus généralement dans la transformation de définitions ou d'algorithmes récursifs en leurs analogues itératifs. Un autòmat amb pila és un tipus d'autòmat que utilitza una pila. Aquests autòmats s'utilitzen en teoria de la computabilitat i són més potents que un autòmat finit però menys capaços que una Màquina de Turing. Si en tot moment només és possible una i només una transició, llavors l'autòmat és un . En altre cas, és diu que l'autòmat és un autòmat amb pila general o no determinista. Els llenguatges que reconeixen els autòmats amb pila pertanyen al grup dels llenguatges lliures del context en la Jerarquia de Chomsky. Автома́т з магази́нною па́м'яттю (англ. pushdown automaton) — в теорії автоматів — скінченний автомат, що додатково використовує стек для зберігання станів. На відміну від скінченних автоматів, автомат з магазинною пам'яттю формально визначається як набір, де * — скінченна множина станів автомата * — єдиний допустимий початковий стан автомата * — множина дозволених кінцевих станів, причому допускається F=Ø, і F=K * — скінченна множина символів вхідного алфавіту, з якого формуються рядки, що зчитуються автоматом * — алфавіт пам'яті (магазину чи стеку) * — нульовий символ пам'яті. * — функція переходів: Пам'ять працює як стек, тобто для зчитування доступний лише останній записаний в ній елемент. Функція переходу за комбінацією поточного стану, вхідного символу і символу на вершині магазину визначає наступний стан (і, можливо, символ для запису в магазин). У випадку, коли в правій частині автоматного правила присутній , у магазин нічого не додається, а елемент з вершини стирається. Якщо магазин порожній, то спрацьовують правила з в лівій частині. Автомат з магазинною пам'яттю може розпізнати будь-яку контекстно-вільну мову. У чистому вигляді автомати з магазинною пам'яттю використовуються вкрай рідко. Зазвичай ця модель використовується для наочного подання відмінності звичайних скінченних автоматів від синтаксичних граматик. Реалізація автоматів з магазинною пам'яттю відрізняється від кінцевих автоматів тим, що поточний стан автомата сильно залежить від будь-якого попереднього. 在自动机理论中，下推自动机（Pushdown automaton）是使用了包含数据的栈的有限自动机。 Een stapelautomaat, ofwel een push-down-automaat (PDA), is een eindige automaat die gebruikmaakt van een stack. De klasse van formele talen die door stapelautomaten wordt geaccepteerd, is de klasse van contextvrije talen. Dat wil zeggen dat stapelautomaten even krachtig zijn als contextvrije grammatica's. Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen. Der Kellerautomat ist ein endlicher Automat, der um einen Kellerspeicher (a.g. Stack) erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine. In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines (see ).Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design. 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 access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than pushdown automata.A nested stack automaton allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols.
gold:hypernym
dbr:Automaton
prov:wasDerivedFrom
wikipedia-en:Pushdown_automaton?oldid=1095500677&ns=0
dbo:wikiPageLength
26479
foaf:isPrimaryTopicOf
wikipedia-en:Pushdown_automaton