Wrocław, 14 listopada 2012
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania – lista 6
1. Niech A =
def
{+, =}. Które z poniższych zdań są prawdziwe?
a) Można utworzyć co najwyżej skończoną liczbę języków formalnych nad alfabetem A.
b) Można utworzyć dokładnie 4 słowa nad alfabetem A.
c) Zbiór { ++, +++, =, += } jest pewnym językiem formalnym nad A.
d) Nad alfabetem A można utworzyć dokładnie 2
4
języków formalnych.
e) Zbiór wszystkich słów nad alfabetem A definiuje pewien nowy alfabet A
.
3. Czy zbiór liczb naturalnych Nat jest równoliczny ze zbiorem Nat
*
– zbiorem wszystkich
skończonych ciągów nad Nat?
4. Czy zbiór wszystkich języków formalnych nad przeliczalnym alfabetem A jest przeliczalny?
5. Niech L będzie językiem formalnym nad alfabetem {0, 1}. Dwa słowa u, v
{0, 1}
*
są
równoważne względem języka L, co oznacza się u ~
L
v, jeżeli
x
{0, 1}
*
(u ^ x
L
v ^ x
L)
Pokazać, że ~
L
jest relacją równoważności.
6. Przedstawić klasy abstrakcji relacji równoważności słów ~
L
względem następujących
języków:
a) L
1
= {1
n
| 1
n
6}
b) L
2
= {0
n
1
n
| n
Nat}
c) L
3
= (0011)
7. Pokazać, że jeśli dla pewnych słów u
L oraz v
{0, 1}
*
zachodzi u^v
[u]
~L
, gdzie
~L
jest
relacją równoważności słów względem języka L, to u^v
n
L dla dowolnego n
Nat.
8. Dana jest gramatyka G = <T, N, P, S
>, gdzie:
T =
def
{A, B, C}
N =
def
{a, b, c}
P =
def
{a ::= A | aA | bC
b ::= BcC
c ::= abC | ABc | AbC }
S = a
Czy słowa AAAA, ABCA należą do języka generowanego przez G? Podać zbiór wszystkich
słów długości 1, 2 i 3 należących do języka generowanego przez G. Scharakteryzować zbiór
wszystkich słów generowanych przez gramatykę G. Czy można zdefiniować „prostszą”
gramatykę, która generuje taki sam język formalny jak gramatyka G?
