IB102 – úkol 6, příklad 1 Odevzdání: 16. 11. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Sestrojte bezkontextovou gramatiku pro jazyk L všech slov nad abecedou
Σ = {a, b}, kde w ∈ L právě tehdy, když platí, že změnou právě dvou znaků ve slově w
dostáváme palindrom. Zároveň musí platit, že dvě změny jsou nutné k tomu, aby se ze
slova w stal palindrom (tedy samo slovo w nesmí být palindrom a ani změnou jednoho
libovolného znaku palindrom nedostáváme).
Formálně, w = a1 . . . an ∈ L právě tehdy, když existují pozice i,j, kde 1 ≤ i < j ≤ |w|,
a znaky ci, cj ∈ {a, b} takové, že slovo w = a1 . . . ai−1 ci ai+1 . . . aj−1 cj aj+1 . . . an = w R
,
a zároveň neexistuje pozice k, kde 1 ≤ k ≤ |w|, a znak ck ∈ {a, b} takový, že w =
a1 . . . ak−1 ck ak+1 . . . an = w R
.
Příklady slov z jazyka L:
abab, aaabb, bbababbbbbb, aababa, abbbbaaba
Příklady slov nenáležících do jazyka L:
ε, a, bb, aab, abaabb, bbbaaa, abababab
Stručně, neformálně zdůvodněte, proč vaše gramatika generuje právě jazyk L.