IB102 – úkol 7, příklad 2 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).