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.

PropertyValue
dbpprop:abstract
  • 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 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 takes 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. In an early result of computational complexity theory, Steven Cook showed in 1979 that deterministic context-free languages can be recognized by a deterministic Turing machine in polynomial time and O(n) space; as a corollary, DCFL is contained in SC.
  • 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. Im 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.
dbpprop:czooProperty
  • Class DCFL
  • D dcfl
dbpprop:hasPhotoCollection
dbpprop:wikiPageUsesTemplate
rdf:type
rdfs:comment
  • 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.
  • 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. Im Bezug auf Grammatiken findet sich auch die Bezeichnung LR(k)-Sprache: Jede LR(k)-Grammatik beschreibt eine deterministisch-kontextfreie Sprache.
rdfs:label
  • Deterministic context-free language
  • Deterministisch kontextfreie Sprache
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of