IB102 – úkol 5, příklad 1 – řešení 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ů.
Třída regulárních jazyků je uzavřená na operaci zlibovolni. To můžeme dokázat dvěma
způsoby, buďto pomocí popisu transformace konečného automatu (automat původně akceptující
slova z jazyka L po transformaci bude akceptovat slova z jazyka zlibovolni(L)),
nebo můžeme využít ekvivalence regulárních jazyků s regulárními výrazy a uzavřenost
operace dokázat úpravou regulárního výrazu.
Důkaz pomocí převedení na regulární výraz
Jazyk L převedeme na regulární výraz. Tím nám vznikne konečná posloupnost základních
regulárních výrazů (tedy výrazů ε, ∅ a a pro každé a ∈ Σ), operací sjednocení, zřetězení
a iterace a závorek. Operaci zlibovolni pak na regulárním výrazu provedeme tak, že nad
všemi základními regulárními výrazy provedeme operaci pozitivní iterace. Takto vzniklé
podvýrazy po provedení operace pozitivní iterace budou stále regulárními výrazy, a i
výsledný regulární výraz bude tedy validním regulárním výrazem a tedy bude popisovat
regulární jazyk. Tím pádem je jazyk zlibovolni(L) regulární pro libovolný regulární jazyk
L a třída regulárních jazyků je tedy uzavřená na operaci zlibovolni.
IB102 – úkol 5, příklad 1 – řešení Odevzdání: 20. 10. 2014
Vypracoval(a): UČO:
Skupina:
Důkaz pomocí transformace konečného automatu
Pro jazyk L si zkonstruujeme konečný automat. Pro každý přechod v konečném automatu
vytvoříme nový pomocný stav. Do pomocného stavu vedeme přechod z původního stavu
pod původním symbolem. Nad novým stavem vytvoříme smyčku nad oním symbolem a
z nového stavu se vrátíme pod ε do druhého stavu. Z ekvivalence DFA s NFA s ε-kroky
vyplývá, že výsledný konečný automat bude stále akceptovat slova regulárního jazyka.
Formálněji napsaná transformace:
Původní automat je dán pěticí
A = (Q, Σ, δ, q0, F),
transformovaný automat
A = (Q , Σ, δ , q0, F).
Pro každý přechod
δ(qm, a) = qo,
kde qm, qo ∈ Q, a ∈ Σ vytvoříme nový stav qn ∈ Q , qn /∈ Q a nové přechody
δ (qm, a) = qn δ (qn, a) = qn δ (qn, ε) = qo.
Mohlo by se zdát, že stačí vytvořit smyčky nad všemi stavy a nemusíme vytvářet nové
stavy, to však nefunguje: uvažme stav, z něhož vychází 2 šipky, jedna pod a a druhá pod
b (stav nemá žádnou smyčku). Pokud bychom přidali smyčky pod a, b k tomuto stavu,
pak v tomto stavu budeme moci míchat písmena a, b, což se však stát nemá (tento stav
nastane například u jazyka {a, b}, přičemž platí, že zlibovolni({a, b}) = {a}+
∪{b}+
, avšak
pouhým přidáním smyček bychom dostali {a, b}∗
). Obdobně by problém nastal i pokud
bychom přidali smyčky k cílovému stavu šipky.
Důkaz pomocí regulárního přechodového grafu
Asi nejelegantnějším konstruktivním důkazem je důkaz za pomoci regulárního přechodového
grafu:
1. Sestrojíme konečný (může být nedeterministický i s ε-kroky) automat popisující
jazyk L
2. tento konečný automat je zároveň i regulárním přechodovým grafem
3. každou hrany pod libovolným písmenem a ∈ Σ nahradíme hranou pod regulárním
výrazem a+
4. výsledkem je regulární přechodový graf popisující jazyk zlibovolni(L)
IB102 – úkol 5, příklad 1 – řešení Odevzdání: 20. 10. 2014
Vypracoval(a): UČO:
Skupina:
Výsledek je nutně zlibovolni(L), protože kdykoli jsme mohli v původním automatu mít
jedno písmeno, nyní můžeme mít neomezené nenulové opakování téhož písmene. Výsledek
rovněž nutně popisuje regulární jazyk (z ekvivalence NFA a regulárních přechodových
grafů).
Tedy třída regulárních jazyků je tedy uzavřena na operaci zlibovolni.