Deterministický bezkontextový jazyk

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 jednoznačná gramatika, 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ů.

Popis

Pojem deterministického bezkontextového jazyka má těsnou souvislost s deterministickým zásobníkovým automatem. Je to zásobníkový automat, jehož výkon je snížený, protože je deterministický; takový automat nesmí mít v žádné situaci více než jednu možnost, jakou provést akci, a proto nemůže rozpoznávat všechny bezkontextové jazyky.[1] Jednoznačná gramatika nemusí vždy generovat deterministický bezkontextový jazyk. Například jazyk palindromů sudé délky nad abecedou {0, 1} má jednoznačnou bezkontextovou gramatiku S → 0S0 | 1S1 | ε. Není možné analyzovat libovolný řetězec z tohoto jazyka bez toho, že by se nejdříve načetly všechny znaky řetězce, což znamená, že zásobníkový automat musí vyzkoušet alternativní přechody mezi stavy, aby dovoloval přijetí slov všech možných délek částečně analyzovaného řetězce.[2]

Vlastnosti

Deterministické bezkontextové jazyky mohou být rozpoznávány deterministickým Turingovým strojem s pamětí velikosti O(log2 n) v polynomiálním čase; v důsledku toho je třída deterministických bezkontextových jazyků podtřídou třídy složitosti SC[3]. Třída deterministických bezkontextových jazyků není uzavřená vůči operaci sjednocení, ale je uzavřená vůči operaci doplňku.

Význam

Deterministické bezkontextové jazyky mají velký praktický význam v matematické informatice, protože mohou být analyzovány mnohem efektivněji než nedeterministické bezkontextové jazyky. Složitost a čas běhu programové realizace analyzátoru, který využívá deterministický zásobníkový automat, je podstatně menší než analyzátoru nedeterministických jazyků. Při naivní implementaci nedeterministického automatu se při provedení každého nedeterministického kroku provede kopie zásobníku; nejznámější algoritmus pro zjišťování příslušnosti k libovolnému bezkontextovému jazyku je Algoritmus CYK, který pracuje v čase řádově O(n2.378), kde n je délka vstupního řetězce. Naproti tomu deterministické bezkontextové jazyky mohou být přijímány v čase řádu O(n) pomocí LR(k) analyzátorů[4]. To je velmi důležité pro překlad programovacích jazyků, protože programy bývají mnohem delší než věty v přirozeném jazyce. Proto definice většiny programovacích jazyků využívá deterministické jazyky.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Deterministic context-free language na anglické Wikipedii.

  1. ↑ HOPCROFT, John; ULLMAN, Jeffrey. Introduction to automata theory, languages, and computation. 1. vyd. [s.l.]: Addison-Wesley, 1979. 
  2. ↑ HOPCROFT, John; MOTWANI, Rajeev; ULLMAN, Jeffrey. Introduction to automata theory, languages, and computation. 2. vyd. [s.l.]: Addison-Wesley, 2001. Dostupné online. 
  3. ↑ S. Cook. Deterministické bezkontextové jazyky jsou přijímány v polynomiálním čase s pamětí úměrnou druhé mocnině logaritmu velikosti gramatiky. Proceedings of ACM STOC'79, stránky 338–345. 1979.
  4. ↑ KNUTH, D. E. "On the translation of languages from left to righ. [s.l.]: [s.n.] Dostupné online. 

Související články