IB107 úkol 3, příklad 2* Odevzdání: 7. 1. 2021, 23:59
Jméno: Novotný Petr UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2*. [3,5 bodu] Nechť A je deterministický konečný automat (DFA) se vstupní abecedou Σ (připomeňme,
že Σ je dána jakožto součást n-tice popisující A). Řekneme, že A je znakově univerzální
pokud existuje slovo w ∈ Σ∗ akceptované automatem A takové, že každý znak abecedy Σ se ve w
vyskytuje alespoň jednou (formálně, s využitím značení
z FJA/Automatů: ∀a ∈ Σ : #a(w) ≥ 1).
Dokažte, že problém
CHAR-UNIV = { A | A je znakově univerzální DFA }
je NP-úplný.
Důkaz NP-těžkosti je možné provést zcela stejně, jako u jednoduššího zadání.
U důkazu příslušnosti do NP je třeba ukázat, že existuje polynom p takový, že znakově univerzální
A velikosti n vždy akceptuje slovo, které obsahuje každý znak alespoň jednou a má délku nejvýše
p(n). Je pak možné použít stejný nedeterministický polynomiální algoritmus jako u jednoduššího
zadání s tím rozdílem, že tento algoritmus bude hádat slovo délky nejvýše p(n). Velikostí automatu
A rozumíme délku slova A . Jistě | A | ≥ |Q|+|Σ|, kde Q je množina stavů a Σ je vstupní abeceda
automatu A.
Ukážeme tedy, že každý znakově univerzální DFA A = (Q, Σ, δ, qinit , F) akceptuje slovo délky
nejvýše |Q| · (|Σ| + 1), které obsahuje každý znak vstupní abecedy alespoň jednou. Sporem. Nechť
u je nejkratší slovo obsahující všechny znaky, které je automatem akceptováno. Předpokládejme, že
|u| > |Q| · (|Σ| + 1). Pak při výpočtu A na slově u se nějaký stav q musí zopakovat alespoň (|Σ| + 2)krát.
Existuje tedy rozdělení u = vu1u2 · · · unw, kde n = |Σ| + 1, v, w ∈ Σ∗ a ui ∈ Σ+, takové,
že po přečtení v se automat nachází v q a rovněž pro libovolné 1 ≤ i ≤ n se po přečtení prefixu
vu1 · · · ui výpočet nachází ve stavu q (tj. čtení podslova ui odpovídá cyklu ve výpočtu). Řekneme,
že 1 ≤ i ≤ n je zbytečné, pokud všechny znaky v ui jsou již obsaženy ve vu1 · · · ui−1 (resp. ve v, pro
i = 1). Protože n = |Σ| + 1, pak existuje zbytečné i ∈ {1, . . . , n}. Ovšem pak odstraněním podslova
ui z u získáme slovo u , které obsahuje ty samé znaky, co u (tj. všechny znaky ze Σ), je akceptováno
(neboť z příslušného výpočtu jsme pouze odstranili jeden cyklus, zejména po přečtení u jsme ve
stejném stavu, jako po přečtení u), a zároveň je kratší než u. Spor s volbou u.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.