Języki Formalne i Złożoność Obliczeniowa

Zestaw ćwiczeń – Część 1 (Zakres: Rozdział 1 i 2)
Czas trwania: \(4 \times 45\text{ min}\) (ok. 3 godziny zegarowe)

Rozdział 1: Podstawy matematyczne i definicje języków

Zadanie 1: Operacje na zbiorach

Niech dane będą zbiory \(A = \{a, b, c\}\), \(B = \{b, c, d\}\) oraz \(C = \{a, d\}\). Wyznacz: a) \(A \cup B\)
b) \(A \cap B\)
c) \(A \setminus B\) oraz \(B \setminus A\)
d) \((A \cup B) \setminus C\)
e) \(A \times C\) (iloczyn kartezjański)
f) \(\mathcal{P}(A)\) oraz \(\mathcal{P}(A \cap B)\) (zbiory potęgowe)

Zadanie 2: Operacje na słowach

Niech \(\Sigma = \{a, b, c\}\). Dane są słowa \(w = aba\), \(u = bb\) oraz \(v = cab\). Wyznacz: a) Długości słów: \(|w|\), \(|u|\), \(|v|\) oraz \(|\epsilon|\)
b) Konkatenacje: \(wu\), \(uw\) oraz \(w\epsilon u\)
c) Odwrócenia: \(w^R\), \(v^R\) oraz \((wu)^R\)
d) Sprawdź, czy zachodzi równość \((wu)^R = u^R w^R\)
e) Potęgi słów: \(w^2\), \(u^3\) oraz \(v^0\)
f) Wszystkie prefiksy oraz wszystkie sufiksy słowa \(v\)

Zadanie 3: Operacje na językach

Niech \(\Sigma = \{a, b\}\). Dane są języki \(L_1 = \{a, \epsilon\}\), \(L_2 = \{ab, b\}\) oraz \(L_3 = \emptyset\). Wyznacz: a) Sumę \(L_1 \cup L_2\)
b) Konkatenacje \(L_1 L_2\) oraz \(L_2 L_1\)
c) Konkatenację \(L_2 L_3\)
d) Potęgi \(L_2^2\), \(L_1^3\) oraz \(L_2^0\)
e) Opisz słownie i wypisz 5 najkrótszych słów należących do domknięcia Kleene'ego \(L_1^*\) oraz \(L_2^+\)

Zadanie 4: Definiowanie języków

Używając formalnego opisu (notacji zbiorów \(\{w \in \Sigma^* : \dots\}\)), zdefiniuj następujące języki nad alfabetem \(\Sigma = \{0, 1\}\): a) \(L_A\): Język wszystkich słów o długości dokładnie \(3\).
b) \(L_B\): Język wszystkich słów o długości co najwyżej \(2\).
c) \(L_C\): Język wszystkich słów, które zaczynają się na \(0\) i kończą na \(1\).
d) \(L_D\): Język wszystkich palindromów (słów, które czytane od przodu i od tyłu są takie same, tj. \(w = w^R\)).
e) \(L_E\): Język słów zawierających tyle samo symboli \(0\), co symboli \(1\) (ozn. \(|w|_0 = |w|_1\)).
f) Niech \(L_F = \{0^n 1^n : n \ge 0\}\) oraz \(L_G = \{0^n 1^m : n, m \ge 1\}\). Które ze słów: \(\epsilon\), \(01\), \(001\), \(0011\), \(0111\), \(10\) należą do \(L_F\), a które do \(L_G\)?

Rozdział 2: Języki Regularne – Automaty Skończone (DFA / NFA)

Zadanie 5: Projektowanie Deterministycznych Automatów Skończonych (DFA)

Dla każdego z poniższych języków nad alfabetem \(\Sigma = \{a, b\}\), narysuj diagram deterministycznego automatu skończonego (DFA), który go akceptuje: a) \(L_A = \{w \in \Sigma^* : w \text{ zawiera podsłowo } ab\}\)
b) \(L_B = \{w \in \Sigma^* : w \text{ kończy się na } bb\}\)
c) \(L_C = \{w \in \Sigma^* : w \text{ zawiera nieparzystą liczbę symboli } a\}\)
d) \(L_D = \{w \in \Sigma^* : |w| \text{ jest podzielne przez } 3\}\)
e) \(L_E = \{w \in \Sigma^* : w \text{ NIE zawiera podsłowa } aaa\}\)
f) \(L_F = \{w \in \Sigma^* : w \text{ zaczyna się i kończy tym samym symbolem oraz } |w| \ge 2\}\)
g) \(L_G = \{w \in \Sigma^* : \text{liczba symboli } a \text{ jest parzysta ORAZ liczba symboli } b \text{ jest nieparzysta}\}\) (konstrukcja produktowa)

