IB102 – úkol 2, příklad 2 Odevzdání: 30. 9. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Uvažme jazyk
L = {w ∈ {a, b, c}∗
| #a(w) + #b(w) = #c(w)}.
Rozhodněte, zda je jazyk L regulární, a vaše tvrzení dokažte. Tzn.:
• Pokud L je regulární, uveďte regulární gramatiku, která L generuje, nebo konečný
deterministický automat, který L akceptuje. Gramatiku/automat zapište se všemi
formálními náležitostmi.
• Pokud L není regulární, dokažte tuto skutečnost pomocí Lemmatu o vkládání (Pumping
lemma).
1