IB102 – úkol 11, příklad 2 Odevzdání: 16. 12. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body]
(a) Připomeňme definici třídy coNP:
coNP = {co−L | L ∈ NP}.
Dokažte, že platí inkluze P ⊆ NP ∩ coNP. Tedy ukažte, že každý jazyk L ∈ P splňuje
L ∈ NP a zároveň L ∈ coNP.
(b) Neformálně zdůvodněte, proč každý regulární jazyk R splňuje R ∈ TIME(n). Tedy
vysvětlete, proč pro každý regulární jazyk existuje Turingův stroj, který ho rozhoduje,
a navíc má lineární časovou složitost vzhledem k délce vstupního slova.
Bonus: [+1 bod] Úlohu (b) dokažte formálně. Přesně popište převod konečného deterministického
automatu na jazykově ekvivalentní Turingův stroj. Zdůvodněte, proč má
Turingův stroj, který vznikne touto konstrukcí, lineární časovou složitost.
1