IB102 – úkol 3, příklad 2 – řešení Odevzdání: 7. 10. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Uvažme jazyk
L = ai
bj
ck
| i, j, k ≥ 0, pokud i = 1, pak j = k
Dokažte pomocí Myhill-Nerodovy věty, že jazyk L není regulární.
Důkaz, že jazyk L není regulární, povedeme sporem pomocí Myhill-Nerodovy věty.
Důkaz. Předpokládejme, že jazyk L je regulární, a tedy podle Myhill-Nerodovy věty má
∼L konečný index – označme ho jako k.
Uvažme nyní slova ab, abb, . . . , abk+1
∈ Σ∗
. Těchto slov je více než je index ∼L ⇒ existují
slova abi
a abj
, kde i = j, taková, že abi
∼L abj
, tj. pro každé w ∈ Σ∗
platí: abi
w ∈ L ⇔
abj
w ∈ L (z definice ∼L).
Uvažme nyní slovo ci
∈ Σ∗
. Přiřetězením tohoto slova ke slovu abi
dostaneme abi
ci
∈ L,
přiřetězením ke slovu abj
dostáváme abj
ci
/∈ L (i = j), což je v rozporu s definicí ∼L.
Máme tedy spor s předpokladem konečnosti indexu ∼L, a tedy jazyk L není regulární.
Bonus: [+2 body] Dokažte, že neregularitu jazyka L nelze dokázat pomocí Lemmatu
o vkládání. Jinými slovy: nalezněte takové n, že pro každé w ∈ L délky alespoň n existuje
x, y, z takové, že xyz = w, |xy| ≤ n, y = ε a pro každé i ≥ 0 platí: xyi
z ∈ L. Dokažte, že
n má uvedené vlastnosti.
Dokážeme, že n = 2 má uvedené vlastnosti.
Důkaz. Každé slovo w ∈ L je tvaru aj
bk
cl
, kde j, k, l ≥ 0 a k = l, jestliže j = 1. Dále
(podle definice PL) uvažujme pouze slova w, pro která platí |w| ≥ n, tedy j + k + l ≥ 2.
Uvažme tedy případy: j = 1 a j = 1.
• Pro j = 1 rozdělíme slovo následovně: x = ε, y = a, z = bm
cm
, kde m ≥ 1. Toto
rozdělení splňuje uvedené podmínky (|a| ≤ 2, a = ε).
Nechť i ∈ N0 je libovolné, platí: xyi
z = ai
bm
cm
∈ L (z definice jazyka L, protože
vždy platí k = l = m).
• Pro j = 1 uvažme následující případy:
– w = bk
cl
, kde k > 0, l ≥ 0. Pak x = ε, y = b, z = bk−1
cl
. Snadno ověříme,
že toto rozdělení splňuje uvedené podmínky. Po napumpování dostáváme w =
xyi
z = bi+k−1
cl
∈ L (slovo je tvaru bk
cl
a #a(w ) = 1).
– w = cl
, kde l ≥ 2. Pak x = ε, y = c, z = cl−1
. Opět se snadno ukáže, že je toto
rozdělení korektní a po napumpování je w = xyi
z = ci+l−1
∈ L.
– w = aabk
cl
, kde k, l ≥ 0. Pak x = ε, y = aa, z = bk
cl
(platí |aa| ≤ 2, aa = ε).
Opět pro libovolné i ∈ N0 platí: w = (aa)i
bk
cl
∈ L (při libovolném i je
#a(w ) = 1)
– w = aj
bk
cl
, kde j ≥ 3, k, l ≥ 0. Pak x = ε, y = a, z = aj−1
bk
cl
. Po napumpování
dostáváme w = ai+j−1
bk
cl
∈ L (j ≥ 3 ⇒ #a(w ) > 1)
1