IB102 úkol 4, příklad 1 Odevzdání: 17. 10. 2016
Jméno: UČO: Skupina:
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.
1. [2 body] Tento úkol se skládá ze 3 nezávislých podúkolů:
a) Nechť L je jazyk nad abecedou {a, b}. Dokažte nebo vyvraťte následující tvrzení:
Pokud L ∪ LR není regulární, pak ani L není regulární. [0.5 bodu]
b) Nechť T je třída všech neprázdných jazyků nad abecedou {a, b}, jejichž všechna slova obsahují
písmeno a. Rozhodněte a dokažte, zda je třída T uzavřená na následující operace:
• průnik,
• sjednocení,
• doplněk,
• rozdíl,
• zřetězení,
• mocnina (libovolná, včetně 0),
• iterace,
• pozitivní iterace.
Pro každou uvedenou operaci buďto dokažte, že je na ni třída T uzavřená, nebo uveďte konkrétní
protipříklad. [1 bod]
c) Dokažte nebo vyvraťte následující tvrzení:
Nechť K je konečný a L libovolný jazyk nad abecedou {a, b}. Potom ((co−K)∪L) je ko-konečný
(jazyk je ko-konečný, je-li jeho doplněk konečný). [0.5 bodu]
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 4, příklad 1 Odevzdání: 17. 10. 2016
Jméno: UČO: Skupina:
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.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.