IB005 úkol 10, příklad 2 Odevzdání: 1. 5. 2020 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.
2. [0,5 bodu] Rozhodněte, zda je následující jazyk nad abecedou Σ = {a, b, c} bezkontextový, a
své tvrzení dokažte.
L = {v · vR
· u · w | v, w ∈ {a, b}∗
, u ∈ {b, c}∗
, |u| > |w|}
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.