IB102 – úkol 5, příklad 1 Odevzdání: 20. 10. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body] Rozhodněte a dokažte, zda je třída regulárních jazyků nad abecedou
Σ = {a, b, c} uzavřena na unární operaci zlibovolni:
zlibovolni(L) = {ui1
1 ui2
2 . . . uin
n | n ∈ N0 ∧ u1, u2, . . . , un ∈ Σ
∧ u1u2 . . . un ∈ L ∧ i1, . . . , in ∈ N}
Tedy, intuitivně řečeno, jazyk zlibovolni(L) obsahuje všechna slova z jazyka L a navíc
všechna slova, která z nich vzniknou tak, že tak, že každé písmeno ve slově w ∈ L libovolněkrát
za sebou zopakujeme (nikoliv však odstraníme). Speciálně pak ε ∈ zlibovolni(L)
právě tehdy, když ε ∈ L.
Uveďme ještě příklady:
zlibovolni({c, ab}) = {c}+
∪ {a}+
· {b}+
= {c, ab, cc, aab, abb, ccc, aaab, aabb, abbb, cccc, . . .}
zlibovolni({ε, abc}) = {ε} ∪ {a}+
· {b}+
· {c}+
= {ε, abc, aabc, abbc, abcc, aabbc, aabcc, abbcc, . . .}
zlibovolni({a}∗
· {b}∗
· {a}) = {a}∗
· {b}∗
· {a}+
Nápověda: Pokud rozhodnete, že třída regulárních jazyků není uzavřená na operaci zlibovolni,
uveďte příslušný protipříklad. Pokud rozhodnete, že třída regulárních jazyků je uzavřená
na operaci zlibovolni, musíte toto tvrzení dokázat, například s pomocí známých uzávěrových
vlastností třídy regulárních jazyků, nebo konstruktivně popsáním algoritmu na
transformaci nějakého formalizmu pro popis regulárních jazyků.