IB005 úkol 10, příklad 1 Odevzdání: 9. 5. 2021 23:59
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, d} bezkontextový a
své tvrzení dokažte.
{ap
bq
cr
dp
| p, q, r ∈ N0, q > p > r}
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.