Zadanie 2. Słowa (14 pkt)
Niech
{
}
b
a
A
,
będzie dwuliterowym alfabetem. Napisem nad alfabetem A nazywamy
skończony ciąg znaków z tego alfabetu o długości większej od zera. Np. takimi napisami są:
a, ab, aba, baba, aaaa
Długość napisu w będziemy oznaczać przez w . Zatem
3
aba
Jeżeli w1 i w2 są napisami, to przez w1w2 będziemy oznaczali napis zbudowany z napisu w1
i z następującego po nim napisu w2. Np. dla
ab
w =
1
i
aa
w =
2
,
abaa
w
w
2
1
Zdefiniujemy teraz napisy 2-regularne. Każdy napis złożony tylko z jednej litery jest
2-regularny. Jeżeli napis w jest 2-regularny, to napis ww jest też 2-regularny. Żadne inne
napisy nie są 2-regularne.
Oto procedura rekurencyjna 2REG(w), która sprawdza, czy dany napis w nad alfabetem A jest
2-regularny.
Specyfikacja:
Dane: napis w o długości n (n ≥ 1), składający się z liter należących do alfabetu A.
Wynik: odpowiedź TAK, jeśli napis w jest napisem 2-regularnym; odpowiedź NIE, jeśli napis
w nie jest napisem 2-regularnym.
2REG(w);
krok 1: jeśli
1
w
, to wynikiem jest TAK
krok 2: jeśli
1
w
i w jest nieparzyste, to wynikiem jest NIE
krok 3: jeśli
1
w
i w jest parzyste, to:
krok 3.1: podziel napis w na dwa napisy w1 i w2 o takiej samej długości i takie,
że
2
1w
w
w =
krok 3.2: jeśli
2
1
w
w ≠
, to wynikiem jest NIE
krok 3.3: wynikiem jest wynik wywołania 2REG(w1)
a) Wypisz parametry wszystkich wywołań rekurencyjnych funkcji 2REG dla poniższych
napisów oraz podaj wynik jej działania:
i.
aabbaabb
ii.
aaaaaaaa
iii.
bbbbbbbbbbbbbbbbbbbb
np.: dla napisu w = abab, parametry wszystkich wywołań rekurencyjnych funkcji 2REG
i wynik jej działania są następujące:
abab→ab→NIE
Poziom rozszerzony - część I
7
b) Jakiej długości są napisy 2-regularne? Odpowiedź uzasadnij.
8
Poziom rozszerzony - część I
c) Ile jest napisów 2-regularnych o długości n (n ≥ 1) nad alfabetem A? Odpowiedź
uzasadnij.
d) Pewnym uogólnieniem napisów 2-regularnych są napisy 3-regularne.
Każdy napis jednoliterowy jest 3-regularny. Jeśli napis w jest 3-regularny, to każdy
z napisów wxw, wwx, gdzie x jest dowolnym napisem nad alfabetem A i takim, że długość
x jest taka sama jak długość w, jest napisem 3-regularnym. Żaden inny napis nie jest
3-regularny.
Przykładowymi napisami 3-regularnymi są: a, aba, abaabaaaa.
Ale aaaabaaba nie jest 3-regularny.
Napisz w wybranej przez siebie notacji (lista kroków, schemat blokowy lub język
programowania) algorytm zgodny ze specyfikacją, który sprawdza 3-regularność danego
napisu.
Specyfikacja:
Dane: napis w, o długości n (n ≥ 1), składający się z liter należących do alfabetu A.
Wynik: odpowiedź TAK, jeśli napis w jest napisem 3-regularnym; odpowiedź NIE, jeśli napis
w nie jest napisem 3-regularnym.
Algorytm
Poziom rozszerzony - część I
9
Nr zadania
2 a)
2 b)
2 c)
2 d)
Maks. liczba pkt
3
2
2
7
Wypełnia
egzaminator! Uzyskana liczba pkt
10
Poziom rozszerzony - część I
przeznaczonym.
","solutions":[]}