IB102 – úkol 5, příklad 1 Odevzdání: 21. 10. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Tento úkol se skládá ze 3 nezávislých podúkolů:
a) Nechť R1, R2 jsou regulární jazyky nad abecedou Σ = {a, b} a platí R1 ⊆ R2.
Rozhodněte a dokažte, zda libovolný jazyk L, pro který platí R1 ⊆ L ⊆ R2, je také
regulární. [0.5 bodu]
b) Označme P třídu všech jazyků nad abecedou Σ = {a, b}, které obsahují alespoň
jedno slovo sudé délky. Rozhodněte a dokažte, zda je třída P uzavřená na následující
operace:
• průnik,
• sjednocení,
• doplněk,
• rozdíl,
• zřetězení,
• mocnina (libovolná, včetně 0),
• iterace.
Pro každou uvedenou operaci buďto dokažte, že je na ni třída P uzavřená, nebo
uveďte konkrétní protipříklad. [1 bod]
c) Uvažme libovolný jazyk X, který není kontextový, libovolný regulární jazyk R a
libovolný ko-konečný jazyk K (jazyk je ko-konečný, je-li jeho doplněk konečný).
Dále uvažme jazyk L definovaný následovně:
L = (R \ (co-K ∩ X))∗
Rozhodněte a dokažte, zda je jazyk L regulární. [0.5 bodu]
1