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 24 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) 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 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?
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.
15. Przedstawić w postaci diagramów składniowych produkcje gramatyk zdefiniowanych w
poprzednich zadaniach.