Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Deterministic pushdown automaton
Summary
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.
A (not necessarily deterministic) PDA can be defined as a 7-tuple:
where
is a finite set of states
is a finite set of input symbols
is a finite set of stack symbols
is the start state
is the starting stack symbol
where is the set of accepting, or final, states
is a transition function, where
where is the Kleene star, meaning that is "the set of all finite strings (including the empty string ) of elements of ", denotes the empty string, and is the power set of a set .
M is deterministic if it satisfies both the following conditions:
For any , the set has at most one element.
For any , if , then for every
There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). The languages accepted by empty stack are those languages that are accepted by final state and are prefix-free: no word in the language is the prefix of another word in the language.
The usual acceptance criterion is final state, and it is this acceptance criterion which is used to define the deterministic context-free languages.
If is a language accepted by a PDA , it can also be accepted by a DPDA if and only if there is a single computation from the initial configuration until an accepting one for all strings belonging to .
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (2)
MATH-483: Gödel and recursivity
Gödel incompleteness theorems and mathematical foundations of computer science
NX-465: Computational neurosciences: neuronal dynamics
In this course we study mathematical models of neurons and neuronal networks in the context of biology and establish links to models of cognition. The focus is on brain dynamics approximated by determ
Related lectures (5)
Theoretical Properties of RNNs
Explores the theoretical properties and practical power of Recurrent Neural Networks, including their relationship to state machines and Turing completeness.
WS1S Solver: Project Structure
Explores the project structure for solving WS1S formulas and planned additions.
Related publications (32)
Related people (1)
Related concepts (5)
Deterministic context-free language
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs. DCFLs are of great practical interest, as they can be parsed in linear time, and various restricted forms of DCFGs admit simple practical parsers.
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 below). 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.
Context-free language
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by context-free grammars. Different context-free grammars can generate the same context-free language. Intrinsic properties of the language can be distinguished from extrinsic properties of a particular grammar by comparing multiple grammars that describe the language.