IB102 - úkol 3, příklad 2 - řešení
Odevzdání: 8.10. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
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).
Řešení: L není regulární. Důkaz provedeme pomocí PL.
• Nechť n je libovolné přirozené číslo, dále pevné.
• Zvolíme slovo w = bnabna. Zřejmě w G L a \w\ > n.
• Všechna možná rozdělení w = xyz, \xy\ < n, y ^ e vypadají takto:
x = bk k > 0
y = bl / > 0, k + l <n
z = bn-k-labna
• Zvolíme i = 3, slovo xy%z pak vypadá takto:
xy3z = bkb3lbn-k-labna = bn+2labna
Zřejmě bn+2labna ^ L, neboť n + 21 ^ n (protože / > 0). Podle Lemmatu o vkládání tedy L není regulární.