IB102 úkol 8, příklad 1 Odevzdání: 21. 11. 2016
Jméno: UČO: Skupina:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
1. [2 body] O následujícím jazyku nad abecedou Σ = {a, b, c} rozhodněte, zda je bezkontextový.
L = {an
w | w ∈ {b, c}∗
, n ∈ N0, n < #b(w) < #c(w)}
Své tvrzení dokažte: V případě, že je vaše odpověď kladná, tj. ž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).
Pro jistotu připomeňme, že N0 značí množinu všech nezáporných celých čísel.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.