IB102 – úkol 7, příklad 2 – řešení Odevzdání: 23. 11. 2015
Vypracoval(a): UČO:
Skupina:
2. [2 body] O následujícím jazyku nad abecedou Σ = {a, b, c} rozhodněte, zda je
bezkontextový, a své tvrzení dokažte.
L = {ucv | u, v ∈ Σ∗
, #a(u) = #b(v), #b(u) = #a(v)}
V případě, že je vaše odpověď, že se jedná o bezkontextový jazyk, uveďte příslušnou
bezkontextovou gramatiku, nebo zásobníkový automat. V opačném případě své tvrzení
dokažte pomocí Lemmatu o vkládání pro bezkontextové jazyky (Pumping lemma pro CFL).
Jazyk L není bezkontextový. Toto tvrzení dokážeme obměnou lemmatu o vkládání pro
bezkontextové jazyky.
• Nechť n ∈ N je libovolné.
• Zvolme slovo z = an
bn
cbn
an
. Pak jistě platí z ∈ L a |z| = 4n + 1 > n.
• Uvažme libovolné rozdělení slova z na pět podslov u, v, w, x, y ∈ Σ∗
, pro která platí
z = uvwxy, |vwx| ≤ n a vx = ε. Pro libovolné takové rozdělení rozlišme následující
případy podle toho, ve kterém z podslov se nachází písmeno c:
Písmeno c se nachází v podslově u (tedy podslovo vwx je vpravo od písmene c)
Zvolme i = 0. Chceme ukázat, že platí uvi
wxi
y = uwy ∈ L.
Díky podmínce vx = ε víme, že slovo vx musí obsahovat alespoň jedno písmeno
a nebo b. Ale pak část slova uwy za písmenem c obsahuje alespoň o jedno
písmeno a nebo b méně než část před pímenem c, a tedy slovo uwy skutečně
do jazyka L nenáleží.
Písmeno c se nachází v podslově v nebo x
Zvolme i = 0. Pak platí uvi
wxi
y = uwy ∈ L, protože slovo uwy neobsahuje
písmeno c.
Písmeno c se nachází v podslově w
Zvolme i = 0. Chceme ukázat, že platí uvi
wxi
y = uwy ∈ L.
Díky podmínce vx = ε víme, že alespoň jedno ze slov v a x musí být neprázdné.
Díky podmínce |vwx| ≤ n navíc víme, že ve slovech v a x se můžou vyskytovat
jen písmena b. Celkově tedy alespoň jedno ze slov v a x obsahuje alespoň jedno
písmeno b.
Ale pak je ve slově uwy před c více znaků a než znaků b za c nebo naopak je
před c méně znaků b než znaků a za c. A tedy slovo uwy skutečně do jazyka L
nenáleží.
Písmeno c se nachází v podslově y (tedy podslovo vwx je vlevo od písmene c)
Zvolme i = 0. Chceme ukázat, že platí uvi
wxi
y = uwy ∈ L.
Díky podmínce vx = ε víme, že slovo vx musí obsahovat alespoň jedno písmeno
a nebo b. Ale pak část slova uwy před písmenem c obsahuje alespoň o jedno
písmeno a nebo b méně než část za pímenem c, a tedy slovo uwy skutečně do
jazyka L nenáleží.
IB102 – úkol 7, příklad 2 – řešení Odevzdání: 23. 11. 2015
Vypracoval(a): UČO:
Skupina:
Celkově jsme pro každé přirozené číslo n našli slovo z z jazyka L délky větší než n takové,
že pro libovolné jeho rozdělení na pět slov u, v, w, x, y splňujících podmínky z lemmatu
o vkládání existuje nezáporné celé číslo i takové, že uvi
wxi
y není v jazyce L, a tedy z
lemmatu o vkládání pro bezkontextové jazyky vyplývá, že jazyk L není bezkontextový.