IB102 – úkol 10, příklad 2 Odevzdání: 9. 12. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť Σ je libovolná abeceda a A, B ⊆ Σ∗
jsou jazyky nad touto abecedou.
Dále nechť HALT je jazyk problému zastavení. O jazyce L řekneme, že je netriviálním
jazykem nad abecedou Σ, pokud L = ∅ a zároveň L = Σ∗
.
Rozhodněte, zda jsou následující tvrzení pravdivá, a svá rozhodnutí zdůvodněte:
(a) A je regulární jazyk, B je netriviální rekursivní jazyk =⇒ A ≤m B,
(b) A ≤m HALT =⇒ A není rekursivní.
1