IB102 – úkol 3, příklad 1 Odevzdání: 19. 10. 2015
Vypracoval(a): UČO:
Skupina:
1. [3 body] O každém z následujících jazyků nad abecedou Σ = {a, b} rozhodněte, zda
je regulární, a vaše tvrzení dokažte.
Tedy je-li vaše odpověď, že se jedná o regulární jazyk, uveďte příslušnou regulární
gramatiku nebo konečný automat včetně všech formálních náležitostí. Pokud se podle vás
naopak o regulární jazyk nejedná, dokažte tuto skutečnost pomocí Lemmatu o vkládání
(Pumping lemma).
a) La = {w ∈ Σ∗
| počet výskytů podslov aa a bb ve slově w je stejný }
b) Lb = {w ∈ Σ∗
| počet výskytů podslov ab a ba ve slově w je stejný }