3  Belirlenimli Sonlu Otomat

Belirlenimli Sonlu Otomat (BSO) ingilizcesi Deterministic finite automaton (DFA) işleyeceğimiz en basit makinedir.

Önce örnekler ile başlayacağız arkasından teorik bilgileri vereceğiz.

3.1 Senaryo: 10 TL’lik Soda Otomatı

Soda fiyatının 10 TL olduğu bir otomat düşünelim.

Kurallar

1. Otomat sadece 5 TL madeni para kabul eder.
2. Para üstü verme veya para iadesi özelliği yoktur.
3. Toplamda 10 TL’ye ulaşıldığında, otomat Soda Ver (kabul) durumuna geçilir.

Geçiş Tablosu

Mevcut Durum (Bakiye)	Girdi: 5 TL Atıldığında	Yeni Durum
\(\rightarrow q_0\) (0 TL)	\(q_5\)	Bakiye 5 TL olur
\(q_5\) (5 TL)	\(q_{soda}\)	Bakiye 10 TL olur (Soda verilir)
\(*q_{soda}\) (10 TL - Soda)	\(q_{soda}\)	Soda verildikten sonra makine kabul durumunda kalır

Durum Diyagramı

Adım Adım İşleyiş Örnekleri

Örnek 1: İki Tane 5 TL Atılması (Toplam 10 TL)

1. Otomat \(q_0\) durumunda başlar (Bakiye: 0 TL).
2. Birinci 5 TL atılır \(\rightarrow\) \(q_5\) durumuna geçilir (Bakiye: 5 TL).
3. İkinci 5 TL atılır \(\rightarrow\) \(q_{soda}\) durumuna geçilir (Bakiye: 10 TL).
4. Sonuç: \(q_{soda}\) kabul durumuna ulaşıldı \(\rightarrow\) KABUL (Soda düşer!).

Örnek 2: Sadece Bir Tane 5 TL Atılması (Toplam 5 TL)

1. Otomat \(q_0\) durumunda başlar (Bakiye: 0 TL).
2. Birinci 5 TL atılır \(\rightarrow\) \(q_5\) durumuna geçilir (Bakiye: 5 TL).
3. Başka para atılmadan beklenir.
4. Sonuç: Otomat \(q_5\) durumunda kalır. \(q_5\) kabul durumu olmadığı için işlem REDDEDİLİR (Soda verilmez).

Önemli Noktalar

1. Belirlilik (Deterministic): Hangi durumda olursanız olun, 5 TL attığınızda bir sonraki durumun ne olacağı %100 bellidir.

2. Sonlu Hafıza (Finite Memory): Otomat sonsuz veri saklamaz; sadece 3 farklı durumu (state) (\(0\text{ TL}\), \(5\text{ TL}\) ve \(10\text{ TL}\)) vardır.

Resmi tanım

Otomatları tanımlarken aşağıdaki bilgileri vererek resmi tanımlarını yaparız.

1. \(Q\): Sonlu durumlar kümesi.

2. \(\Sigma\): Alfabe:

3. \(\delta\): Geçiş fonksiyonu (\(Q \times \Sigma \rightarrow Q\))

4. \(q_0\) Başlangıç durumu: (\(Start\ State\))

5. \(F\): Kabul durumları kümesi (\(Accept\ States\)).

Resmi tanım özellikleri

1. \(Q\) (Sonlu Durumlar Kümesi)

Makinenin sahip olabileceği tüm durumlar:

\[Q = \{q_0, q_5, q_{soda}\}\]

• \(q_0\): Bakiye 0 TL
• \(q_5\): Bakiye 5 TL
• \(q_{soda}\): Bakiye 10 TL (Soda Verildi)

2. \(\Sigma\) (Girdi Alfabesi)

Otomata atılabilecek kabul edilen semboller/girdiler:

\[\Sigma = \{5\}\]

3. \(\delta\) (Geçiş Fonksiyonu: \(Q \times \Sigma \rightarrow Q\))

Geçişler formal küme eşleşmesi veya liste olarak şu şekilde tanımlanır:

\[\begin{aligned} \delta(q_0, 5) &= q_5 \\ \delta(q_5, 5) &= q_{soda} \\ \delta(q_{soda}, 5) &= q_{soda} \end{aligned}\]

4. \(q_0\) (Başlangıç Durumu)

