Důkaz, že jazyk 𝐿 = {𝑎𝑗
𝑏𝑗
𝑐𝑎𝑗
𝑏𝑗
| 𝑗 ∈ N} není bezkontextový:
∙ Nechť 𝑛 ∈ N je libovolné, dále pevné číslo.
∙ Zvolíme 𝑧 = 𝑎 𝑛
𝑏 𝑛
𝑐𝑎 𝑛
𝑏 𝑛
z jazyka 𝐿 tak, že |𝑧| = 4𝑛 + 1 ≥ 𝑛.
∙ Uvažme libovolné rozdělení slova 𝑧 na 5 podslov 𝑢, 𝑣, 𝑤, 𝑥, 𝑦 ∈ Σ*
, pro
která platí 𝑧 = 𝑢𝑣𝑤𝑥𝑦, |𝑣𝑤𝑥| ≤ 𝑛 a 𝑣𝑥 ̸= 𝜀. Pro libovolné takové
rozdělení rozlišme následující případy podle toho, ve kterém z podslov
se nachází písmeno 𝑐:
Písmeno 𝑐 se nachází v podslově 𝑦 (tedy 𝑣𝑥 = 𝑎 𝑘
𝑏𝑙
, přičemž 𝑘 +
𝑙 ≥ 1).
Zvolíme 𝑖 = 0, pak 𝑢𝑣 𝑖
𝑤𝑥𝑖
𝑦 = 𝑎 𝑛−𝑘
𝑏 𝑛−𝑙
𝑐𝑎 𝑛
𝑏 𝑛
a jelikož je pumpovaná
část neprázdná, tak jsme zkrátili část slova před znakem 𝑐,
a tedy 𝑢𝑣 𝑖
𝑤𝑥𝑖
𝑦 /∈ 𝐿.
Písmeno 𝑐 se nachází v podslovech 𝑣 nebo 𝑥. Zvolíme 𝑖 = 0, pak
𝑢𝑣 𝑖
𝑤𝑥𝑖
𝑦 neobsahuje 𝑐, tedy není tvaru 𝑎𝑗
𝑏𝑗
𝑐𝑎𝑗
𝑏𝑗
, a tedy 𝑢𝑣 𝑖
𝑤𝑥𝑖
𝑦 /∈
𝐿.
Písmeno 𝑐 se nachází v podslově 𝑤 (tedy 𝑣𝑥 = 𝑏 𝑘
𝑎𝑙
, přičemž 𝑘 +
𝑙 ≥ 1).
Zvolíme 𝑖 = 0, pak 𝑢𝑣 𝑖
𝑤𝑥𝑖
𝑦 =
Písmeno 𝑐 se nachází v podslově 𝑢 (tedy 𝑣𝑥 = 𝑎 𝑘
𝑏𝑙
, přičemž 𝑘 +
𝑙 ≥ 1).
Celkově jsme pro každé přirozené číslo 𝑛 našli slovo 𝑧 z jazyka 𝐿 délky větší
než 𝑛 takové, že pro libovolné jeho rozdělení na pět slov 𝑢, 𝑣, 𝑤, 𝑥, 𝑦 splňujících
podmínky z lemmatu o vkládání existuje nezáporné celé číslo 𝑖 takové, že
𝑢𝑣 𝑖
𝑤𝑥𝑖
𝑦 není v jazyce 𝐿, a tedy z lemmatu o vkládání pro bezkontextové
jazyky vyplývá, že jazyk 𝐿 není bezkontextový.
1
Důkaz, že jazyk 𝐿 = {𝑎𝑗
𝑏𝑗
𝑐𝑎𝑗
𝑏𝑗
| 𝑗 ∈ N} není bezkontextový:
∙ Nechť 𝑛 ∈ N je libovolné, dále pevné číslo.
∙ Zvolíme 𝑧 = 𝑎⌈ 𝑛
2
⌉
𝑏⌈ 𝑛
2
⌉
𝑐𝑎⌈ 𝑛
2
⌉
𝑏⌈ 𝑛
2
⌉
z jazyka 𝐿, délka 𝑧 je větší než 𝑛.
∙ Uvažme libovolné rozdělení slova 𝑧 na 5 podslov 𝑢, 𝑣, 𝑤, 𝑥, 𝑦 ∈ Σ*
, pro
která platí 𝑧 = 𝑢𝑣𝑤𝑥𝑦, |𝑣𝑤𝑥| ≤ 𝑛 a 𝑣𝑥 ̸= 𝜀:
Celkově jsme pro každé přirozené číslo 𝑛 našli slovo 𝑧 z jazyka 𝐿 délky větší
než 𝑛 takové, že pro libovolné jeho rozdělení na pět slov 𝑢, 𝑣, 𝑤, 𝑥, 𝑦 splňujících
podmínky z lemmatu o vkládání existuje nezáporné celé číslo 𝑖 takové, že
𝑢𝑣 𝑖
𝑤𝑥𝑖
𝑦 není v jazyce 𝐿, a tedy z lemmatu o vkládání pro bezkontextové
jazyky vyplývá, že jazyk 𝐿 není bezkontextový.
2
Důkaz, že jazyk 𝐿 = {𝑢𝑐𝑣 | 𝑢, 𝑣 ∈ {𝑎, 𝑏}*
, # 𝑎(𝑢) = # 𝑏(𝑣) a # 𝑏(𝑢) =
# 𝑎(𝑣)} není bezkontextový:
∙ Nechť 𝑛 ∈ N je libovolné, dále pevné číslo.
∙ Zvolíme slovo 𝑧 =
∙ Uvažme libovolné rozdělení slova 𝑧 na 5 podslov 𝑢, 𝑣, 𝑤, 𝑥, 𝑦 ∈ Σ*
, pro
která platí 𝑧 = 𝑢𝑣𝑤𝑥𝑦, |𝑣𝑤𝑥| ≤ 𝑛 a 𝑣𝑥 ̸= 𝜀:
Celkově jsme pro každé přirozené číslo 𝑛 našli slovo 𝑧 z jazyka 𝐿 délky větší
než 𝑛 takové, že pro libovolné jeho rozdělení na pět slov 𝑢, 𝑣, 𝑤, 𝑥, 𝑦 splňujících
podmínky z lemmatu o vkládání existuje nezáporné celé číslo 𝑖 takové, že
𝑢𝑣 𝑖
𝑤𝑥𝑖
𝑦 není v jazyce 𝐿, a tedy z lemmatu o vkládání pro bezkontextové
jazyky vyplývá, že jazyk 𝐿 není bezkontextový.
3
Důkaz, že jazyk 𝐿 = {𝑎𝑗
𝑏 𝑘
𝑐𝑙
| 𝑗 < 𝑘 < 𝑙} není bezkontextový:
4