IB102 – úkol 3, příklad 1 – řešení 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ý }
1. Jazyk La není regulární. Jeho neregularitu dokážeme pomocí obměny tvrzení Lemmatu
o vkládání.
• Buď n ∈ N libovolné přirozené číslo, nadále pevné.
• Zvolme slovo w = an
bn
. Slovo w jistě patří do jazyka L a jeho délka je |w| =
2n ≥ n.
• Uvažme rozdělení slova w na libovolné tři částí w = xyz splňující podmínky
|xy| ≤ n a y = ε. Pak slova x, y, z musí být ve tvaru
x = ak
,
y = al
,
z = an−k−l
bn
pro vhodná čísla k, l ∈ N0. Navíc musí platit l > 0, protože víme, že y = ε.
• Zvolme i = 0 a uvažme slovo xyi
z. Dosazením, použitím definice mocniny slova
a algebraickými úpravami dostaneme
xy0
z = xz = ak
· an−k−l
bn
= an−l
bn
.
Slovo xy0
z jistě nepatří do jazyka L, protože l > 0, a tedy z Lemmatu o vkládání
dostáváme, že jazyk L není regulární.
2. Jazyk Lb je regulární. Klíčové pozorování je, že mezi každými dvěma výskyty podslova
ab se musí objevit výskyt podslova ba a naopak mezi každými dvěma výskyty
podslova ba se musí objevit výskyt podslova ab. Takže jazyk Lb můžeme zapsat
jiným způsobem jako
Lb = {w ∈ {a, b}∗
| slovo w začíná a končí stejným písmenem} ∪ {ε}.
Pak už je jednoduché popsat jazyk Lb regulární gramatikou G = ({S, A, B}, {a, b}, P, S),
kde
P = {S → ε | a | b | aA | bB,
A → a | aA | bA,
B → b | aB | bB}.