A deterministic context-free language is a formal language which is defined by a deterministic context-free grammar. The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic pushdown automaton. The set of deterministic context-free languages are a proper subset of the set of context-free languages that possess an unambiguous context free grammar.
| Property | Value |
|---|
| dbpedia-owl:abstract
|
- Eine deterministisch kontextfreie Sprache ist eine Sprache, die von einem deterministischen Kellerautomaten akzeptiert wird. Manchmal wird auch der gekürzte Begriff deterministische Sprache verwendet. Die Definition geht auf Seymour Ginsburg und Sheila Greibach zurück. In Bezug auf Grammatiken findet sich auch die Bezeichnung LR(k)-Sprache: Jede LR(k)-Grammatik beschreibt eine deterministisch-kontextfreie Sprache. Strenggenommen gilt die Umkehrung zwar nicht, denn es gibt deterministisch-kontextfreie Sprachen, die keine LR(0)-Sprachen sind (d.h. nicht als LR-Grammatik darstellbar sind), jedoch lassen sie sich durch Einführung einer eindeutigen Markierung für das Wortende in eine solche überführen.
- A deterministic context-free language is a formal language which is defined by a deterministic context-free grammar. The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic pushdown automaton. The set of deterministic context-free languages are a proper subset of the set of context-free languages that possess an unambiguous context free grammar. For example, the language of even-length palindromes on the alphabet of 0 and 1 has the simple, unambiguous grammar S → 0S0 | 1S1 | ε, but it cannot be parsed by a deterministic push down automaton. The languages of this class have practical importance in computer science. The complexity of the program and execution of a deterministic pushdown automaton is vastly less than that of a nondeterministic one. In the naive implementation, it must make copies of the stack every time a nondeterministic step occurs. The best known algorithm to test membership in any context-free language is Valiant's algorithm, taking O(n) time, whereas membership in a deterministic context-free language can be tested in O(n) time, where n is the length of the string. The deterministic context-free languages are exactly those recognized by some LR grammar. In an early result of computational complexity theory, Stephen Cook showed in 1979 that deterministic context-free languages can be recognized by a deterministic Turing machine in polynomial time and O(log n) space; as a corollary, DCFL is a subset of the complexity class SC.
|
| dcterms:subject
| |
| rdfs:comment
|
- Eine deterministisch kontextfreie Sprache ist eine Sprache, die von einem deterministischen Kellerautomaten akzeptiert wird. Manchmal wird auch der gekürzte Begriff deterministische Sprache verwendet. Die Definition geht auf Seymour Ginsburg und Sheila Greibach zurück. In Bezug auf Grammatiken findet sich auch die Bezeichnung LR(k)-Sprache: Jede LR(k)-Grammatik beschreibt eine deterministisch-kontextfreie Sprache.
- A deterministic context-free language is a formal language which is defined by a deterministic context-free grammar. The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic pushdown automaton. The set of deterministic context-free languages are a proper subset of the set of context-free languages that possess an unambiguous context free grammar.
|
| rdfs:label
|
- Deterministisch kontextfreie Sprache
- Deterministic context-free language
|
| owl:sameAs
| |
| foaf:page
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
