IB102 – úkol 7, příklad 2 Odevzdání: 18. 11. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Buď Σ = {a, b, c} abeceda a L ⊆ Σ∗
jazyk
L = {am
bn
cmn
| m, n ∈ N}.
Rozhodněte, zda je jazyk L bezkontextový, a vaše tvrzení dokažte. Tzn.:
• Pokud jazyk L je bezkontextový, uveďte bezkontextovou gramatiku, která L generuje,
nebo zásobníkový automat, který L akceptuje. Gramatiku/automat zapište se
všemi formálními náležitostmi.
• Pokud jazyk L není bezkontextový, dokažte tuto skutečnost pomocí lemmatu o vkládání
pro bezkontextové jazyky (pumping lemma pro CFL).
1