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. They are thus widely used throughout computer science.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Deterministický bezkontextový jazyk (cs)
- Deterministisch kontextfreie Sprache (de)
- Deterministic context-free language (en)
- Langage algébrique déterministe (fr)
- Linguagem livre de contexto determinística (pt)
|
| rdfs:comment
| - 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. They are thus widely used throughout computer science. (en)
- En informatique théorique et en théorie des langages, un langage algébrique déterministe est un langage algébrique reconnu (par états finals) par un automate à pile déterministe. L'intérêt des langages déterministes est que leur analyse syntaxique se fait en temps linéaire en la longueur du mot, alors que dans un langage algébrique quelconque, la complexité est cubique, ou en tout cas se ramène à la complexité du produit matriciel, donc est en O(n2,37) où n est la longueur du mot par l'algorithme de Valiant. Tout langage algébrique déterministe peut être décrit par une grammaire LR(1) et réciproquement. Cela permet de les utiliser pour des applications pratiques. Ainsi, la plupart des langages de programmation sont des langages algébriques déterministes. (fr)
- Na teoria da linguagem formal, linguagens livres de contexto determinísticas (LLCD) são um subconjunto de linguagens livres de contexto (LLC). Elas são as linguagens livres de contexto que podem ser aceitos por um autômato determinístico (AD). (pt)
- Deterministický bezkontextový jazyk (anglicky deterministic context-free language, DCFL) je v teorii formálních jazyků každý bezkontextový jazyk, který lze přijímat deterministickým zásobníkovým automatem. Každý deterministický bezkontextový jazyk je jednoznačný, což znamená, že pro něj existuje , ale pro libovolný (neprázdný) deterministický bezkontextový jazyk existují i nejednoznačné gramatiky. Protože existují nedeterministické jednoznačné bezkontextové jazyky, je třída deterministických bezkontextových jazyků vlastní podtřídou třídy bezkontextových jazyků. (cs)
- 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. (de)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Deterministický bezkontextový jazyk (anglicky deterministic context-free language, DCFL) je v teorii formálních jazyků každý bezkontextový jazyk, který lze přijímat deterministickým zásobníkovým automatem. Každý deterministický bezkontextový jazyk je jednoznačný, což znamená, že pro něj existuje , ale pro libovolný (neprázdný) deterministický bezkontextový jazyk existují i nejednoznačné gramatiky. Protože existují nedeterministické jednoznačné bezkontextové jazyky, je třída deterministických bezkontextových jazyků vlastní podtřídou třídy bezkontextových jazyků. Deterministické bezkontextové jazyky mají velký praktický význam a jsou často používány v matematické informatice, protože je lze analyzovat v čase přímo úměrném délce vstupní věty a různé omezené tvary deterministických bezkontextových gramatik umožňují sestrojení jednoduchých praktických analyzátorů. Přirozené jazyky jsou ze své podstaty nejednoznačné a jejich analýza je mnohem pomalejší než analýza programovacích jazyků. (cs)
- 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. Umgekehrt gibt es für jede deterministisch kontextfreie Sprache ein , so dass eine LR(k)-Sprache ist (d. h. eine LR(k)-Grammatik hat). Tatsächlich reicht dafür in jedem Fall , aber nicht . Jedoch lässt sich auch jede deterministisch kontextfreie Sprache, die nicht LR(0) ist, durch Einführung einer eindeutigen Markierung für das Wortende in eine LR(0)-Sprache überführen. (de)
- 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. They are thus widely used throughout computer science. (en)
- En informatique théorique et en théorie des langages, un langage algébrique déterministe est un langage algébrique reconnu (par états finals) par un automate à pile déterministe. L'intérêt des langages déterministes est que leur analyse syntaxique se fait en temps linéaire en la longueur du mot, alors que dans un langage algébrique quelconque, la complexité est cubique, ou en tout cas se ramène à la complexité du produit matriciel, donc est en O(n2,37) où n est la longueur du mot par l'algorithme de Valiant. Tout langage algébrique déterministe peut être décrit par une grammaire LR(1) et réciproquement. Cela permet de les utiliser pour des applications pratiques. Ainsi, la plupart des langages de programmation sont des langages algébriques déterministes. (fr)
- Na teoria da linguagem formal, linguagens livres de contexto determinísticas (LLCD) são um subconjunto de linguagens livres de contexto (LLC). Elas são as linguagens livres de contexto que podem ser aceitos por um autômato determinístico (AD). (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)