Makinenin sıfır bakiye ile başladığı durum:

\[q_0 = q_0\]

5. \(F\) (Kabul Durumları Kümesi)

Sodanın verilmesini (başarılı tamamlanmayı) temsil eden durumlar kümesi:

\[F = \{q_{soda}\}\]

Ek sorular

• Bu makine bu hali ile kullanışlı değildir. Bu makineye iptal ve soda_ver girdilerini ekleyin. Bu girdiler için gerekirse yeni durumlar ekleyin.

Çözüm 4.1

3.2 Senaryo: Çift sayıda ‘0’ içeren girdileri kabul eden otomat

Bir bilgisayar, bir lamba anahtarına \(N\) kez basıldıktan sonra lambanın AÇIK mı yoksa KAPALI mı olduğunu nasıl anlar?”

• Hafızasız durum makineleri (memoryless state machines), sadece var olan durum hakkında bilgi sahibidirler.

Kurallar

1. İçinde çift sayıda 0 bulunan dizgileri (hiç 0 bulunmaması da dahil) kabul edilir.
2. Tek sayıda 0 içeren dizgileri red edilir.

• Alfabe (\(\Sigma\)): \(\{0, 1\}\)
• Görev:
• Durumlar (\(Q\)): \(\{q_{çift}, q_{tek}\}\)
• \(q_{çift}\): Şu ana kadar görülen 0 sayısı çift. (Başlangıç ve Kabul Durumu)
• \(q_{tek}\): Şu ana kadar görülen 0 sayısı tek.

Resmi Tanım

BSO’lar 5’li demet \((Q, \Sigma, \delta, q_0, F)\) olarak tanımlanır:

1. \(Q = \{q_{çift}, q_{tek}\}\) — Durumlar kümesi.

2. \(\Sigma = \{0, 1\}\) — Girdi alfabesi.

3. \(\delta\): Geçiş fonksiyonu (\(Q \times \Sigma \rightarrow Q\))

4. \(q_0 = q_{çift}\) — Başlangıç durumu.

5. \(F = \{q_{çift}\}\) — Kabul (final) durumları kümesi.

Geçiş Tablosu

Durum	Girdi: 0	Girdi: 1
\(\rightarrow *q_{çift}\)	\(q_{tek}\)	\(q_{çift}\)
\(q_{tek}\)	\(q_{çift}\)	\(q_{tek}\)

Not: \(\rightarrow\) başlangıç durumunu, \(*\) ise kabul (bitiş) durumunu gösterir.

Durum Diyagramı

• 1 girdisi 0 sayısını etkilemediği için makine kendi bulunduğu durumda kalır (kendi üzerine döngü/self-loop).

• 0 girdisi geldiğinde ise tek/çift durumu değişir.

• Örnek 1: 1010 dizgisi (Kabul Edilir)

\[q_{çift} \xrightarrow{\mathbf{1}} q_{çift} \xrightarrow{\mathbf{0}} q_{tek} \xrightarrow{\mathbf{1}} q_{tek} \xrightarrow{\mathbf{0}} q_{çift} \quad (q_{çift} \in F \rightarrow \textbf{Kabul})\]

• Örnek 2: 101 dizgisi (Reddedilir)

\[q_{çift} \xrightarrow{\mathbf{1}} q_{çift} \xrightarrow{\mathbf{0}} q_{tek} \xrightarrow{\mathbf{1}} q_{tek} \quad (q_{tek} \notin F \rightarrow \textbf{Red})\]

• Boş Dizgi (\(\epsilon\)): Okuma yapılmadan \(q_{çift}\) durumunda kalınır. İçinde 0 adet ‘0’ vardır (0 çift bir sayıdır), dolayısıyla \(\epsilon\) da kabul edilir.

Ekstra Soru

• “Bu BSO’yu, ‘01’ ile biten dizgileri kabul edecek şekilde nasıl değiştirirsiniz?”

Tip

Belirli (Deterministik) olma kuralı: Her durumdan, alfabedeki her sembol için tam olarak bir çıkış oku olmalıdır.

Tip

Düzenli diller (regular languages), sonlu otomatlar tarafından tanınabilen dillerdir.

3.3 BSO Sorular Alfabe 0,1

Aşağıdaki dilleri tanıyan DFA’ların durum diyagramlarını çizin. Alfabe \(\{0, 1\}\)’dir.