Zadanie 6: Projektowanie Niedeterministycznych Automatów Skończonych (NFA / \(\epsilon\)-NFA)

Dla każdego z poniższych języków nad alfabetem \(\Sigma = \{0, 1\}\), zaprojektuj niedeterministyczny automat skończony (może zawierać \(\epsilon\)-przejścia), który go akceptuje. Postaraj się, aby automat miał jak najmniej stanów: a) \(L_A = \{w \in \Sigma^* : w \text{ zaczyna się na } 01 \text{ LUB kończy się na } 01\}\)
b) \(L_B = \{w \in \Sigma^* : \text{trzeci symbol od końca to } 1\}\)
c) \(L_C\) opisany wyrażeniem regularnym \((01)^* + 1^*\)
d) \(L_D = \{w \in \Sigma^* : w \text{ zawiera podsłowo } 00 \text{ lub podsłowo } 111\}\)
e) \(L_E = \{w \in \Sigma^* : |w| \text{ jest parzyste LUB zawiera co najmniej dwie jedynki}\}\)

Zadanie 7: Konwersja NFA \(\to\) DFA (Konstrukcja Podzbiorowa)

Przekształć poniższe automaty niedeterministyczne na równoważne im automaty deterministyczne (DFA), używając algorytmu konstrukcji podzbiorowej. Pomiń stany nieosiągalne.

Przypadek 1: NFA nad \(\Sigma = \{a, b\}\), akceptujący słowa kończące się na \(a\):

Przypadek 2: NFA nad \(\Sigma = \{0, 1\}\):

Przypadek 3 (\(\epsilon\)-NFA \(\to\) DFA): Automat z \(\epsilon\)-przejściami nad \(\Sigma = \{a, b\}\):

Zadanie 8: Minimalizacja DFA

Zminimalizuj poniższe automaty DFA (usuń stany nieosiągalne, a następnie wyznacz klasy równoważności stanów metodą tabelaryczną lub podziału zbioru stanów):

Automat 1: \(\Sigma = \{0, 1\}\), \(Q = \{A, B, C, D, E, F\}\), stan początkowy: \(A\), \(F_{akc} = \{C, D, E\}\):

Automat 2: \(\Sigma = \{a, b\}\), \(Q = \{q_0, q_1, q_2, q_3, q_4\}\), stan początkowy: \(q_0\), \(F_{akc} = \{q_2, q_4\}\):

Rozdział 2: Wyrażenia Regularne i Gramatyki Regularne

Zadanie 9: Konstrukcja Wyrażeń Regularnych

Napisz wyrażenia regularne opisujące następujące języki nad alfabetem \(\Sigma = \{0, 1\}\): a) \(L_A\): Język słów zaczynających się na \(1\), a kończących na \(0\).
b) \(L_B\): Język słów zawierających co najmniej trzy jedynki (\(1\)).
c) \(L_C\): Język słów zawierających dokładnie dwie lub dokładnie trzy jedynki (\(1\)).
d) \(L_D\): Język słów, w których po każdym \(0\) musi natychmiast wystąpić \(1\) (np. \(\epsilon, 11, 01, 11011 \in L_D\), ale \(00, 10, 010 \notin L_D\)).
e) \(L_E\): Język słów o długości parzystej.
f) \(L_F\): Język słów, w których na pozycjach nieparzystych stoi zawsze symbol \(1\).
g) \(L_G\): Język wszystkich słów oprócz słowa pustego \(\epsilon\) oraz słowa \(01\).
h) \(L_H\): Język słów, w których symbole \(0\) i \(1\) występują naprzemiennie (np. \(\epsilon, 0, 1, 010, 1010\)).

Zadanie 10: Konwersja Wyrażenie Regularne \(\to\) \(\epsilon\)-NFA (Konstrukcja Thompsona)

Stosując ściśle algorytm konstrukcji Thompsona, narysuj krok po kroku automaty \(\epsilon\)-NFA dla następujących wyrażeń regularnych nad \(\Sigma = \{a, b\}\): a) \(R_1 = (a + b)^* a\)
b) \(R_2 = a b^* + b\)
c) \(R_3 = (a b + b)^* a\)
d) Po wykonaniu podpunktu a), przekształć otrzymany automat \(\epsilon\)-NFA na równoważny DFA i go zminimalizuj.

Zadanie 11: Konwersja DFA \(\to\) Wyrażenie Regularne (Eliminacja Stanów / Równania Ardena)

Użyj metody eliminacji stanów (lub układu równań z lematem Ardena: jeśli \(X = AX + B\) i \(\epsilon \notin A\), to \(X = A^*B\)), aby znaleźć wyrażenia regularne równoważne poniższym automatom:

