IB102 – úkol 7, příklad 2 – řešení Odevzdání: 18. 11. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Buď Σ = {a, b, c} abeceda a L ⊆ Σ∗
jazyk
L = {am
bn
cmn
| m, n ∈ N}.
Rozhodněte, zda je jazyk L bezkontextový, a vaše tvrzení dokažte. Tzn.:
• Pokud jazyk L je bezkontextový, uveďte bezkontextovou gramatiku, která L generuje,
nebo zásobníkový automat, který L akceptuje. Gramatiku/automat zapište se
všemi formálními náležitostmi.
• Pokud jazyk L není bezkontextový, dokažte tuto skutečnost pomocí lemmatu o vkládání
pro bezkontextové jazyky (pumping lemma pro CFL).
Řešení: Jazyk L není bezkontextový.
Důkaz. Tvrzení dokážeme obměnou lemmatu o vkládání pro bezkontextové jazyky.
Tedy chceme dokázat, že pro každé n ∈ N existuje slovo z ∈ L takové, že |z| ≥ n a
pro všechna slova u, v, w, x, y splňující z = uvwxy, vx = ε a |vwx| ≤ n existuje i ∈ N0
takové, že uvi
wxi
y ∈ L. Z obměny tvrzení lemmatu o vkládání pak vyplývá, že jazyk L
není bezkontextový. (Všimněte si, že díky Poznámce 3.25 můžeme v tvrzení Věty 3.24
místo konstant p, q ∈ N psát jedinou konstantu n ∈ N).
• Nechť tedy n ∈ N je libovolné přirozené číslo, dále však pevné.
• Zvolíme slovo z = an
bn
cn2
. Jistě z ∈ L a |z| ≥ n.
• Buď z = uvwxy libovolné rozdělení slova z, kde vx = ε, |vwx| ≤ n. Pak pro tvar
slova vx mohou nastat následující případy:
– vx ∈ {a}+
: Pak vx = ak
pro nějaké k ∈ N (k > 0). Volbou i = 0 získáme
slovo z = uv0
wx0
y = uwy = an−k
bn
cn2
. Slovo z nenáleží do jazyka L, protože
(n − k)n = n2
− kn < n2
.
– vx ∈ {b}+
: Analogicky
– vx ∈ {c}+
: Pak vx = ck
pro nějaké k ∈ N (k > 0). Volbou i = 0 získáme
slovo z = uv0
wx0
y = uwy = an
bn
cn2−k
. Slovo z nenáleží do jazyka L, protože
n2
> n2
− k.
– vx ∈ {a}+
{b}+
: Pak vx = ak
bl
pro nějaká k, l ∈ N (k, l > 0). Volbou i = 0
získáme slovo z = uv0
wx0
y = uwy = an−k
bn−l
cn2
. Slovo z nenáleží do jazyka
L, protože (n − k)(n − l) < n2
.
– vx ∈ {b}+
{c}+
: Pak vx = bk
cl
pro nějaká k, l ∈ N (k, l > 0). Navíc z podmínky
|vwx| ≤ n vyplývá nerovnost l ≤ n − k < n ≤ nk, protože k + l = |vx| ≤
|vwx| ≤ n. Volbou i = 0 získáme slovo z = uv0
wx0
y = uwy = an
bn−k
cn2−l
.
Slovo z nenáleží do jazyka L, protože n(n − k) = n2
− nk < n2
− l.
1
IB102 – úkol 7, příklad 2 – řešení Odevzdání: 18. 11. 2013
Vypracoval(a): UČO:
Skupina:
Jiné případy nastat nemohou, protože platí |vwx| ≤ n, tudíž slovo vx může obsahovat
nejvíce dva různé znaky abecedy. Celkově jsme pro každé rozdělení našli i ∈ N0 takové,
že slovo uvi
wxi
y ∈ L, a tedy podle lemmatu o vkládání pro bezkontextové jazyky jazyk
L není bezkontextový.
2