1. \(\{w \mid w \text{ '1' ile başlar ve '0' ile biter}\}\)

Çözüm 4.2

http://localhost:4200/content/dfa-soru-cozumleri.html#sec-sorular-dfa-1-basla-0-bit

2. \(\{w \mid w \text{ en az üç adet '1' içerir}\}\) ÇÖZÜLDÜ

3. \(\{w \mid w \text{ 0101 alt dizesini içerir. } \text{ Yani bir } x \text{ ve } y \text{ kelimesi için } w = x0101y\}\)

4. \(\{w \mid w \text{ uzunluğu en az 3'tür ve 3. sembolü '0'dır}\}\)
   ÇÖZÜLDÜ

5. \(\{w \mid w \text{ '0' ile başlar ve tek uzunluktadır}\}\)

6. \(\{w \mid w \text{ '0' ile başlar ve tek uzunluktadır, VEYA '1' ile başlar ve çift uzunluktadır}\}\)

7. \(\{w \mid w \text{, 110 alt dizesini içermez: } \}\)

8. \(\{w \mid w \text{ uzunluğu en fazla 5'tir}\}\)

9. \(\{w \mid w \text{ '11' ve '111' hariç herhangi bir dizedir}\}\)

10. \(\{w \mid w \text{ dizisinin her tek pozisyonu '1'dir}\}\) ÇÖZÜLDÜ.

11. \(\{w \mid w \text{ en az iki adet '0' ve en fazla bir adet '1' içerir}\}\)
    

12. \(\{\epsilon, 0\}\)

13. \(\{w \mid w \text{ çift sayıda '0' içerir VEYA tam olarak iki adet '1' içerir}\}\)

14. Boş küme (\(\emptyset\))

15. Boş dize (\(\epsilon\)) hariç tüm dizeler

16. \(\{w \mid w \text{, '01' ile biter}\}\) ÇÖZÜLDÜ.

17. \(\{w \mid w \text{, '111' ile biter}\}\) ÇÖZÜLDÜ.

18. Uzunluğu çift olan dizeler

19. Uzunluğu tek olan dizeler

20. 0 ile başlayan dizeler

21. \(\{w \mid w \text{, '0' ile başladığında 0 biter ve 1 ile başladığında 1 ile biter.}\}\)

3.4 BSO terimler ve tekrar

1. \(Q\): Sonlu durumlar kümesi. BSO’nun bulunabileceği durumların listesi

2. \(\Sigma\) Alfabe, sembol kümesi örnekler:

• \(\Sigma = {0,1}\)
• \(\Sigma = {a,b,c,d}\)

3. Dizgi (string), alfabe üzerindeki sembol listesi, örnekler:

• 010001
• abdddc

4. \(\epsilon\) (epsilon): 0 uzunluktaki dizgi

5. Dil (language), dizgi kümesidir, örnekler:

• \(A=\emptyset\) (boş küme)
• \(B={0,1,11,000111}\)
• \(C={a,b,c,aabbccdaaa}\)

6. Geçiş tablosu: geçiş fonksiyonu bilgilerinin tablo olarak verilmesi

7. Geçiş diyagramı: geçiş fonksiyonunun şekil olarak verilmesi. Daha anlaşılır olduğu için tercih edilir.

8. \(\delta\): Geçiş fonksiyonu (\(Q \times \Sigma \rightarrow Q\))

Matematiksel resmi tanım. Tablo veya diyagram olarak verilebileceği gibi doğal dil olarak ta tanımlanabilir.

9. \[q_0 \in Q \] Başlangıç durumu(Start State)

10. \(F \subseteq Q\): Kabul durumları kümesi (Accept States). Son durumlar (final state)’te kullanılmaktadır.

11. \[ L(M) = A \] makine M, A dilini tanır (recognizes) anlamına gelmektedir. M dil içindeki dizgiyi kabul eder.

12. Tuzak durumu (trap state), diğer kullanıbilen isimler:

    • dead state (ölü durum)
    • sink state (çukur durumu)

13. Boş küme DFA

13. DFA epsilon (0 uzunlukta dizgi)

3.5 BSO Örnek vidyolar

• Emre Sermutlu Deterministic Finite Automata (DFA) - I (Konu Anlatımı)
• Emre Sermutlu Deterministic Finite Automata (DFA) - II (Çözümlü Örnekler)