Alphabet, string ve length
Hafta 2 notunda şöyle yazmıştın: "alfabe → language → language üzerinde yaptığımız bir işlem". Dersin bütün yapısı bu. Elinde birkaç sembol var. Onları yan yana yazarak kelimeler kuruyorsun. Bazı kelimeleri bir kümeye topluyorsun. Sonra şu soruyu soruyorsun: "Verilen kelime bu kümede mi?" Bu soruyu cevaplayan makineler dersin konusu.
- Alphabet: boş olmayan, sonlu bir küme. Elemanlarına symbol denir. Genelde $\Sigma$ ya da $\Gamma$ ile gösterilir: $\Sigma_1 = \{0,1\}$, $\Sigma_2 = \{a, b, \dots, z\}$, $\Gamma = \{0, 1, x, y, z\}$.
- String (over $\Sigma$): $\Sigma$'dan alınmış symbol'lerin sonlu bir dizisi. Araya virgül koymadan yazılır:
01001, $\Sigma_1$ üzerinde bir string'dir. - Length $|w|$: string'deki symbol sayısı. $|01001| = 5$. Length'i $n$ olan bir string'i $w = w_1 w_2 \cdots w_n$ diye yazarız, her $w_i \in \Sigma$.
- Empty string $\varepsilon$: length'i 0 olan tek string. Sayılardaki 0 gibi davranır. Tahtada programlamadaki karşılığı yazıldı:
String str = "";bir empty string,str2 = "a";ise length'i 1 olan bir string. - Reverse $w^R$: $w$'yi tersten yazmak, $w_n w_{n-1} \cdots w_1$. $(0011)^R = 1100$.
- Substring: $z$, $w$'nin içinde ardışık olarak geçiyorsa $w$'nin substring'idir.
cad,abracadabra'nın substring'i. - $\Sigma^n$: length'i tam $n$ olan bütün string'lerin kümesi. $|\Sigma| = k$ ise $|\Sigma^n| = k^n$, çünkü her pozisyon için $k$ seçenek var. $\Sigma^0 = \{\varepsilon\}$.
Hafta 2'deki Q1'i doğru çözmüştün: $\Sigma = \{0,1\}$ için length'i 2 olan string'ler 00, 01, 10, 11, length'i $n$ olanların sayısı $2^n$. Aşağıdaki araç aynı sayımı istediğin alphabet ile yapıyor. $\Sigma^j$'yi $\Sigma^{j-1}$'deki her string'in sonuna her symbol'ü ekleyerek kuruyor.
Önce tahmin et: $\Sigma = \{a, b, c\}$ için $\Sigma^3$'te kaç string var? $\Sigma^0$ boş küme mi, yoksa içinde bir eleman var mı?
- $\varepsilon$ bir symbol değil, bir string. $\Sigma = \{0,1\}$ ise $\varepsilon \notin \Sigma$ ama $\varepsilon \in \Sigma^0$.
- Alphabet sonlu olmak zorunda ve boş olamaz. String de her zaman sonludur.
- Substring ardışık olmalı.
ab,acb'nin substring'i değil: a ile b arasında c var.
$\Sigma = \{a, b, c\}$. Length'i 3 olan kaç string vardır?
Hangisi 0110'un substring'i değildir?
Concatenation, prefix ve string order
Hafta 2'deki Q3'ü bilememiştin. Bu yüzden burada yavaş gidiyoruz.
Concatenation iki string'i uç uca eklemek demek. Araya hiçbir şey girmez, hiçbir şey toplanmaz.
- $xy = 01\,110 = 01110$
- $yx = 110\,01 = 11001$
- $|xy| = |x| + |y| = 2 + 3 = 5$
- $xy \ne yx$: sıra önemli.
- $x = x_1 \cdots x_m$, $y = y_1 \cdots y_n$ ise $xy = x_1 \cdots x_m y_1 \cdots y_n$ ve $|xy| = |x| + |y|$.
- Concatenation commutative değil ($xy \ne yx$ olabilir), ama associative: $(xy)z = x(yz)$.
- $\varepsilon$ etkisiz eleman: $x\varepsilon = \varepsilon x = x$.
- $x^k$: $x$'i $k$ kez arka arkaya yazmak. $(01)^3 = 010101$, $0^4 = 0000$, $x^0 = \varepsilon$. Buradan $|x^k| = k\,|x|$.
- Prefix: $xz = y$ olacak bir $z$ varsa $x$, $y$'nin prefix'idir. Ayrıca $x \ne y$ ise proper prefix.
01,0110'un proper prefix'i; $\varepsilon$ her string'in prefix'i. - Prefix-free language: hiçbir eleman başka bir elemanın proper prefix'i değil. $\{0, 10, 11\}$ prefix-free; $\{0, 01\}$ değil.
- Shortlex order (string order): önce kısa string'ler, aynı length'tekiler sözlük sırasıyla. $\{0,1\}$ üzerinde: $(\varepsilon, 0, 1, 00, 01, 10, 11, 000, \dots)$. Düz sözlük sırası (lexicographic order) bütün string'leri sıralayamaz: $0, 00, 000, \dots$ hiç bitmez ve
1'e asla sıra gelmez.
- String'leri sayı gibi toplama:
01ile110'un concatenation'ı01110, binary toplamları olan111değil. - $0^3$ bir sayı değil,
000string'i. Bu yazım ileride $0^n 1^n$ gibi language'larda sürekli karşına çıkacak. - Reverse sırayı da çevirir: $(xy)^R = y^R x^R$. $(01\,110)^R = 011\,10$.
$x = 01$, $y = 110$. $yx$ nedir?
$|x| = 2$ ve $|y| = 3$ ise $|x^3 y|$ kaçtır?
Hangi language prefix-free'dir?
Language: $\Sigma^*$'ın bir alt kümesi
Derse şöyle başlandı: $\Sigma = \{0,1\}$ ve $L = \{0, 1, 10, 11, \dots, 101, \dots\}$, yani binary yazılmış sayılar. Bu string'ler üzerinde işlem de tanımlanabilir: 101 + 11 = 1000 ($5 + 3 = 8$).
Sayı olmayan veriler de string olarak yazılabilir. Tahtada node'ları 0, 1, 10, 11 olan bir graph şöyle kodlandı: önce node listesi, bir ayraç, sonra edge listesi: (0, 1, 10, 11 * 1-0, 1-10, 11-10, 0-11). Sonra $L = \{$valid graph representations due to the given representation$\}$ yazıldı. Kurala uymayan bir string (örneğin listede olmayan bir node'a edge veren) bu language'da değildir.
Notuna da "data representation: renk, satranç" yazmışsın. Fikir şu: her veri bir string'e çevrilebilir. O zaman "bu veri geçerli mi, bu graph'ın şu özelliği var mı?" soruları tek bir soruya dönüşür: bu string bu language'da mı?
- $\Sigma^*$: $\Sigma$ üzerindeki bütün string'lerin kümesi, $\varepsilon$ dahil. $\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \cdots$. $\{0,1\}^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, \dots\}$.
- Language: bir string kümesi. $\Sigma$ üzerindeki her language $L \subseteq \Sigma^*$.
- Küme yazımı: $\{w \mid w \text{ ends with } 1\}$ "1 ile biten bütün $w$'ler" diye okunur. Language sonlu da olabilir ($\{01, 10\}$), sonsuz da.
- $\emptyset$: empty language, hiç string içermez, $|\emptyset| = 0$.
- $\{\varepsilon\}$: sadece empty string'i içeren language, $|\{\varepsilon\}| = 1$.
- Power set $\mathcal{P}(A)$: $A$'nın bütün alt kümelerinin kümesi. $|A| = n$ ise $|\mathcal{P}(A)| = 2^n$. $\mathcal{P}(\{a,b\}) = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}$.
- $L \subseteq \Sigma^*$ demek $L \in \mathcal{P}(\Sigma^*)$ demek. Yani $\Sigma$ üzerindeki bütün language'ların kümesi tam olarak $\mathcal{P}(\Sigma^*)$.
$\Sigma^*$ sonsuz ama sayılabilir (countable): string'leri shortlex sırasıyla 1, 2, 3, … diye numaralayabilirsin. $\mathcal{P}(\Sigma^*)$ ise sayılamayacak kadar büyük (uncountable). Makineler (DFA, Turing machine) sonlu birer tarif olduğu için sayılabilir çoklukta. Demek ki hiçbir makinenin tanıyamadığı language'lar var. Bunu dönemin ikinci yarısında diagonalization ile göreceksin; vizede yok.
| Yazım | Ne? | Kaç eleman / length |
|---|---|---|
| $\varepsilon$ | bir string | length 0 |
| $\{\varepsilon\}$ | bir language | 1 string |
| $\emptyset$ | bir language | 0 string |
Hafta 2 notundaki benzetme: $\emptyset$ boş bir kutu, $\{\varepsilon\}$ ise içinde boş bir kağıt olan kutu. Kağıtta bir şey yazmıyor ama kutu boş değil.
$\Sigma^*$ sonsuz bir küme, ama içinde sonsuz uzunlukta bir string yok. Her elemanı sonlu.
Hangisi doğrudur?
$A = \{a, b, c\}$ için $|\mathcal{P}(A)|$ kaçtır?
İlk makine: state diagram ve $M_1$
Finite automaton, hafızası çok küçük bir bilgisayar modeli. Sipser'in ilk örneği bir market kapısının kontrolcüsü. İki state'i var: OPEN ve CLOSED. Dört input'u var: FRONT (öndeki pedde biri var), REAR (arkadaki pedde biri var), BOTH, NEITHER.
| state \ input | NEITHER | FRONT | REAR | BOTH |
|---|---|---|---|---|
| CLOSED | CLOSED | OPEN | CLOSED | CLOSED |
| OPEN | CLOSED | OPEN | OPEN | OPEN |
CLOSED'dan başlayıp FRONT, REAR, NEITHER, FRONT, BOTH, NEITHER, REAR, NEITHER input'larını alırsa şu state'lerden geçer: CLOSED, OPEN, OPEN, CLOSED, OPEN, OPEN, CLOSED, CLOSED, CLOSED. Bu makinenin hafızası tek bir bit: hangi state'te olduğu. Asansör, bulaşık makinesi ve termostat kontrolcüleri de aynı fikirle çalışır. Finite automaton'ların olasılıklı akrabası Markov chain'dir (notuna "transition'lar oklar oluyor" diye yazmıştın).
Şimdi soyut bir makineye geçelim. Aşağıdaki $M_1$'in state diagram'ı:
- Daire = state. $M_1$'in üç state'i var: $q_1, q_2, q_3$.
- "Boşluktan gelen" ok start state'i gösterir: $q_1$.
- Çift daire accept state'tir: $q_2$. (Notunda "O rejected state, OO accepted state" yazmışsın.)
- Oklar transition'dır. Ok üzerindeki symbol, o oktan hangi symbol okununca gidileceğini söyler.
0,1etiketi iki ayrı okun kısaltmasıdır.
Çalışma kuralı: start state'te başla. Input'u soldan sağa, birer symbol oku. Her symbol'de o symbol'ün okunu izle. Son symbol okununca bak: accept state'teysen accept, değilsen reject. Çıktı sadece bu iki cevaptan biri.
1101
- $q_1$'de başla.
- 1 oku, $q_1 \to q_2$.
- 1 oku, $q_2 \to q_2$.
- 0 oku, $q_2 \to q_3$.
- 1 oku, $q_3 \to q_2$.
- Input bitti, makine $q_2$'de, $q_2$ accept state: accept.
$M_1$ şunları da kabul eder: 1, 01, 11, 0101010101, 100, 0100, 110000, 0101000000. Reddettikleri: 0, 10, 101000.
Kendin çalıştır: DFA simulator
Kutudaki metin makinenin kendisi. Her satır bir transition: q1 0 -> q2 "$q_1$'de 0 okununca $q_2$'ye git" demek. start: ve accept: satırları start state'i ve accept state'leri verir, # ile başlayan kısım açıklamadır. Bu biçim hocanın DFA builder aracındakiyle aynı. Metni değiştirirsen diagram hemen yeniden çizilir.
Önce tahmin et: $M_1$, 0100'ü kabul eder mi? 101000'ü? Önce kağıtta izle, sonra aşağıda çalıştır.
- Accept edip durmak yok. Makine accept state'e erken gelip sonra oradan çıkabilir. Karar sadece input bittiği anda verilir: önemli olan durduğun yer değil, input bitince bulunduğun yer.
10'da $M_1$, $q_2$'den geçer ama $q_3$'te biter: reject. - DFA input'u her zaman soldan sağa, bir kez okur. Geri dönemez, symbol atlayamaz.
$M_1$ 0100 üzerinde hangi state'lerden geçer ve ne karar verir?
$M_1$, $\varepsilon$'u kabul eder mi?
"M1'i şu input'larda çalıştır, geçtiğin state'leri sırayla yaz, accept/reject söyle: 1101, 0100, 10, ε."
İpucu 1
Yukarıdaki $\delta$ tablosunu (ya da diagram'ı) önüne koy. Her symbol için tek bir hücreye bakıyorsun: "şu state'teyim, şu symbol geldi, nereye?" Listeye start state'i de yaz: $n$ symbol için $n+1$ state.
İpucu 2
Kararı sadece listenin son elemanı verir. $\varepsilon$'da liste tek elemanlı: start state.
Çözümü göster
1101: $q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \xrightarrow{1} q_2$. $q_2 \in F$: accept.0100: $q_1 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_2$. Accept: son 1'den sonra iki, yani çift sayıda 0 var.10: $q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_3$. $q_3 \notin F$: reject. Son 1'den sonra tek sayıda 0 var.- $\varepsilon$: hiç symbol okunmaz, makine $q_1$'de kalır. $q_1 \notin F$: reject.
$q_2$ ile $q_3$ arasındaki gidip gelme, son 1'den sonraki 0'ların tek mi çift mi olduğunu tutuyor. Derste söylenen "even/odd until now" state'leri bu fikir. Dördünü de simulator'da çalıştırıp kontrol edebilirsin.
Formal definition: 5-tuple ve $\delta$
Diagram sezgi için iyi, ama iki soruyu kesin cevaplamaz: "Hiç accept state olmayabilir mi?" ve "Her state'ten her symbol için tam bir ok mu çıkmalı?" Formal definition bu belirsizlikleri kaldırır ve bize bir notation verir.
$f : D \to R$, $D$'deki (domain) her elemana $R$'den (range) tam bir eleman atar. $Q \times \Sigma$, Cartesian product: bütün $(q, a)$ çiftleri, $q \in Q$, $a \in \Sigma$. $|Q \times \Sigma| = |Q| \cdot |\Sigma|$.
A finite automaton is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, where
- $Q$ is a finite set called the states,
- $\Sigma$ is a finite set called the alphabet,
- $\delta : Q \times \Sigma \to Q$ is the transition function,
- $q_0 \in Q$ is the start state, and
- $F \subseteq Q$ is the set of accept states.
Accept state'lere final state da denir. $\delta(x, 1) = y$, "$x$'ten $y$'ye 1 etiketli bir ok var" demek.
Tanımdan iki soru da cevaplanır. $F = \emptyset$ seçmek serbest, yani sıfır accept state olabilir. $\delta$ bir function olduğu için her $(q, a)$ çiftine tam bir sonraki state atanır: her state'ten her symbol için tam bir ok çıkar. Hiç ok yoksa function tanımsız kalır; iki ok varsa makine hangisine gideceğini bilemez. "Deterministic" kelimesi buradan gelir.
- $Q = \{q_1, q_2, q_3\}$: makinenin "hafızası" bu üç durumdan ibaret.
- $\Sigma = \{0, 1\}$: input'ta görülebilecek symbol'ler.
- $\delta$:
$\delta$ 0 1 $q_1$ $q_1$ $q_2$ $q_2$ $q_3$ $q_2$ $q_3$ $q_2$ $q_2$ - $q_1$ start state.
- $F = \{q_2\}$.
Tabloda $|Q| \cdot |\Sigma| = 3 \cdot 2 = 6$ hücre var ve hepsi dolu. Diagram ile 5-tuple aynı bilgiyi taşır; birinden diğerine her zaman geçebilirsin.
- "Is it really a DFA?" Sınavda en sık kaybedilen puan: sadece ilginç okları çizip geri kalanları unutmak. Tablodaki her hücre dolu olmalı. Gidecek yer yoksa bir dead state ekle (Bölüm 9). Hoca 26 Ekim'de çözümü bu kontrolle bitirdi.
- $\delta$'nın range'i $Q$: her çiftin cevabı bir state. Bir state kümesi değil (o NFA'da gelecek).
- $q_0$ bir state ($q_0 \in Q$), $F$ ise bir küme ($F \subseteq Q$). "$F = q_2$" değil "$F = \{q_2\}$" yaz.
- Start state aynı zamanda accept state olabilir. O zaman $\varepsilon$ kabul edilir (Bölüm 6, $M_3$).
"The following are the state diagrams of two DFAs, $M_1$ and $M_2$. Answer the following questions about each of these machines.
a. What is the start state?
b. What is the set of accept states?
c. What sequence of states does the machine go through on input aabb?
d. Does the machine accept the string aabb?
e. Does the machine accept the string $\varepsilon$?"
Bu alıştırmanın $M_1$ ve $M_2$'si yukarıdaki $M_1$'den farklı makineler; alphabet $\{a, b\}$. Diagram'lar kitaptaki şekilden yeniden çizildi.
İpucu 1
(a) ve (b) diagram'dan okunur: boşluktan gelen ok ve çift daireler. (c) için start state'ten başla ve a, a, b, b oklarını sırayla izle. Listeye start state'i de yaz: 4 symbol için 5 state çıkar.
İpucu 2
(e) için hiç ok izlemezsin. Tek soru: start state accept state mi? Simulator'da "Ex 1.1 M1" ve "Ex 1.1 M2" hazır makinelerini yükleyip kontrol edebilirsin.
Çözümü göster
| $M_1$ | $M_2$ | |
|---|---|---|
| (a) start state | $q_1$ | $q_1$ |
| (b) accept states | $\{q_2\}$ | $\{q_1, q_4\}$ |
(c) aabb üzerinde | $q_1, q_2, q_3, q_1, q_1$ | $q_1, q_1, q_1, q_2, q_4$ |
(d) aabb accept? | Hayır ($q_1 \notin F$) | Evet ($q_4 \in F$) |
| (e) $\varepsilon$ accept? | Hayır ($q_1 \notin F$) | Evet ($q_1 \in F$) |
Sipser'in arkadaki "Selected Solutions" kısmı da aynı cevapları veriyor.
"Give the formal description of the machines $M_1$ and $M_2$ pictured in Exercise 1.1."
İpucu 1
Beş parçayı sırayla yaz: $Q$, $\Sigma$, $\delta$, start state, $F$. $\delta$'yı tablo olarak ver.
İpucu 2
Tabloyu doldururken her state için iki soru sor: "a gelince nereye?", "b gelince nereye?" $M_1$ için 6, $M_2$ için 8 hücre olmalı.
Çözümü göster
$M_1 = (\{q_1, q_2, q_3\}, \{a, b\}, \delta_1, q_1, \{q_2\})$ ve $M_2 = (\{q_1, q_2, q_3, q_4\}, \{a, b\}, \delta_2, q_1, \{q_1, q_4\})$.
| $\delta_1$ | a | b | $\delta_2$ | a | b | |
|---|---|---|---|---|---|---|
| $q_1$ | $q_2$ | $q_1$ | $q_1$ | $q_1$ | $q_2$ | |
| $q_2$ | $q_3$ | $q_3$ | $q_2$ | $q_3$ | $q_4$ | |
| $q_3$ | $q_2$ | $q_1$ | $q_3$ | $q_2$ | $q_1$ | |
| $q_4$ | $q_3$ | $q_4$ |
"The formal description of a DFA $M$ is $(\{q_1, q_2, q_3, q_4, q_5\}, \{u, d\}, \delta, q_3, \{q_3\})$, where $\delta$ is given by the following table. Give the state diagram of this machine."
| $\delta$ | u | d |
|---|---|---|
| $q_1$ | $q_1$ | $q_2$ |
| $q_2$ | $q_1$ | $q_3$ |
| $q_3$ | $q_2$ | $q_4$ |
| $q_4$ | $q_3$ | $q_5$ |
| $q_5$ | $q_4$ | $q_5$ |
İpucu 1
Önce beş daire çiz. Start'ı ($q_3$) boşluktan gelen okla, accept state'i ($q_3$) çift daireyle işaretle. Sonra tablonun her hücresi için bir ok çiz: 10 ok.
İpucu 2
u hep bir numara azaltıyor, d bir numara artırıyor. Daireleri $q_1$'den $q_5$'e bir sıraya dizersen diagram düzgün çıkar. Uçlarda ne oluyor?
Çözümü göster
State'ler bir sıra hâlinde: u bir adım sola, d bir adım sağa götürür. $q_1$'de u ve $q_5$'te d self-loop olur (duvara çarpan bir sayaç gibi). Start ve tek accept state ortadaki $q_3$: makine, bu yürüyüş $q_3$'te biten string'leri kabul eder. Örneğin ud ve du kabul, u red.
$|Q| = 3$ ve $|\Sigma| = 2$ olan bir DFA'nın transition tablosunda kaç hücre vardır?
Bir DFA'da $F = \emptyset$ olabilir mi? Olursa hangi language'ı tanır?
Computation, $L(M)$ ve regular language
$M = (Q, \Sigma, \delta, q_0, F)$ bir finite automaton ve $w = w_1 w_2 \cdots w_n$, her $w_i \in \Sigma$ olsun. Aşağıdaki üç şartı sağlayan bir $r_0, r_1, \dots, r_n$ state dizisi varsa $M$ accepts $w$:
- $r_0 = q_0$ (start state'te başla),
- $\delta(r_i, w_{i+1}) = r_{i+1}$, $i = 0, \dots, n-1$ için ($\delta$'ya göre ilerle),
- $r_n \in F$ (accept state'te bitir).
$M$ recognizes $A$, eğer $A = \{w \mid M \text{ accepts } w\}$. Bu $A$'ya language of $M$ denir: $L(M) = A$.
A language is called a regular language if some finite automaton recognizes it.
Yani "$L$ regular" demenin yolu bir DFA kurup göstermek. Vizenin P1 sorusu tam olarak budur.
- $M_1$: $L(M_1) = \{w \mid w$ contains at least one 1 and an even number of 0s follow the last 1$\}$.
0100için $r_0, \dots, r_4 = q_1, q_1, q_2, q_3, q_2$. - $M_2$ (Ex 1.7): $Q = \{q_1, q_2\}$, start $q_1$, $F = \{q_2\}$, $\delta(q, 0) = q_1$ ve $\delta(q, 1) = q_2$ (hangi $q$'da olursan ol). Makine sadece "son okunan symbol neydi" bilgisini tutar.
1101: $q_1, q_2, q_2, q_1, q_2$, accept.110: $q_1$'de biter, reject. $L(M_2) = \{w \mid w \text{ ends in a } 1\}$. - $M_3$ (Ex 1.9): $M_2$'nin aynısı, tek fark $F = \{q_1\}$. Start state accept olduğu için $\varepsilon$ kabul edilir. $L(M_3) = \{w \mid w \text{ is the empty string } \varepsilon \text{ or ends in a } 0\}$.
- $M_4$ (Ex 1.11), $\Sigma = \{a, b\}$: ilk symbol makineyi sola ($q$'lar) ya da sağa ($r$'ler) gönderir ve $s$'ye geri dönüş yok. Sol tarafta a ile bitince, sağ tarafta b ile bitince accept. Language: aynı symbol ile başlayıp biten string'ler (
a,b,aa,bb,babkabul;ab,ba,bbbared).
- $M_5$ (Ex 1.13), $\Sigma = \{\langle\text{RESET}\rangle, 0, 1, 2\}$: okunan sayıların toplamını mod 3 tutar, $\langle\text{RESET}\rangle$ sayacı sıfırlar; toplam 3'ün katıysa accept. $w = 1\,0\,\langle\text{RESET}\rangle\,2\,2\,\langle\text{RESET}\rangle\,0\,1\,2$ için state dizisi $q_0, q_1, q_1, q_0, q_2, q_1, q_0, q_0, q_1, q_0$: üç şart da sağlanıyor, accept (Ex 1.17).
- $B_i$ (Ex 1.15): aynı fikir her $i \ge 1$ için. Diagram çizilemez çünkü $i$ bir parametre; makine formal olarak verilir: $B_i = (Q_i, \Sigma, \delta_i, q_0, \{q_0\})$, $Q_i = \{q_0, \dots, q_{i-1}\}$, $\delta_i(q_j, 0) = q_j$, $\delta_i(q_j, 1) = q_{(j+1) \bmod i}$, $\delta_i(q_j, 2) = q_{(j+2) \bmod i}$, $\delta_i(q_j, \langle\text{RESET}\rangle) = q_0$. Mod $k$ sayma kalıbı bir sonraki dersin ilk konusu.
- Accept string'ler için, recognize language'lar için kullanılır. Bir makine birçok string'i accept eder ama tam olarak bir language'ı recognize eder.
- $L(M)$, makinenin kabul ettiği string'lerin tamamı. "
1101'i kabul ediyor" demek $L(M)$'yi bulmak değildir; reddettiklerini de kontrol et. - $\varepsilon \in L(M) \iff q_0 \in F$. Language $\varepsilon$ içeriyorsa start state accept olmak zorunda; içermiyorsa olmamalı.
$M_2$: start $q_1$, $F = \{q_2\}$, 0 her zaman $q_1$'e, 1 her zaman $q_2$'ye götürüyor. $L(M_2)$ nedir?
$M_1$ ve $w = 10$ için formal tanımdaki $r_0, r_1, r_2$ dizisi hangisi, ve hangi şart bozuluyor?
Tasarım yöntemi: "neyi hatırlamam lazım?"
Sipser'in önerisi: kendini makinenin yerine koy. String'in symbol'leri sana birer birer geliyor ve string'in ne zaman biteceğini bilmiyorsun. Bu yüzden her symbol'den sonra "şu ana kadar gördüğüm string language'da mı?" sorusuna cevabın hazır olmalı.
Bütün string'i aklında tutamazsın: input buradan Ay'a kadar uzun olabilir ve elinde sadece tek bir kağıt var. Neyse ki çoğu language için her şeyi hatırlamak gerekmez, sadece kritik bilgiyi tutarsın. Derste sorulan soru da buydu: "Bir string'i compute ederken kaç farklı state'e ihtiyacım olabilir?"
- Hatırlanacak bilgiyi sonlu bir olasılık listesi olarak yaz. Her olasılık bir state.
- Transition'lar: her olasılıktan, her symbol okununca hangi olasılığa geçiliyor?
- Start state: hiç symbol okunmamışken ($\varepsilon$) geçerli olan olasılık.
- Accept state'ler: string orada bitseydi kabul etmek istediğin olasılıklar.
State'lere kaydettikleri bilgiye göre ad ver ("tek sayıda 1 gördüm", "son symbol 0"), "ikinci daire" gibi değil. Diagram yanlış olsa bile bu adlar kısmi puan getirir.
Hatırlanacak tek şey: şu ana kadar görülen 1'lerin sayısı tek mi, çift mi. İki olasılık, iki state: $q_{even}$ ve $q_{odd}$. 1 okununca state değişir, 0 okununca aynı kalır. Start $q_{even}$, çünkü $\varepsilon$'da sıfır tane 1 var ve 0 çift. Accept $q_{odd}$.
001'i substring olarak içeren string'ler (Sipser Ex 1.21)
Makine olarak 1'leri atlarsın. Bir 0 gelince aranan kalıbın ilk symbol'ünü görmüş olabilirsin. Ardından 1 gelirse 0 sayısı yetmedi, başa dönersin. 0 gelirse kalıbın iki symbol'ünü görmüşsündür; artık 1 gelene kadar beklersin. Dört olasılık:
- $q$: kalıbın hiçbir parçasını yeni görmedim,
- $q_0$: yeni bir 0 gördüm,
- $q_{00}$: yeni
00gördüm, - $q_{001}$: kalıbın tamamını gördüm.
$q_{001}$'e bir kez gelince oradan çıkılmaz: string'in geri kalanı ne olursa olsun kalıp görülmüştür. 0010, 1001, 001, 11111110011111 kabul; 11, 0000 red.
Tahtadaki language: $L = \{1, 100, 10000, \dots, 01, 0100, \dots\}$, yani en az bir 1 var ve son 1'den sonra çift sayıda 0 geliyor ($M_1$'in language'ı). Tahtada state'ler, tuttukları bilgiyle adlandırılarak çizildi:
- $q_0$: no 1s seen yet (0 gelince yerinde kalır),
- $q_1$: 1 seen but no following zeros yet (1 gelince yerinde kalır),
- $q_2$: son 1'den sonra tek sayıda 0,
- $q_3$: son 1'den sonra çift sayıda (en az iki) 0.
Tahtadaki örnek string 0010100000100: son 1'den sonra iki 0 var, makine $q_3$'te biter, accept. $q_1$ ve $q_3$'ün altına kırmızı nokta konmuştu: ikisi de accept ve ikisinin okları aynı yere gidiyor (1 ile $q_1$'e, 0 ile $q_2$'ye). Aynı davranan iki state birleştirilebilir. Birleştirince Sipser'in üç state'li $M_1$'i çıkar. Derste bu işi sistematik yapan DFA minimization algoritmasının adı geçti; bu ders için "aynı davranan state'ler birleşir" fikri yeterli.
"Σ = {0,1}. 'Çift sayıda 0 içeren' string'leri tanıyan DFA tasarla. State'ler ne 'hatırlıyor'? Tablo + 5-tuple yaz."
İpucu 1
Tarifin 1. adımı: okurken neyi bilmen gerekiyor? 0'ların tam sayısı mı, yoksa daha azı mı yeter?
İpucu 2
Start state'i $\varepsilon$ belirler: $\varepsilon$'da kaç tane 0 var ve bu sayı çift mi?
Çözümü göster
Tutulacak bilgi: şu ana kadar görülen 0'ların sayısı tek mi, çift mi. İki state yeter.
- $q_{even}$: çift sayıda 0 gördüm. Start, çünkü $\varepsilon$'da sıfır tane 0 var. Accept.
- $q_{odd}$: tek sayıda 0 gördüm.
| $\delta$ | 0 | 1 |
|---|---|---|
| $q_{even}$ | $q_{odd}$ | $q_{even}$ |
| $q_{odd}$ | $q_{even}$ | $q_{odd}$ |
5-tuple: $(\{q_{even}, q_{odd}\}, \{0,1\}, \delta, q_{even}, \{q_{even}\})$. 1 okumak state'i değiştirmez çünkü 1'ler sayılmıyor. $\varepsilon$ kabul edilir.
start: even accept: even even 0 -> odd even 1 -> even odd 0 -> even odd 1 -> odd
Bu metni aşağıdaki checker'a yapıştırıp "even number of 0s" hedefiyle kontrol edebilirsin.
Checker: DFA'n gerçekten bu language'ı mı tanıyor?
Hedef bir language seç ve DFA'nı kutuya yaz. Sayfa, length'i 8'e kadar olan bütün string'leri (511 tane) hem senin DFA'nda çalıştırıyor hem de hedef language'ın tanımıyla karşılaştırıyor. Bir fark bulursa en kısa karşı örneği gösteriyor. Eksik okları da işaretliyor ve tek tıkla bir dead state'e yönlendirebiliyor.
Önce tahmin et: "odd number of 1s" için iki state yeter mi? "contains 001" için en az kaç state gerekir? Önce kâğıda çiz, sonra yaz ve kontrol et.
"Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.
b. {w | w contains at least three 1s}
c. {w | w contains the substring 0101 (i.e., w = x0101y for some x and y)}
f. {w | w doesn't contain the substring 110}
i. {w | every odd position of w is a 1}"
Alıştırmanın bu bölüme uyan kısımları. (a), (d), (g), (h), (k), (m), (n) Bölüm 9'da. (e) ve (j) hemen aşağıda: iki bilgiyi birlikte tutuyorlar. (l) iki koşulu "or" ile bağladığı için sonraki dersin product construction konusunda.
İpucu 1
(b) 1'leri say ama 3'te dur: "3 ya da daha fazla" tek bir olasılık. (c) $E_2$ gibi: kalıbın ne kadarını yeni gördün? (f) "içermeyen" = "içeren"in tersi; önce 110'u arayan DFA'yı kur.
İpucu 2
(c)'de en zor adım, kalıp yarıda bozulunca nereye döneceğin: 010 gördükten sonra 0 gelirse elinde hâlâ yeni bir 0 var. (i)'de pozisyonları 1'den say: 1., 3., 5. symbol'ler 1 olmalı; çift pozisyonlar serbest. $\varepsilon$ language'da mı?
Çözümü göster
(b) $c_j$ = "şu ana kadar $j$ tane 1 gördüm", $c_3$ = "en az 3". 0 hiçbir şeyi değiştirmez.
start: c0 accept: c3 c0 0 -> c0 c0 1 -> c1 c1 0 -> c1 c1 1 -> c2 c2 0 -> c2 c2 1 -> c3 c3 0,1 -> c3
(c) State adı, kalıbın en uzun "yeni görülmüş" başı: $p$ (hiçbiri), $p_0$, $p_{01}$, $p_{010}$, $p_{0101}$ (bulundu, çıkış yok). 010'dan sonra 0 gelince son 0 yeni bir başlangıçtır, $p_0$'a dönülür; 01'den sonra 1 gelince elde kalıbın başı kalmaz, $p$'ye dönülür.
start: p accept: p0101 p 0 -> p0 p 1 -> p p0 0 -> p0 p0 1 -> p01 p01 0 -> p010 p01 1 -> p p010 0 -> p0 p010 1 -> p0101 p0101 0,1 -> p0101
(f) 110'u arayan DFA'yı kur ($t$, $t_1$, $t_{11}$, $t_{110}$), sonra accept ve non-accept state'lerin yerini değiştir (Bölüm 10). $t_{110}$ bir dead state olur.
start: t accept: t, t1, t11 t 0 -> t t 1 -> t1 t1 0 -> t t1 1 -> t11 t11 1 -> t11 t11 0 -> t110 t110 0,1 -> t110
(i) Tutulacak bilgi: sıradaki symbol tek pozisyonda mı, çift pozisyonda mı? $o$ = "sıradaki pozisyon tek", $e$ = "sıradaki pozisyon çift", $d$ = dead. Tek pozisyonda 0 görülürse string kurtulamaz. $\varepsilon$'da kontrol edilecek pozisyon yok, kabul.
start: o accept: o, e o 1 -> e o 0 -> d e 0,1 -> o d 0,1 -> d
"Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.
e. {w | w starts with 0 and has odd length, or starts with 1 and has even length}
j. {w | w contains at least two 0s and at most one 1}"
Bu iki şıkta tarifin 1. adımı iki parçalı bir bilgi veriyor. State'ler o iki parçanın bütün kombinasyonları.
İpucu 1
(e) İlk symbol'ü bir kez görünce unutmaman gerekir; sonra sadece length'in tek mi çift mi olduğunu tutarsın. (j) 0'ları "0, 1, en az 2" diye, 1'leri "0, 1" diye say. İkinci 1 gelince string kurtulamaz.
İpucu 2
(e) için $\varepsilon$ ile başla: ilk symbol yok, start reject. (j)'de kaç kombinasyon var? $3 \cdot 2 = 6$, buna dead state eklenir. Accept olanlar "en az iki 0" satırındakiler.
Çözümü göster
(e) State adı = (ilk symbol, şu ana kadarki length tek mi çift mi). $o_0$: 0 ile başladı, length tek (accept). $e_0$: 0 ile başladı, length çift. $o_1$: 1 ile başladı, length tek. $e_1$: 1 ile başladı, length çift (accept). İlk symbol'den sonra her symbol length'in paritesini çevirir.
start: s accept: o0, e1 s 0 -> o0 s 1 -> o1 o0 0,1 -> e0 e0 0,1 -> o0 o1 0,1 -> e1 e1 0,1 -> o1
Daha kısası da var: $o_0$ ile $e_1$ ikisi de accept ve ikisi de her symbol'de bir reject state'e geçiyor; $e_0$ ile $o_1$ ikisi de reject ve her symbol'de bir accept state'e geçiyor. Aynı davranan state'leri birleştirince 3 state kalır: $s$, $a$ (accept), $r$. $s \xrightarrow{0} a$, $s \xrightarrow{1} r$, $a \xrightarrow{0,1} r$, $r \xrightarrow{0,1} a$. Sınavda iki çözüm de doğru.
start: s accept: a s 0 -> a s 1 -> r a 0,1 -> r r 0,1 -> a
(j) State $q_{ij}$: $i$ = görülen 0 sayısı (2'de durur, "en az 2" demek), $j$ = görülen 1 sayısı. 0 gelince $i$ artar (2'de kalır), 1 gelince $j$ 0'dan 1'e geçer; $j = 1$ iken 1 gelirse dead state $d$. Accept: $q_{20}$ ve $q_{21}$.
start: q00 accept: q20, q21 q00 0 -> q10 q10 0 -> q20 q20 0 -> q20 q01 0 -> q11 q11 0 -> q21 q21 0 -> q21 q00 1 -> q01 q10 1 -> q11 q20 1 -> q21 q01 1 -> d q11 1 -> d q21 1 -> d d 0,1 -> d
7 state, her state'ten her symbol için tam bir ok. Bu "bilgileri bir tablonun satır ve sütunları gibi düzenle" fikri, sonraki dersteki product construction'ın ta kendisi.
- "Contains" ile "ends with" farklı. "Contains" için accept state her symbol'de kendine dönen bir tuzak olmalı. Aksi hâlde kalıbı gördükten sonra gelen symbol makineyi accept state'ten çıkarır ve "ends with" kurmuş olursun.
- Kalıp yarıda bozulunca her zaman başa dönülmez.
001ararken $q_{00}$'da 0 gelirse hâlâ son iki symbol00: yerinde kalırsın. - Bütün string'i hatırlamaya çalışma. "Son $k$ symbol", "sayı mod $k$", "kalıbın ne kadarı görüldü" gibi sonlu bir bilgi ara.
$E_2$ (001 içeren string'ler) $q_{00}$'dayken 0 okursa nereye gider?
"Tek sayıda 1" DFA'sında start state neden $q_{even}$?
Tahtadan: binary'de çift sayılar, reverse ve leading zeros
$\Sigma = \{0,1\}$, $E = \{0, 10, 100, 110, 1000, 1010, \dots\}$. Bir binary sayının çift olup olmadığına son bit (least significant bit) karar verir: 0 ile biten sayı çifttir. DFA string'i soldan sağa okuduğu için karar veren bit en son okunan bit. Makinenin hatırlaması gereken tek şey "son okunan bit neydi".
Tahtadaki ilk çizimde üç state vardı: start, "son bit 1" ve "son bit 0" (accept). Tahtada iki string izlendi: 11101 $\notin L$ (1 ile bitiyor) ve 1000 (0 ile bitiyor, kabul).
Sonra "too many states" denip iki state'e inildi: "odd until now" (start) ve "even until now" (accept). Start state ile "son bit 1" state'i aynı davranıyor: ikisi de reject ve okları aynı yere gidiyor. Bu yüzden birleşiyorlar. Start accept olmadığı için $\varepsilon \notin L$: $\varepsilon$ bir sayı değil.
İki state'li DFA 00, 010, 0010 gibi string'leri de kabul eder. Bunlar başında fazladan 0 olan (leading zeros) çift sayılar: 0010 = 2. $E$'nin listesinde böyle string yok, ama DFA onları kabul ediyor. Language'ı sen tanımlarsın: leading zeros'a izin veriyorsan bu DFA doğru; vermiyorsan ("sayı 0 ile başlamaz, tek istisna 0") başı kontrol eden ek state'ler ve bir dead state gerekir. 26 Ekim'deki "divisible by 5" çözümünde hoca leading zeros'u kabul etti.
Sonra aynı sayılar ters yazıldı: $E^R = \{0, 01, 001, 011, 0001, \dots\}$, "evens in reverse order". Artık karar veren bit ilk okunan bit. DFA daha da kolaylaşır: ilk symbol 0 ise accept'e gidip orada kal, 1 ise dead state'e gidip orada kal. Tahtada bu language'a "strings that start with zero" denildi; leading zeros'a izin verince $Z = \{0, 00, 000, \dots, 01, 010, 001, \dots, 01001, \dots\}$.
Notuna "reverse şekilde daha kolay olur diye düşünüp aslında yeni bir language oluşturduk" yazmışsın, doğru: $E^R$ başka bir language. DFA yine soldan sağa okur; tahtada 0011001 string'inin yanındaki sola bakan ok, ters yazılmış sayının hangi yönden okunduğunu gösteriyor.
Leading zeros olmadan ("without leading zeros!"): orijinal sayının başında fazladan 0 yoksa ters çevrilmiş string 0'la bitemez, tek istisna sayının kendisi 0 ise. O zaman language $\{0\} \cup \{0w1 \mid w \in \Sigma^*\}$ olur. Tahtadaki turuncu DFA: start'tan 0 ile accept'e; accept'te 1 gelirse orada kal, 0 gelirse "son symbol 0" state'ine geç; oradan 1 gelince accept'e dön. Start'tan 1 gelirse dead state.
"Binary'de çift sayılar (E) için DFA. Bir binary sayının çift olup olmadığına hangi bit karar verir? 0010 language'da mı olmalı (leading zeros)? ε ne olmalı?"
İpucu 1
Ondalık sistemde bir sayının çift olduğunu son basamağa bakarak anlarsın. Binary'de de öyle. DFA o basamağı ne zaman görür?
İpucu 2
0010 ve $\varepsilon$ için cevap language'ın tanımına bağlı. Önce bir tanım seç, sonra DFA'yı o tanıma uydur. $\varepsilon$ bir sayı mı?
Çözümü göster
Karar veren bit son bit (LSB): 0 ile biten binary sayı çifttir. DFA'nın "son okunan bit 0 mıydı?" bilgisini tutması yeter.
Leading zeros serbestse (derste ve 26 Ekim'de seçilen yol), 0010 = 2 language'dadır. $\varepsilon$ sayı değil, reddedilir; bu yüzden start state accept değil.
start: odd accept: even # odd = "odd until now" (start), even = "even until now" odd 0 -> even odd 1 -> odd even 0 -> even even 1 -> odd
Leading zeros yasaksa language $\{0\} \cup \{1w0 \mid w \in \Sigma^*\}$ olur ve 0010 reddedilir. Başı kontrol etmek için üç state daha gerekir: ayrı bir start state (s), yalnızca tek başına 0 için bir accept state (zero) ve 0'dan sonra bir symbol daha gelirse gidilen dead state (dead).
start: s accept: zero, even s 0 -> zero s 1 -> odd zero 0,1 -> dead odd 0 -> even odd 1 -> odd even 0 -> even even 1 -> odd dead 0,1 -> dead
Sınavda böyle bir belirsizlik varsa seçtiğin tanımı bir cümleyle yaz ("leading zeros kabul ediliyor") ve DFA'yı ona göre kur.
- "Reverse" DFA'nın string'i sağdan sola okuması değil. DFA her zaman soldan sağa okur. $E^R$ yeni bir language ve onun için yeni bir DFA kuruluyor.
0çift bir sayı ve $E$'de. Tek başına0'ı kabul etmeyi unutma.- Regular language'lar reverse işlemine göre de kapalı: $A$ regular ise $A^R$ de regular (Sipser Problem 1.31). İspatı NFA gerektirir; şimdilik sadece sonucu bil.
Tahtadaki iki state'li DFA (odd until now / even until now) 0010'u ne yapar?
$E^R$ DFA'sında (leading zeros serbest) start state'ten 1 okunursa ne olmalı?
Tahtadan: ends with 01, starts with 10 ve ikisi birden
Hatırlanacak bilgi: son symbol'ler kalıbın ne kadarını oluşturuyor? $s$: işe yarar bir şey yok, $a$: son symbol 0, $b$: son iki symbol 01 (accept). $b$'den 0 gelirse yeni bir 01'in başı oluşur ($a$'ya), 1 gelirse 11 olur ve işe yarar bir şey kalmaz ($s$'ye).
İlk iki symbol 1 ve 0 olmalı. Olursa accept state'e gidip orada kalırsın, gerisi önemsiz. Olmazsa string kurtulamaz. Tahtada bu durum için bir sink state çizildi: accept olmayan ve her symbol'de kendine dönen bir state. Buna dead state ya da trap state de denir.
Sink state'i atarsan $\delta(s, 0)$ ve $\delta(x, 1)$ tanımsız kalır ve makine artık DFA değildir.
Tahtadaki fikir: $L_2$'nin baş kısmını al, ardından $L_1$'in DFA'sını bağla. Tahtada 10'dan sonraki state $L_1$'in start state'ine yapıştırıldı ve yanına "101 $\notin L$" yazıldı.
Bu yapıştırılmış makine gerçekten 101'i reddeder: 10'dan sonra $t$'ye gelir, 1 ile $t$'de kalır. Ama tanımı harfiyen okursan 101 hem 10 ile başlıyor hem 01 ile bitiyor: ortadaki 0 iki kalıpta da kullanılıyor.
Not: Tahtadaki "101 $\notin L$" notu, yapıştırılmış DFA'nın davranışına uyuyor ama $L_3$'ün tanımına uymuyor. "starts with 10 and ends with 01" tanımına göre 101 $\in L_3$. Sınavda tanımı harfiyen uygula; kalıplar üst üste binebiliyorsa (burada ortak 0) bunu hesaba kat.
"$L_3 = \{w \mid w$ starts with 10 and ends with 01$\}$" için bir DFA kur.
İpucu 1
Önce baş kısmı halleden üç state: start, "1 gördüm", ve bir sink state. 10 okunduktan sonra makine hangi bilgiye sahip? Son okunan symbol 0.
İpucu 2
$L_1$'in DFA'sında "son symbol 0" bilgisini tutan state hangisi? 10'dan sonra oraya gidersen ortadaki 0, 01'in 0'ı olarak da sayılır.
Çözümü göster
Baş: $s \xrightarrow{1} x \xrightarrow{0} y$; $s$'den 0 ve $x$'ten 1 sink state'e. 10'dan sonra $L_1$'in üç state'i devreye girer: $w$ (işe yarar bir şey yok), $y$ (son symbol 0), $z$ (son iki symbol 01, accept). 10'dan sonra son symbol 0 olduğu için doğrudan $y$'ye gidilir.
start: s accept: z s 1 -> x s 0 -> sink x 0 -> y x 1 -> sink y 0 -> y y 1 -> z z 0 -> y z 1 -> w w 0 -> y w 1 -> w sink 0,1 -> sink
Kontrol: 101: $s, x, y, z$, accept. 1001: $s, x, y, y, z$, accept. 1011: $\dots, z, w$, reject. 01: sink, reject. Toplam 6 state; length'i 10'a kadar bütün string'lerde tanımla aynı cevabı veriyor.
"P1 [20 points] Construct a DFA for the languages
(a) Binary strings that contain neither 00 nor 11."
Sorunun (b) şıkkı (1'ler 2'li ya da 4'lü gruplarda) bir sonraki derste.
İpucu 1
Bir string'in 00 ya da 11 içerip içermediğini anlamak için okurken neyi bilmen yeter? Bir önceki symbol.
İpucu 2
Aynı symbol iki kez üst üste gelirse string kurtulamaz: dead state. $\varepsilon$, 0, 1 language'da mı? Start state ile "son symbol 0" state'i neden birleşemez?
Çözümü göster
Language, symbol'leri sırayla değişen string'ler: $\varepsilon$, 0, 1, 01, 10, 010, 101, … Tutulacak bilgi son symbol. State'ler:
- $s$: henüz symbol yok (start, accept, çünkü $\varepsilon$ ne
00ne11içerir), - $a_0$: son symbol 0 (accept),
- $a_1$: son symbol 1 (accept),
- $d$:
00ya da11görüldü (dead, reject).
start: s accept: s, a0, a1 s 0 -> a0 s 1 -> a1 a0 0 -> d a0 1 -> a1 a1 0 -> a0 a1 1 -> d d 0,1 -> d
$s$ ile $a_0$ birleşemez: $s$'den 0 okununca accept'te kalınır (0 language'da), $a_0$'dan 0 okununca dead state'e gidilir (00 değil). Aynı nedenle $s$ ile $a_1$ de ayrı. 4 state ve her state'ten her symbol için tam bir ok: gerçekten bir DFA.
Çözüm length'i 10'a kadar bütün string'lerde language'ın tanımıyla karşılaştırıldı. Bu kâğıdın repoda cevap anahtarı yok.
Simulator ve checker birlikte
Hazır makinelerden "Tahtadaki yapıştırılmış $L_3$"ü seç, hedef olarak $L_3$'ü bırak ve kontrol et: checker ilk karşı örnek olarak 101'i bulmalı. Sonra kendi düzeltmeni yaz. "Sink'siz $L_2$" makinesi eksik okları göstermek için var: eksikleri tek tıkla dead state'e gönder.
Önce tahmin et: "Sink'siz $L_2$" makinesi 0'ı kabul eder mi, reddeder mi, yoksa takılır mı? Takılırsa bu bir DFA mı?
"Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.
a. {w | w begins with a 1 and ends with a 0}
d. {w | w has length at least 3 and its third symbol is a 0}
g. {w | the length of w is at most 5}
h. {w | w is any string except 11 and 111}
k. {ε, 0}
m. The empty set
n. All strings except the empty string"
Alıştırmanın bu bölüme uyan kısımları: baş, son, length ve sonlu language'lar. Hepsinde dead state ya da "artık her şey kabul" state'i gerekiyor.
İpucu 1
(a) baş kısmı $L_2$ gibi, son kısmı $M_2$/$M_3$ gibi. (d) ilk iki symbol önemsiz, üçüncü karar verir. (g) length'i 5'e kadar say, 6. symbol dead state'e götürür.
İpucu 2
(h) neredeyse her şey kabul: sadece 11 ve 111'de bitmek reject olmalı. (k), (m), (n)'de önce $\varepsilon$'a karar ver: start state accept mi? (m) için kaç accept state gerekir?
Çözümü göster
(a) $s$'den 0 ile dead state; 1 ile "1 ile başladı" bölgesine. Orada son symbol'ü tut: $b_1$ (son 1), $b_0$ (son 0, accept).
start: s accept: b0 s 1 -> b1 s 0 -> d b1 0 -> b0 b1 1 -> b1 b0 0 -> b0 b0 1 -> b1 d 0,1 -> d
(d) İlk iki symbol'ü say, üçüncüye bak.
start: p0 accept: ok p0 0,1 -> p1 p1 0,1 -> p2 p2 0 -> ok p2 1 -> d ok 0,1 -> ok d 0,1 -> d
(g) $l_j$ = "length $j$", $j \le 5$ hepsi accept; $l_6$ dead.
start: l0 accept: l0, l1, l2, l3, l4, l5 l0 0,1 -> l1 l1 0,1 -> l2 l2 0,1 -> l3 l3 0,1 -> l4 l4 0,1 -> l5 l5 0,1 -> l6 l6 0,1 -> l6
(h) 1, 11, 111 yolunu takip et; bu yoldan herhangi bir sapma ya da 111'den sonraki bir symbol, "artık her şey kabul" state'i $x$'e götürür. Reject edilen sadece $h_{11}$ ve $h_{111}$.
start: h accept: h, h1, x h 1 -> h1 h 0 -> x h1 1 -> h11 h1 0 -> x h11 1 -> h111 h11 0 -> x h111 0,1 -> x x 0,1 -> x
(k) $\{\varepsilon, 0\}$: start accept, 0 ile ikinci bir accept state'e, başka her şey dead.
start: s accept: s, z s 0 -> z s 1 -> d z 0,1 -> d d 0,1 -> d
(m) Empty set: tek state, accept state yok ($F = \emptyset$, Bölüm 5).
start: q accept: q 0,1 -> q
(n) $\varepsilon$ hariç her şey: start reject, ilk symbol'den sonra accept'te kal.
start: s accept: a s 0,1 -> a a 0,1 -> a
Her birini yukarıdaki checker'a yapıştırıp aynı adlı hedefle kontrol edebilirsin.
$L_1$ (ends with 01) DFA'sında accept state $b$'deyken 0 okunursa nereye gidilir?
$L_2$ (starts with 10) DFA'sından sink state'i ve ona giden okları silersen ne olur?
Complement: $F$ yerine $Q - F$
Bir language class'ı (örneğin bütün regular language'lar) bir işleme göre closed ise, o class'tan language alıp işlemi uyguladığında sonuç yine aynı class'ta kalır. Tam sayılar toplamaya göre closed: iki tam sayının toplamı yine tam sayı. Bölmeye göre değil: $1/2$ tam sayı değil.
Neden işe yarar? Basit DFA'lardan karmaşık language'ları kurarsın. Bir language'ın regular olmadığını göstermek için de kullanılır. İlk örnek complement.
$M = (Q, \Sigma, \delta, q_0, F)$ bir DFA ve $L(M) = A$ ise $M' = (Q, \Sigma, \delta, q_0, Q - F)$, $\overline{A} = \Sigma^* - A$'yı tanır. Transition'lara dokunulmaz; sadece accept ve non-accept state'ler yer değiştirir.
Neden doğru: her string için $M$ ve $M'$ aynı state'te biter. $M$ o state'te kabul ediyorsa $M'$ reddeder, $M$ reddediyorsa $M'$ kabul eder.
Sonuç: regular language'lar complement'e göre closed. Union ve intersection (product construction) bir sonraki derste.
"M2'yi değiştirerek '1 ile bitmeyen' string'leri tanıyan DFA yap. Neyi değiştirdin? (İpucu: bu soru closure sorusuna bağlanıyor.)"
İpucu 1
Transition'lara dokunmana gerek var mı? Her string $M_2$'de hangi state'te bitiyorsa yeni makinede de orada bitecek. Değişmesi gereken sadece karar.
İpucu 2
$\varepsilon$ 1 ile bitiyor mu? Bitmiyorsa yeni makine onu kabul etmeli; o zaman start state ne olmalı?
Çözümü göster
Sadece accept ve non-accept state'lerin yeri değişir: $F = \{q_2\}$ yerine $F = \{q_1\}$. Yeni makine $(\{q_1, q_2\}, \{0,1\}, \delta, q_1, \{q_1\})$; $\delta$ aynı.
Artık 0 ile biten string'ler ve $\varepsilon$ kabul ediliyor. $\varepsilon$ da "1 ile bitmeyen" bir string, kabul edilmesi doğru. Çıkan makine tam olarak Sipser'in $M_3$'ü. Yaptığın şey yukarıdaki genel kuralın bir örneği: $F$ yerine $Q - F$.
- Önce DFA'yı tamamla, sonra çevir. Dead state'i çizmediğin bir makinede $F$'yi çevirirsen eksik okta takılan string'ler yine reddedilir. "Sink'siz $L_2$"yi çevirirsen
0reddedilir, ama0, "starts with 10"un complement'inde. - Complement'te $\varepsilon$'u unutma: $\varepsilon \notin A$ ise $\varepsilon \in \overline{A}$ ve yeni start state accept olur.
- Bu hile sadece DFA'da çalışır. NFA'da accept state'leri çevirmek complement vermez; nedeni NFA dersinde.
$M_2$'de $F = \{q_2\}$ yerine $F = \{q_1\}$ yaparsan makine hangi language'ı tanır?
$L_1$ (ends with 01) DFA'sında $F$ ile $Q - F$'yi değiştirdin. Hangisi yeni makinede kabul edilmez?
Chapter 0'dan: üç ispat tekniği
Vizenin kapsamı Chapter 0'ı da içeriyor. Sipser 0.4'te üç ispat türü var ve dönem boyunca hepsini kullanacaksın.
"Böyle bir nesne vardır" türü bir teoremi, nesneyi kurup göstererek ispatlamak. Sipser'in örneği: 2'den büyük her çift $n$ için $n$ node'lu 3-regular bir graph vardır (node'ları bir çembere diz, komşuları ve tam karşıdakini bağla). Bu derste yaptığın her DFA tasarımı bir proof by construction: "$L$ regular" iddiasını, $L$'yi tanıyan DFA'yı kurarak ispatlıyorsun.
İddianın yanlış olduğunu varsay ve bu varsayımdan açıkça yanlış bir sonuç (contradiction) çıkar. O zaman varsayım yanlış, iddia doğru. Sipser'in günlük hayattan örneği: Jill dışarıdan kupkuru geliyor; yağmur yağsaydı ıslak olurdu, o hâlde yağmur yağmıyor. Vizenin P3 ve P5 soruları bu kalıpla yazılır: "Assume $L$ is regular. …" ve sonunda contradiction.
Sonsuz bir kümenin (örneğin $\mathbb{N}$) her elemanının bir özelliği olduğunu göstermek için iki parça: basis ($P(1)$ doğru) ve induction step (her $i \ge 1$ için $P(i)$ doğruysa $P(i+1)$ de doğru). Step'te $P(i)$'nin doğru olduğu varsayımına induction hypothesis denir. Basis 1'den değil herhangi bir $b$'den de başlayabilir.
İddia: $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$, her $n \ge 1$ için.
İspatı göster
Basis ($n = 1$): sol taraf 1, sağ taraf $1 \cdot 2 / 2 = 1$. Eşit.
Induction hypothesis: bir $k \ge 1$ için $1 + \cdots + k = k(k+1)/2$ olsun.
Induction step: $1 + \cdots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = (k+1)\left(\dfrac{k}{2} + 1\right) = \dfrac{(k+1)(k+2)}{2}$. Bu, formülün $n = k+1$ için yazılmış hâli.
Basis ve step birlikte formülün her $n \ge 1$ için doğru olduğunu gösterir. ∎
İspatı göster
- Tersini varsay: $\sqrt 2$ rational, yani $\sqrt 2 = m/n$, $m$ ve $n$ tam sayı. Kesri sadeleştir: $m$ ile $n$'nin ikisi birden çift değil.
- İki tarafı $n$ ile çarp ve karesini al: $2n^2 = m^2$. Yani $m^2$ çift, o hâlde $m$ de çift (tek sayının karesi tektir). $m = 2k$ yaz.
- Yerine koy: $2n^2 = 4k^2$, yani $n^2 = 2k^2$. O hâlde $n$ de çift.
- $m$ ve $n$ ikisi de çift. Bu, kesri sadeleştirdiğimiz varsayımıyla çelişiyor. Demek ki $\sqrt 2$ irrational. ∎
- Contradiction ispatında varsayımı ilk cümlede açıkça yaz ("Assume …"). Hoca ispatlarda cümlelerin sırasını puanlıyor; sırası bozuk cümleler üstü çizilerek okunuyor.
- Induction'da step'i yazıp basis'i unutmak ispatı geçersiz kılar: domino taşlarının devrilmesi için ilkinin düşmesi gerekir.
"$L$ regular değildir" ispatı vizede "Assume $L$ is regular." diye başlar. Bu hangi ispat türü?
Induction step'te neyi göstermen gerekir?
Son kontrol
Konular karışık geliyor. Her soruda önce hangi tanımın gerektiğini seç.
$Q = \{p, r\}$, $\Sigma = \{0,1\}$ olan bir makinede $p$'den 1 okununca hem $p$'ye hem $r$'ye giden iki ok var. Bu makine için hangisi doğru?
Tek state'li bir DFA: state hem start hem accept, 0 ve 1 için okları kendine dönüyor. Language'ı nedir?
Bir DFA'nın $\varepsilon$'u kabul edip etmediğini nasıl anlarsın?
$\Sigma = \{0,1\}$. Length'i en fazla 2 olan kaç string var?
"Starts with 10 and ends with 01" language'ında hangisi yoktur?