IB102 – úkol 4, příklad 1 Odevzdání: 13. 10. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body]
a) Rozhodněte a zdůvodněte, zda je třída regulárních jazyků nad abecedou Σ = {a, b, c}
uzavřená na unární operaci removeA, která z jazyka odstraní všechna slova obsahující
alespoň jedno a.
b) Dokažte nebo vyvraťte: L je regulární =⇒ L je konečný nebo co−L je konečný
c) Dokažte nebo vyvraťte: L∗
je regulární =⇒ L je regulární
d) Dokažte nebo vyvraťte: L∗
není regulární =⇒ L není regulární
Pokud budete potřebovat, můžete v celém příkladu využívat toho, že na přednášce a
cvičeních byly ukázány některé neregulární jazyky (jejich neregularitu nemusíte znovu
dokazovat).