IB102 – úkol 5, příklad 1 – řešení Odevzdání: 2. 11. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Nechť L a R jsou regulární jazyky nad abecedou Σ a operace inject(L, R)
je definována následovně:
inject(L, R) = {u · v · w | uw ∈ L, v ∈ R}
Intuitivně je tedy inject(L, R) jazyk obsahující všechna slova, která vzniknou vložením
libovolného slova z jazyka R někam do libovolného slova z jazyka L. Například:
inject({a, aa} , {b, bb}) = {ba, ab, bba, abb, baa, aba, aab, bbaa, abba, aabb}
inject({ε, a} , {a, ab}) = {a, ab, aa, aab, aba}
Vaším úkolem je rozhodnout, zda je jazyk inject(L, R) regulární, tedy že třída regulárních
jazyků je uzavřená na operaci inject. Vaši odpověď dokažte, a to tak, že:
• Pokud rozhodnete, že není, najděte regulární jazyky L a R takové, že jazyk inject(L, R)
regulární není.
• Pokud rozhodnete, že je, dokažte tvrzení například s pomocí známých uzávěrových
vlastností třídy regulárních jazyků prezentovaných na přednášce, nebo konstruktivně
popsáním algoritmu na transformaci nějakého formalizmu pro popis regulárních ja-
zyků.
Třída regulárních jazyků je uzavřená na operaci inject. To můžeme dokázat popisem
algoritmu na konstrukci konečného automatu A rozpoznávajícího jazyk inject(L, R).
Základní myšlenka konstrukce
Budeme konstruovat konečný automat pro výsledný jazyk. Vyjdeme z DFA pro jazyky
L a R (ty existují, protože L, R jsou regulární). Kdykoli načteme nějaký prefix u slova
x = uw z jazyka L, budeme moci dále pokračovat slovem v z jazyka R a pak dokončit
načítání příslušného sufixu w. Zároveň však musíme zajistit, že:
1. toto vložení půjde udělat právě jednou,
2. po vložení v bude možné pokračovat jen takovým sufixem w, že uw ∈ L.
To tedy znamená, že po dobu načítání v si musíme pamatovat, ve kterém stavu automatu
pro L jsme začali v vkládat, a po skončení načítání v si musíme pamatovat, že již
další slovo z R vkládat nelze.
IB102 – úkol 5, příklad 1 – řešení Odevzdání: 2. 11. 2015
Vypracoval(a): UČO:
Skupina:
Myšlenka konstrukce konečného automatu – podrobněji
Mějme konečný automat AL pro jazyk L a konečný automat AR pro jazyk R. Pro každý
stav automatu AL vytvoříme kopii AR. Dále si vytvoříme kopii automatu AL, kterou
označíme A L.
Nyní spojíme všechny uvedené automaty do jednoho automatu A. Pro každý stav q
automatu AL opakujeme tento postup:
• z q vedeme přechod pod ε do vstupního stavu příslušné kopie AR,
• ze všech akceptujících stavů příslušné kopie AR vedeme přechod pod ε do stavu q
automatu A L, který odpovídá stavu q
Tímto jsme spojili všechny automaty a dále je potřeba zvolit počáteční stav a akceptující
stavy A. Jako počáteční stav A vybereme stav, který byl počátečním stavem
automatu AL. Koncové stavy budou všechny koncové stavy automatu A L.
Mohlo by se zdát, že automat A L není potřeba a z akceptujících stavů automatů pro
jazyk R by se stačilo vracet do stavů automatu AL. Tím bychom však vytvořili jazyk,
který dovoluje vložit více slov z jazyka R do slov z jazyka L, a to libovolně-krát.
Další chybnou úvahou je vytvoření pouze jednoho automatu pro jazyk R. To ale nestačí,
protože se musíme vrátit právě do toho místa ve slově z L, kde bylo načítání přerušeno
slovem z R.
Formální zápis konstrukce konečného automatu
DFA pro jazyk L je dán pěticí AL = (QL, Σ, δL, qL0, FL), DFA pro jazyk R pěticí AR =
(QR, Σ, δR, qR0, FR). Pro jazyk inject(L, R) vytvoříme NFA s ε-kroky A = (Q, Σ, δ, q0, F),
kde
• Q = ({1, 2} × QL) ∪ (QL × QR)
• q0 = (1, qL0)
• F = {(2, q) | q ∈ FL}
• δ((1, q), ε) = {(q, qR0)}, kde q ∈ QL
• δ((p, q), ε) = {(2, p)}, kde p ∈ QL a q ∈ FR
• δ((i, q), a) = {(i, p) | p = δL(q, a)}, kde i ∈ {1, 2}, a ∈ Σ a q ∈ QL
• δ((p, q), a) = {(p, r) | r = δR(q, a)}, kde a ∈ Σ, p ∈ QL a q ∈ QR
Poznámka: Stavy automatu A jsou označeny uspořádanými dvojicemi, kde první složka
určuje, ve které části slova u · v · w (uw ∈ L, v ∈ R) se nacházíme. Dvojice tvaru (1, q)
označují stavy pro část u, dvojice (2, q) pro část w a dvojice (p, q), kde p ∈ QL, stavy pro
část v.