Otomata Teorisi II (Automata Theory II)

FA (Finite Automaton) iki tip halinde sınıflandırılabilir:

1. Deterministik Sonlu Otomata (DFA)

2. Deterministik Olmayan Sonlu Otomata (NDFA / NFA)

Deterministik Sonlu Otomata (Deterministic Finite Automata)

DFA'daki, her bir giriş sembolü için, makinenin bir hareket durumunun ifadesidir. Dolayısıyla sonlu sayıda duruma  sahip olduğundan sonlu durum makinesi de denir. 

DFA  6 başlığın ile temsil edilebilir (Q, Σ, δ, q0, F, δ*). Bunlar:

1. Q tüm durumların kümesidir.

2. Σ alfabesi denilen sembollerin bir kümesidir. (λ bu kümenin elemanı değildir)

3. δ: Q × Σ → Q, karakterlerle geçiş fonksiyonudur.

4. q0 (q0 ∈ Q) başlangıç durumunu ifade eder.

5. F (F ⊆ Q) sonlu durumların kümesidir.
6. δ* = { q, word } = q' string ile geçiş fonksiyonudur.

Egzersiz
Aşağıdaki ifadelerle bir sonlu durum makinesi ifade edilmektedir.

Q = {q0, q1, q2, q3, q4, q5} 

Σ = {a, b}

Başlangıç Durumu (İnitial State) = q0

F = { q4 }
δ = { q0, a } = q1
δ* = { q0, ab } = q2

Geçiş Tablosu (Transition Table)

δ	a	b
q0	q1	q5
q1	q5	q2
q2	q5	q3
q3	q4	q5
q4	q5	q5
q5	q5	q5

Accept (Kabul Edilen) String

Görüldüğü gibi Σ = {a, b} alfabenin her stringi için bir durumdan diğer duruma geçiş sağlanmıştır.

Level I

Level II

a

b

b

a

Level III

a

b

b

a

Level IV

a

b

b

a

Level V

a

b

b

a

Level VI

Reject (Red Edilen) String
Görüldüğü gibi abba stringi dışında gelen herhangi bir stringi sonlu durum makinesi trap (q5) durumuna geçiş sağlamaktadır.

a

b

a

Level I

a

b

a

a

b

a

Level II

a

b

a

Level III

Diğer Reject (Red Edilen) String

λ

Level I

Egzersiz
Üsteki egzersizde belirtilen sonlu durum makinesine davranışını değiştirecek 2 adet initial state eklenirse kabul edeceği stringler nasıl ifade edilir?

Q = {q0, q1, q2, q3, q4, q5} 

Σ = {a, b}

Başlangıç Durumu (İnitial State) = q0

F = { q0, q2, q4 }
δ = { q0, a } = q1
δ* = { q0, ab } = q2

Davranışı Değişen Sonlu Durum Makinesi 

λ

Level I

Bu sonlu durum makinesinin kabul ettiği bir string örneklenmiştir. Buna göre bu otomatanın dili:
L = {λ, ab, abba} olacaktır.

Egzersiz
Aşağıda çift sayıda 1 kabul eden bir sonlu durum makinesi ifade edilmektedir?

Q = { q0, q1 } 

Σ = { 1 }

Başlangıç Durumu (İnitial State) = q0

F = { q0 }
δ = { q0, 1 } = q1
δ* = { q0, 11 } = q0

1

1

Bu sonlu durum makinesinin kabul ettiği bir string örneklenmiştir. Buna göre bu otomatanın dili:
L = { x : x ∈ Σ* ve x çift olmak üzere } veya L = {λ, 11, 1111, 111111, ... } olacaktır.

Karakter ile (δ: Q × Σ → Q) ve String ile (δ*: Q × Σ* → Q) Geçiş Fonksiyonları 

Karakteri ile (δ: Q × Σ → Q) geçiş fonksiyonu

δ = { q1, b } = q2

Karakter ile Geçiş Fonksiyonu Geçiş Fonksiyonu

String ile (δ: Q × Σ* → Q) geçiş fonksiyonu
δ* = { q0, abb } = q3

Özel Durum: δ* = { q, λ } = q

δ* = { q1, λ } = q1

String ile Geçiş Fonksiyonu Simülasyonu

Kabul Edilen ve Kabul Edilmeyen Dil Tanımları

M = {Q, Σ, δ, q0, F} 

M kabul edilen bir dil
L(M) = { w ∈ Σ*: δ* { q0, word } ∈ F }

M = {Q, Σ, δ, q0, F} 

M kabul edilmeyen bir dil
L(M)' = { w ∈ Σ*: δ* { q0, word } Ï F }

Bir sonraki yazımda görüşmek üzere...