DU zadani0302 (PDF)

IB102 – u
´ kol 3, pˇ
r´ıklad 2
Vypracoval(a):
Skupina:

Odevzd´
an´ı: 8. 10. 2012
ˇ
UCO:

2. [2 body] Uvaˇzme jazyk
L = {w ∈ {a, b}∗ | pr´avˇe kaˇzd´
y k-t´
y symbol ve w je a,
kde k je libovoln´e, pevn´e, kladn´e pˇrirozen´e ˇc´ıslo}
Tedy napˇr´ıklad slova aaa, babab, bbabbabba, bbbba, bbbbbabbb do tohoto jazyka patˇr´ı, zat´ımco
slova babba, bbbababbba nikoliv.
Rozhodnˇete, zda jazyk L je ˇci nen´ı regul´arn´ı a dokaˇzte:
• Pokud L je regul´arn´ı, uved’te regul´arn´ı gramatiku generuj´ıc´ı anebo koneˇcn´
y deterministick´
y automat akceptuj´ıc´ı dan´
y jazyk. Gramatiku/automat zapiˇste se vˇsemi form´aln´ımi
n´aleˇzitostmi.
• Pokud L nen´ı regul´arn´ı, dokaˇzte tuto skuteˇcnost pomoc´ı Lemmatu o vkl´ad´an´ı (tzv.
Pumping Lemma).