IB107 úkol 3, příklad 2 Odevzdání: 7. 12. 2021, 23:59
Jméno: Noblesní Plšice 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 body] Uvažme problém pro danou gramatiku G typu 0 (tedy bez omezení) a dané k ∈ N
rozhodnout, zda lze v této gramatice odvodit prázdné slovo ε v nejvýše k krocích. Problém nazveme
bounded epsilon derivation a ztotožníme s množinou
BED = { G, k | G je gramatika splňující S
≤k
=⇒G ε, kde S je kořenem G}.
Dokažte, že problém BED je NP-těžký.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.