IB102 – úkol 3, příklad 1 – řešení Odevzdání: 7. 10. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Uvažme abecedu Σ = {a, b} a uvažme jazyk L nad touto abecedou:
L = {xwx | x ∈ {a, b}, w ∈ {a, b}∗
}
Najděte nějakou pravou kongruenci ∼ s konečným indexem takovou, že jazyk L je sjednocením
některých tříd rozkladu Σ∗
podle ∼. Dokažte, že se jedná o pravou kongruenci,
včetně důkazu, že se jedná o ekvivalenci.
Rozhodněte, zda je jazyk regulární. Své rozhodnutí zdůvodněte.
Řešení
Pravou kongruenci ∼ s konečným indexem takovou, že L je sjednocením některých tříd
rozkladu Σ∗
podle ∼, nejjednodušeji odvodíme z totálního deterministického konečného
automatu pro jazyk L.
Nejprve si tedy navrhneme totální DFA A akceptující jazyk L:
A = ({qε, qaw, qbw, qawa, qbwb}, Σ, δ, qε, {qawa, qbwb})
qε
qawqbw qawaqbwb
a
b
b
a
a
b
a
b
b
a
Σ∗
nyní můžeme rozdělit do disjunktních tříd rozkladu odpovídajících jednotlivým
stavům automatu A1
:
Tε = L(qε) = {ε}
Taw = L(qaw) = {a}.({a}∗
.{b}+
)∗
Tbw = L(qbw) = {b}.({b}∗
.{a}+
)∗
Tawa = L(qawa) = {a}.({b}∗
.{a}+
)+
= Taw.{a}+
= {a}.{a, b}∗
.{a}
Tbwb = L(qbwb) = {b}.({a}∗
.{b}+
)+
= Tbw.{b}+
= {b}.{a, b}∗
.{b}
1
Zde zápis L(q), kde q ∈ Q označuje jazyk akceptovaný automatem jehož definice je stejná jako definice
automatu A až na množinu akceptujících stavů která je {q}.
1
IB102 – úkol 3, příklad 1 – řešení Odevzdání: 7. 10. 2013
Vypracoval(a): UČO:
Skupina:
Slovní popis tříd rozkladu:
• Tε je třída obsahující jen prázdné slovo. Prázdné slovo musí být ve třídě samo,
protože dosud nevíme jakým písmem bude slovo začínat
• Taw je třída slov, která začínají a a nepatří do jazyka L, nicméně mají potenciál
do něj patřit pokud k nim bude přiřetězeno slovo končící na a. (Do této třídy patří
také a.)
• Tbw – obdobně pro b
• Tawa je třída slov délky alespoň 2, která začínají na a a končí na a. Tedy všechna
slova v této třídě rozkladu patří do L.
• Tbwb – opět obdobně pro b
Lze vidět přímo z definice tříd (nebo jejich popisu), že tyto třídy jsou skutečně disjunktní
a zároveň jejich sjednocením je Σ∗
, tedy tvoří rozklad množiny Σ∗
.
Jazyk L je potom sjednocením tříd Tawa a Tbwb, tedy
L = Tawa ∪ Tbwb
Relaci ∼ můžeme definovat pomocí výše zadefinovaných tříd rozkladu:
u ∼ v
def
⇐⇒ ∃X ∈ {Tε, Taw, Tbw, Tawa, Tbwb} : u ∈ X ∧ v ∈ X
(Tedy u je v relaci s v jestliže patří do stejné třídy rozkladu)
Takto definovaná relace ∼
• je reflexivní:
Důkaz. Platí, že každé x ∈ Σ∗
patří do nějaké třídy rozkladu, tedy je jistě v relaci
samo se sebou.
• je symetrická
Důkaz. Uvažme libovolná slova x, y taková, že x ∼ y.
Potom z definice ∼ plyne, že existuje třída rozkladu X taková, že x ∈ X, y ∈ X a
tedy jistě platí i y ∼ x.
• je tranzitivní
Důkaz. Uvažme libovolná slova x, y, z taková, že x ∼ y, y ∼ z
Potom z definice ∼ plyne, že existuje třída rozkladu X taková, že x ∈ X, y ∈ X,
z ∈ X.
Situace, kdy by x a y padly obě do nějaké třídy X a y a z padly do jiné třídy Y
(tedy x ∈ X, y ∈ X, y ∈ Y, z ∈ Y, X = Y ), nastat nemůže, protože jednotlivé třídy
rozkladu jsou disjunktní.
Tedy platí, že i x ∼ z.
2
IB102 – úkol 3, příklad 1 – řešení Odevzdání: 7. 10. 2013
Vypracoval(a): UČO:
Skupina:
• je pravá kongruence
V následujícím textu budu proměnné označující prvky množiny Σ označovat podtrženými znaky ze začátku abecedy,
tedy například c je proměnná, znaky abecedy budu psát normálně, například a, b.
Důkaz. Podle tvrzení 2.21 z přednášky lze podmínku k tomu aby ekvivalence byla
pravou kongruencí zformulovat jako
∀u, v ∈ Σ∗
, c ∈ Σ : u ∼ v ⇒ uc ∼ vc
Musíme zde tedy ukázat, že jsou-li libovolná 2 slova v relaci ∼, pak pokud k oběma
přidáme libovolné písmeno ze Σ, výsledná slova budou opět v relaci ∼.
Postupně probereme jednotlivé třídy rozkladu a jednotlivá c ∈ Σ.
– u, v ∈ Tε: jediným slovem je ε, a tedy vždy u = v a tedy i ∀c ∈ Σ : uc = vc,
proto z reflexivity ∼ platí uc ∼ vc.
– u, v ∈ Taw:
∗ přiřetězujeme c = a: ua, va ∈ Tawa (lze vidět z popisu Tawa a jeho vztahu
k Taw)
Taw.{a} ⊆ Tawa
∗ přiřetězujeme c = b: ub, vb ∈ Taw (z popisu lze vidět, že můžeme přidat
libovolný počet znaků b a stále zůstáváme v Taw)
Taw.{b} ⊆ Taw
– u, v ∈ Tawa:
∗ přiřetězujeme c = a: ua, va ∈ Tawa
Tawa.{a} ⊆ Tawa
∗ přiřetězujeme c = b: ub, vb ∈ Taw
Tawa.{b} ⊆ Taw
– u, v ∈ Tbw: (chová se obdobně jako Taw)
∗ přiřetězujeme c = a: ua, va ∈ Tbw
Tbw.{a} ⊆ Tbw
∗ přiřetězujeme c = b: ub, vb ∈ Tbwb
Tbw.{b} ⊆ Tbwb
– u, v ∈ Tbwb: (chová se obdobně jako Tawa)
∗ přiřetězujeme c = a: ua, va ∈ Tbw
Tbwb.{a} ⊆ Tbw
∗ přiřetězujeme c = b: ub, vb ∈ Tbwb
Tbwb.{b} ⊆ Tbwb
Index relace ∼ je 5 (protože rozklad Σ∗
/∼ je tvořen 5 množinami).
Jazyk L je regulární – nalezli jsme pravou kongruenci ∼ s konečným indexem takovou,
že L je sjednocením některých tříd rozkladu Σ∗
/∼, tedy podle Myhill-Nerodovy věty
je jazyk L regulární.
3