Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Deterministic context-free language
open-in-new
<p>In <a href="/facts/Formal_language_theory/crDTyP8q">formal language theory</a>, deterministic context-free languages (DCFL) are a <a href="/facts/Proper_subset/SJGERmbA">proper subset</a> of <a href="/facts/Context-free_language/sHDxB5So">context-free languages</a>. They are context-free languages that can be accepted by a <a href="/facts/Deterministic_pushdown_automaton/WHaMPJcS">deterministic pushdown automaton</a>. DCFLs are always unambiguous, meaning that they admit an <a href="/facts/Unambiguous_grammar/elcVDDL4">unambiguous grammar</a>. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs. </p><p>DCFLs are of great practical interest, as they can be parsed in <a href="/facts/Linear_time/77T62gmf">linear time</a>, and various restricted forms of DCFGs admit simple practical parsers. They are thus widely used throughout computer science. </p>