IB005 úkol 10, příklad 1 Odevzdání: 2. 5. 2022 12:00
Jméno: UČO:
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. [0,5 bodu] Rozhodněte, zda je následující jazyk nad abecedou Σ = {a, b, c} bezkontextový a
své tvrzení dokažte.
L = {ck
s | s ∈ {a, b}∗
, k = #a(s) · #b(s)}.
Je-li vaše odpověď kladná, tzn. rozhodnete-li, že se jedná o bezkontextový jazyk, uveďte příslušný
zásobníkový automat včetně všech formálních náležitostí (nezapomeňte také explicitně uvést,
jakým způsobem akceptuje), případně můžete nejprve navrhnout gramatiku a následně sestrojit její
analyzátor. Výsledný zásobníkový automat nesmí být rozšířený.
Pokud se podle vás naopak o bezkontextový jazyk nejedná, dokažte tuto skutečnost pomocí
Lemmatu o vkládání pro bezkontextové jazyky (Pumping lemma pro CFL).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.