IB102 – úkol 6, příklad 1 – řešení 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.
Řešením je například gramatika G = ({S, Z, X}, {a, b}, P, S), kde
P = {S → aSa | bSb | aZb | bZa,
Z → aZa | bZb | aXb | bXa,
X → ε | a | b | aXa | bXb}.
Intuitivně, pomocí neterminálu S a pravidel aSa, bSb generujeme postupně palindrom.
Abychom mohli vygenerovat terminální řetězec, musíme někdy použít pravidlo aZb nebo
bZa. Tím si zaručíme existenci první pozice, na které je nutné provést změnu, abychom
dostali palindrom.
Neterminál Z tedy uchovává informaci o tom, že terminální řetězec před ním, psaný
pozpátku, je terminálním řetězcem za ním, ve kterém provedeme právě jednu změnu znaku
(na libovolné pozici). Při dalším generování můžeme použít obdobně jako u neterminálu
S pravidla aZa, bZb, kterými pokračujeme v generování palindromu. Abychom mohli
vygenerovat terminální řetězec, musíme použít pravidlo aXb nebo bXa.
Pokud tedy dostaneme ve větné formě neterminál X, máme zaručeno, že terminální řetězec
před ním, psaný pozpátku, je terminální řetězec za ním, ve kterém provedeme právě
dvě změny znaků (na libovolných, různých pozicích). Pro další generování tedy lze použít
jen ta pravidla, která zachovávají vlastnost palindromu, případně ukončit generování.