Deterministic context-free language
From Wikipedia, the free encyclopedia
A deterministic context-free language is a formal language that is a proper subset of languages defined by context-free grammars.[1] The set of deterministic context-free languages is identical to the set of languages accepted by a deterministic pushdown automaton.
[edit] References
- ^ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley, 233.
 |
This mathematics-related article is a stub. You can help Wikipedia by expanding it. |
| Automata theory: formal languages and formal grammars | |||
|---|---|---|---|
| Chomsky hierarchy |
Grammars | Languages | Minimal automaton |
| Type-0 | Unrestricted | Recursively enumerable | Turing machine |
| n/a | (no common name) | Recursive | Decider |
| Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
| n/a | Indexed | Indexed | Nested stack |
| Type-2 | Context-free | Context-free | Nondeterministic Pushdown |
| n/a | Deterministic Context-free | Deterministic Context-free | Deterministic Pushdown |
| Type-3 | Regular | Regular | Finite |
| Each category of languages or grammars is a proper subset of the category directly above it. | |||
