Wrocław, 12 listopada 2015
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 24 języków formalnych.
e) Zbiór wszystkich słów nad alfabetem A definiuje pewien nowy alfabet Aó�.
2. Niech A =def {0, 1} oraz B =def {a, b, c}. Czy A* ~ B*?
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) L1 = {1n | 1 Ł� n Ł� 6}
b) L2 = {0n 1n | n ��Nat}
c) L3 = {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^vn��L dla dowolnego n��Nat.
8. Dana jest gramatyka G = , 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 oraz 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ę G , która generuje taki sam język formalny jak
gramatyka G, to znaczy L(G) = L(G )?
9. Przedstawić drzewa rozbioru składniowego dla wszystkich słów długości 4 generowanych
przez gramatykę z zadania 8.
10. Zdefiniować gramatykę generującą następujące zbiory:
a) zbiór wszystkich palindromów (słów, które można odczytywać tak samo zarówno w
przód jak i wspak) nad alfabetem {a, b},
b) zbiór wszystkich słów nad alfabetem {a, b} zawierających dokładnie dwa razy więcej
symboli a niż symboli b,
c) L = {aibjck | i ą� j lub j ą� k}.
13. Dana jest gramatyka G = <{a, b}, {S}, {S ::= aS | aSbS | e�}, S>. Udowodnić, że
L(G) = {x | każdy przedrostek x ma co najmniej tyle symboli a, co symboli b}
14. Dla wybranego języka programowania, na przykład, C, C++, Java, zdefiniować gramatykę
określającą wybrany podzbiór wyrażeń arytmetycznych z tego języka.