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?

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 = {a

i

b

j

c

k

| i



j lub j



k}.

13. Dana jest gramatyka G = <{a, b}, {S}, {S ::= aS | aSbS |



}, 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.