-
V řadě (i praktických) aplikací je třeba zjistit, zda daný jazyk je (a nebo není) DCFL.
-
K důkazu, že je DCFL stačí nalézt odpovídající DPDA. Obrácená situace, kdy chceme ukázat, že není DCFL, může být složitější. Pokud by nebyl ani CFL, můžeme použít pumping lemma, ale často může být CFL, ale ne DCFL. Jelikož není známo žádné pumping lemma, které by platilo specialně do DCFL, musíme se spolehnout jen na uzávěrové vlastnosti. Naštěstí DCFL jsou uzavřeny na některé operace, například vůči doplňku, na něž CFL obecně uzavřeny nejsou.
-
Třída DCFL není uzavřena vzhledem k operaci průniku.
-
Třída deterministických bezkontextových jazyků je uzavřena vůči doplňku.
-
Třída DCFL není uzavřena vzhledem ke sjednocení.
Příklad
Navigace
Předchozí: Deterministické zásobníkové automaty Následující: Turingův stroj, nedeterministický TS Celý okruh: 1. Teoretické základy informatiky