IB102 – úkol 3, příklad 1 Odevzdání: 6. 10. 2014
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 deterministický 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) L1 = {u#v | u, v ∈ {a, b}∗
a slovo v je podslovem slova u}
b) L2 = {uv | u, v ∈ {a, b}∗
a slovo v je podslovem slova u}