Automat 1: Język słów o parzystej liczbie zer nad \(\Sigma = \{0, 1\}\):

Automat 2: Automat nad \(\Sigma = \{a, b\}\):

Automat 3: Automat nad \(\Sigma = \{a, b\}\):

Zadanie 12: Gramatyki Regularne

a) Przekształć automat DFA z Zadania 11 (Automat 1 – parzysta liczba zer) na równoważną mu gramatykę regularną (prawostronnie liniową).
b) Jaki język nad \(\Sigma = \{a, b\}\) generuje poniższa gramatyka \(G_1\)? Zapisz go za pomocą wyrażenia regularnego:

Rozdział 2: Własności Domknięcia, Lemat o Pompowaniu i Twierdzenie Myhilla-Nerode'a

Zadanie 13: Własności domknięcia języków regularnych

a) Języki \(L_1 = \{a^n : n \ge 0\}\) (czyli \(a^*\)) oraz \(L_2 = \{b^n : n \ge 0\}\) (czyli \(b^*\)) są regularne. Czy język \(L = L_1 \cap L_2\) jest regularny? Uzasadnij odpowiedź i wypisz wszystkie słowa należące do języka \(L\).
b) Wiadomo, że języki regularne są domknięte ze względu na dopełnienie, sumę, przecięcie i konkatenację. Korzystając z praw De Morgana, udowodnij, że jeśli języki są domknięte na sumę i dopełnienie, to muszą być również domknięte na przecięcie (\(L_1 \cap L_2\)).
c) Czy każdy podzbiór języka regularnego jest językiem regularnym? Podaj dowód lub kontrprzykład (wskazówka: rozważ język \(\Sigma^*\)).
d) Niech \(L_1\) będzie językiem regularnym, a \(L_2\) językiem nieregularnym. Czy język \(L_1 \cup L_2\) może być regularny? Czy zawsze jest nieregularny? Podaj odpowiednie przykłady.

Zadanie 14: Lemat o Pompowaniu (Dowodzenie nieregularności)

Wykorzystaj Lemat o Pompowaniu dla języków regularnych, aby udowodnić (przez sprzeczność), że poniższe języki nie są regularne: a) \(L_A = \{0^k 1^{2k} : k \ge 0\} = \{\epsilon, 011, 001111, \dots\}\)
b) \(L_B = \{a^n b^n : n \ge 0\}\)
c) \(L_C = \{w \in \{a, b\}^* : w = w^R\}\) (język palindromów)
d) \(L_D = \{0^i 1^j : i > j \ge 0\}\) (wskazówka: rozważ pompowanie w dół, tj. dla \(k = 0\))
e) \(L_E = \{a^{n^2} : n \ge 0\} = \{\epsilon, a, aaaa, aaaaaaaaa, \dots\}\)
f) \(L_F = \{w \in \{0, 1\}^* : |w|_0 = |w|_1\}\) (wskazówka: możesz użyć lematu o pompowaniu bezpośrednio lub skorzystać z domkniętości na przecięcie z językiem \(0^*1^*\))

Zadanie 15: Relacja nierozróżnialności i Twierdzenie Myhilla-Nerode'a

Przypomnienie: Dwa słowa \(x, y \in \Sigma^*\) są w relacji \(\sim_L\) (\(x \sim_L y\)), jeśli dla każdego słowa \(z \in \Sigma^*\) zachodzi: \(xz \in L \iff yz \in L\). Język \(L\) jest regularny wtedy i tylko wtedy, gdy indeks relacji \(\sim_L\) (liczba jej klas abstrakcji) jest skończony.

a) Wyznacz wszystkie klasy abstrakcji relacji \(\sim_L\) dla języka \(L = \{w \in \{a, b\}^* : w \text{ kończy się na } ab\}\). Ile ich jest? Jak mają się one do minimalnego automatu DFA dla tego języka?
b) Wyznacz wszystkie klasy abstrakcji relacji \(\sim_L\) dla języka \(L = \{w \in \{0, 1\}^* : |w|_0 \text{ jest parzysta}\}\).
c) Wykorzystaj Twierdzenie Myhilla-Nerode'a, aby udowodnić, że język \(L_1 = \{a^n b^n : n \ge 0\}\) nie jest regularny (wskaż nieskończony zbiór słów parami rozróżnialnych względem \(\sim_{L_1}\)).
d) Wykorzystaj Twierdzenie Myhilla-Nerode'a, aby udowodnić, że język \(L_2 = \{w w^R : w \in \{0, 1\}^*\}\) (palindromy parzystej długości) nie jest regularny.
e) Wykorzystaj Twierdzenie Myhilla-Nerode'a, aby udowodnić, że język \(L_3 = \{a^p : p \text{ jest liczbą pierwszą}\}\) nie jest regularny.