IB102 – úkol 3, příklad 1 – řešení 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}
a) Jazyk L1 není regulární.
Neregularitu jazyka L1 dokážeme obměnou tvrzení Lemmatu o vkládání.
• Nechť n ∈ N je libovolné přirozené číslo, nadále pevné.
• Zvolme slovo w = an
#an
. Slovo w jistě patří do jazyka L1, protože slovo an
je
podslovem slova an
, a zároveň jistě platí |w| ≥ n.
• Nechť x, y, z ∈ Σ∗
jsou libovolná slova taková, že platí w = xyz, |xy| ≤ n a y = ε.
Tedy slova x, y, z musí být ve tvaru
x = ak
,
y = al
,
z = an−k−l
#an
pro vhodná čísla k, l taková, že k ≥ 0, l > 0 a k + l ≤ n.
• Zvolme i = 0, potom platí
xyi
z = xy0
z = xz = ak
an−k−l
#an
= an−l
#an
.
Ale pak slovo xy0
z nenáleží do jazyka L1, protože platí l > 0, a tudíž slovo an
nemůže být podslovem slova an−l
. Tedy z Lemmatu o vkládání vyplývá, že jazyk
L1 není regulární.
b) Jazyk L2 je regulární.
Klíčové pozorování je, že platí rovnost L2 = {a, b}∗
. Libovolné slovo w ∈ {a, b}∗
lze
totiž napsat ve tvaru w = w · ε a ε je jistě podslovem slova w. Stačí tedy najít
deterministický konečný automat akceptující jazyk {a, b}∗
. Takovým automatem je
například automat
q0
a, b
.