tajg-zadania-3, Elektronika, Podstawy Automatyki
[ Pobierz całość w formacie PDF ]
3.1.
Niech
A = {a, b, c, d}
i
R
A
A
. Znaleźć
R
*
i
R
+
, gdy:
(a) R = { (a,b), (b,c), (c,d) }
(b) R = { (a,c), (d,b), (c,d) }
(c) R = { (a,b), (a,c), (a,d), (b,d), (b,c), (c,d) }
(d) R = { (a,b), (b,c), (c,d), (d,a) }
(e) R = { (a,b), (a,c), (a,d), (d,c), (d,b), (d,a) }
(f) R = { (a,b), (c,d), (a,d), (c,b) }
(g) R = { (a,b), (b,a), (c,d), (d,c) }
(h) R = { (a,b), (a,c), (a,d), (b,a), (c,a), (d,a) }
3.2.
Niech
R
będzie relacją nad alfabetem
A
(
R
A
A).
Wykazać, że istnieje dokładnie
jedna relacja
R
e
, taka że:
(1)
R
R
e
(2)
R
e
jest relacją równoważności w zbiorze
A
(3) jeśli
R’
jest pewną relacją równoważności nad alfabetem
A
oraz
R
R’
to
R
e
R
’
(
R
e
nazywa się najmniejszą relacją równoważności zawierającą
R
).
3.3.
Dana jest gramatyka
G = < N, T, P, Z >
oraz relacje
FIRST
i
LAST
określone na
zbiorze N
(X
Y
)
P : X
N, Y
N
T,
(N
T)
*
T)
*
Dla poniższych gramatyk wyznaczyć zbiory
head(X)
i
tail(X)
dla wszystkich
X
(X
Y)
P : X
N, Y
N
T,
(N
N
, przy
czym zbiory te są zdefiniowane jak poniżej:
head(X) = { Y | (X,Y)
FIRST
*
, X
N, Y
N
T }
tail(X) = { Y | (X,Y)
FIRST
*
, X
N, Y
N
T }
(a) S
S g | A
A
C f B | C e
B
e
C
A
(b) E
T | E + T
T
F | T * F
F
a | ( E )
T zgodnie z poniższymi definicjami:
X
FIRST
Y
X
LAST
Y
[ Pobierz całość w formacie PDF ]