IB 102 - úkol 3, příklad 2
Odevzdání: 8.10. 2012
Vypracoval (a): Skupina:
UCO:
2. [2 body] Uvažme jazyk
L = {w G {a, b}* | právě každý k-tf symbol ve w je a,
kde k je libovolné, pevné, kladné přirozené číslo}
Tedy například slova aaa, babab, bbabbabba, bbbba, bbbbbabbb do tohoto jazyka patří, zatímco slova babba, bbbababbba nikoliv.
Rozhodněte, zda jazyk L je či není regulární a dokažte:
• Pokud L je regulární, uveďte regulární gramatiku generující anebo konečný deterministický automat akceptující daný jazyk. 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í (tzv. Pumping Lemma).