IB102 - úkol 3, příklad 1
Odevzdání: 8.10. 2012
Vypracoval (a): Skupina:
UCO:
1. [2 body] Uvažme jazyk
L = {w G {a, b}* | právě každý 2. symbol ve w je a anebo právě každý 3. symbol ve w je a}. (Tedy například slovo babab do tohoto jazyka patří, zatímco slovo babaaa nebo babba 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).