JFiZO - Lista 5
JFiZO - Zadanie 11.006
Pokazać, że jeśli L\subseteq \Sigma^* jest regularny, to Lustro(L)=\{wv^R\in \Sigma^* : wv\in L\} też jest.
Niech A=(Q_A, \Sigma, \delta_A, q^A_0, F_A) będzie DFA takim, że, L(A)=L. Skonstruujemy sobie NFA B rozpoznający Lustro(L).
Q_B=Q_A\times 2^{Q_A}\times\{0,1\} - oznacza to trójki złożone ze stanu A, ze stanu odwróconego A (podzbioru Q_A) i jednej flagi. Odwrócony A to NFA powstały przez odwrócenie strzałek (funkcja przejścia staje się relacją). Flagę będziemy czytać jako „czy przekroczyłeś już granicę w|v”.
q^B_0=\langle q^A_0, F_A, 0\rangle
Zasada działania jest taka, że czytamy literki i przesuwamy się po lewej współrzędnej do pewnego miejsca (czyli wczytujemy w), w pewnym momencie przełączamy flagę (tylko raz; odpowiedni moment dostajemy od tego… jak go JMA nazywa? adwokata? sędziego? wyroczni?) i zaczynamy jechać po drugiej współrzędnej, czytając literki w odwrotnej kolejności niż by to było w L (co odpowiada v^R). W momencie, gdy nasze współrzędne się spotkają (lewa będzie należeć do drugiej), mamy stan akceptujący.
Formalniej:
\delta_B(\langle q, R, 0 \rangle, a) = \{\langle\delta_A(q,a),R,0\rangle\}\cup \{\langle q, \{p\in Q_A : \delta_A(p,a)\in R\}, 1\rangle\},
\delta_B(\langle q, R, 1 \rangle, a) = \{\langle q, \{p\in Q_A : \delta_A(p,a)\in R\}, 1\rangle\},
F_B = \{\langle q, R, \_\rangle : q \in R\}.
JFiZO - Zadanie 11.007
Źle odczytałem definicję, więc to rozwiązanie prawdopodobnie nie działa.
Pokazać, że DFA rozpoznający Lustro(L) może potrzebować wykładniczo więcej stanów niż DFA rozpoznający L.
Niech L = L_{(0+1)^90(0+1)^*} będzie językiem słów nad \{0,1\} mających 0 na dziesiątej pozycji.
Każdy potrafi narysować DFA o 12 stanach, który go rozpoznaje (wczytałem 0, 1, …, 8, 9 znaków; wczytałem 10. i był on zerem; nie był zerem).
Język Lustro(L) jest może nieco bardziej skomplikowany i nie chce nam się pisać dla niego regexpu, ale wiemy, że każde słowo w nim musi mieć zero na dziesiątej pozycji od końca. Oh wait, zad. 1 mówi nam, że DFA rozpoznający taki język potrzebuje 1024 stanów.
A jeszcze do tego musi zapewne sprawdzać nadal zero na początku. Tak czy siak, mamy 1024=(2-\epsilon)^{12} stanów. Można to uogólnić do dowolnego k.
No faktycznie, jest źle. Ale można troszeczkę poprawić i będzie lepiej: rozważmy język L_{2(0+1)^90(0+1)^*}. Wtedy w Lustro(L) znajdują się między innymi wyrazy opisywane przez (0+1)^*0(0+1)^92, których jest co najmniej 512. Załóżmy nie wprost, że DFA rozpoznający ten język (całe lustro) ma mniej niż 512 stanów, wtedy dla dwóch wyrazów osiąga ten sam stan, etc. etc.
JFiZO - Zadanie 11.008
Czy jeśli L jest regularny, to Lustro(L) również jest regularny?
Źle odczytałem definicję, więc to rozwiązanie prawdopodobnie nie działa.
No nie bardzo.
Weźmy sobie L=0^n1^n. Wtedy Lustro(L)=0^n1^n1^m0^m.
Niech N będzie stałą z lematu o pompowaniu.
Rozważmy słowo 0^N1^{2N}0^N\cdots zad. 40
L=a^nb^mc^md^n (S\rightarrow aSd | A | \epsilon, A \rightarrow bAc | \epsilon).
N-stała z lematu, w=a^Nb^Nd^Nc^N…
JFiZO - Zadanie 09.033
Zadanie 33. Czy język L_4 = \{w \in \{0, 1, 2\}^∗ : \exists x \in \{0, 1, 2\}^∗ \, w = xx\} jest bezkontekstowy?
Twierdzenie. Język L_4 nie jest bezkontekstowy.
Dowód. Rozpatrzmy język L = L_4 \cap L(0^*10^*10^*10^*1). Przecięcie języka bezkontekstowego z regularnym, daje nam język bezkontekstowy (dowodu jednak nie będzie, a mógłby polegać na łączeniu dwóch automatu w jeden).
Załóżmy nie wprost, że L jest bezkontekstowy. Na mocy bla bla lemat o pomopowaniu bla bla stała N.
Rozpatrzmy słowo w = 0^N10^N10^N10^N1. Nie da się go rozbić na sztyx taki, że |zty| \leq N.
JFIZO - Zadanie 09.047
Mało zadeptany śnieg - drak (zad 46)
int fun(n)
{
for (i = 0; ; i++) {
dom = 0;
for (arg = 0; arg < i; arg++) {
for (steps = 0; steps < i - arg; steps++) {
if (fi_n(arg) == 1 po steps krokach) {
dom++;
break;
}
}
}
if (dom >= 7)
return 1;
}
}
JFIZO - Zadanie 09.048
Zbiory rekurencyjnie przeliczalne A, B, C, D. Każda liczba naturalna należy do dokładnie dwóch z nich. Zbiory są rekurencyjnie przeliczalne, więc istnieją f_A, f_B, f_C, f_D, takie, że n \in X \Rightarrow f_X(n) = 1. Zbudujmy g_X, takie, że n \in X \Rightarrow g_X(n) = 1, n \not \in X \Rightarrow g_X(n) = 0:
int g_A(n) {
int count = 0;
for(i = 0; ; i += 100) {
if (w i krokach f_A(n) == 1) {
return 1;
} else {
for X (B, C, D) {
if (w i krokach f_X(n) == 1)
count++;
}
}
if (count == 2) return 0;
}
}
