In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data.
| Property | Value |
|---|
| dbpedia-owl:abstract
|
- Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik. Es handelt sich um ein rein theoretisches Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen – ob es tatsächlich möglich oder sinnvoll wäre, eine solche Maschine zu bauen, ist dabei unerheblich. Bei einem Kellerautomaten handelt es sich um einen endlichen Automaten, der um einen Kellerspeicher erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine.
- In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data.
- 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.
- Pinoautomaatti on deterministisen äärellisen automaatin (DFA) yleistys, johon liittyy myös pino. Pinoautomaatti on ilmaisuvoimaisempi kuin DFA. Sillä voidaan tunnistaa yhteysriippumaton eli kontekstivapaa kieli. Kuten äärellinen automaatti mallinnetaan tilojen ja niiden välisten siirtymien joukkona, pinoautomaatti lisää tähän pinon siten, että jokaiseen siirtymään voi liittyä sen siirtymän lisäksi uuden alkion lisääminen pinoon, vanhan alkion lukeminen pinosta pois, molemmat tai pinon pitäminen sellaisenaan. Näistä operaatioista symbolin asettaminen pinoon voidaan suorittaa vapaasti siirtymän yhteydessä, mutta sellainen siirtymä, joka lukisi symbolin pinosta voidaan tehdä, jos ja vain jos pinon päällimmäisenä on jo luettava symboli. Pinoautomaatin graafinen mallinnus noudattaa myös tyypillisesti äärellisen automaatin mallia; siihen vain lisätään kaariin jokin merkintätapa pinon operaatioille. Tyypillisesti merkintä on sellainen, että kaaren nimen lähettyvillä on merkitty pino-operaatiot muodossa 'lukusymboli/kirjoitussymboli'. Toimintoa, jota ei tehdä, merkitään pinosymbolissakin epsilonilla 'ε' tai lambdalla 'λ', joka tiukan teoreettisen tulkinnan mukaan tarkoittaisi, että pinoon kirjoitetaan tai siitä luetaan ei-mitään.
- Un automa a pila o Push Down Automa (PDA) è una macchina astratta adatta a riconoscere ed accettare quei linguaggi che nelle grammatiche formali sono detti liberi da contesto (o di tipo 2, o non contestuali, o context-free). Il nome di tale macchina deriva dal fatto che come memoria di lavoro utilizza una struttura dati detta stack.
- プッシュダウン・オートマトン（Pushdown Automaton）は、オートマトンの一種で文脈自由言語を認識する抽象デバイスである。 ある意味では、プッシュダウン・オートマトンはスタックを使った有限オートマトンである。
- Een stapelautomaat, ofwel een push-down automaat (PDA), is een eindige automaat die gebruik maakt 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.
- W teorii obliczeń, automat ze stosem (PDA, ang. pushdown automaton) to 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)是使用了包含数据的栈的有限自动机。
- В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.
- 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 semblable à un automate fini mais il dispose également d'une pile. Ainsi, un automate à pile prend en entrée un mot et réalise une série de transitions, chacune consistant à lire une lettre du mot ou à réaliser des opérations sur la pile. Les transitions effectuées dépendent des lettres du mot et du sommet de la pile. Selon l'état de l'automate à la fin du calcul, le mot peut être accepté ou refusé. La puissance de calcul des automates à piles correspond aux langages non-contextuels soit ceux qui peuvent être décrits par une grammaire hors-contexte.
|
| dbpedia-owl:thumbnail
| |
| dbpedia-owl:wikiPageExternalLink
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data.
- 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 Push Down Automa (PDA) è una macchina astratta adatta a riconoscere ed accettare quei linguaggi che nelle grammatiche formali sono detti liberi da contesto (o di tipo 2, o non contestuali, o context-free). Il nome di tale macchina deriva dal fatto che come memoria di lavoro utilizza una struttura dati detta stack.
- プッシュダウン・オートマトン（Pushdown Automaton）は、オートマトンの一種で文脈自由言語を認識する抽象デバイスである。 ある意味では、プッシュダウン・オートマトンはスタックを使った有限オートマトンである。
- Een stapelautomaat, ofwel een push-down automaat (PDA), is een eindige automaat die gebruik maakt 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.
- 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)是使用了包含数据的栈的有限自动机。
- В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.
- Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik. Es handelt sich um ein rein theoretisches Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen – ob es tatsächlich möglich oder sinnvoll wäre, eine solche Maschine zu bauen, ist dabei unerheblich.
- Pinoautomaatti on deterministisen äärellisen automaatin (DFA) yleistys, johon liittyy myös pino. Pinoautomaatti on ilmaisuvoimaisempi kuin DFA. Sillä voidaan tunnistaa yhteysriippumaton eli kontekstivapaa kieli.
- W teorii obliczeń, automat ze stosem (PDA, ang. pushdown automaton) to 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.
- 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 semblable à un automate fini mais il dispose également d'une pile. Ainsi, un automate à pile prend en entrée un mot et réalise une série de transitions, chacune consistant à lire une lettre du mot ou à réaliser des opérations sur la pile. Les transitions effectuées dépendent des lettres du mot et du sommet de la pile.
|
| rdfs:label
|
- Kellerautomat
- Pushdown automaton
- Autómata con pila
- Pinoautomaatti
- Automate à pile
- Automa a pila
- プッシュダウン・オートマトン
- Stapelautomaat
- Automat ze stosem
- Autômato com pilha
- Автомат с магазинной памятью
- 下推自动机
|
| owl:sameAs
| |
| foaf:depiction
| |
| foaf:page
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
