Otomata Teorisi III (Automata Theory III)

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

1. Deterministik Sonlu Otomata (DFA)

2. Deterministik Olmayan Sonlu Otomata (NDFA / NFA)

Deterministik Olmayan Sonlu Otomata (Non-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. 

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

1. Q durumların kümesidir.

2. Σ alfabesi denilen sembollerin bir kümesidir.

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

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

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

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

Q = { q0, q1, q2, q3 } 

Σ = { a }

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

F = { q2}
δ = { q0, a } = { q1, q2 }
δ* = { q0, aa } = q2

Geçiş Tablosu (Transition Table)

δ	a
q0	q1, q3
q1	q2
q2	-
q3	-

Level I

Level II

a

a

a

a

a

a

Lambda Geçişleri (Lambda Transitions)

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

Q = { q0, q1, q2, q3 } 

Σ = { a }

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

F = { q3 }
δ = { q0, a } = q1
δ* = { q0, aa } = q3

Level I

a

a

Level II

Level III

a

a

Level IV

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

Q = { q0, q1, q2 } 

Σ = { 0, 1 }

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

F = { q0 }
δ = { q0, 1 } = q1
δ* = { q0, 10 } = { q0 ,q2 }

Level I

1

0

Level II

1

0

Level III 

λ

Level I

Sonlu Olmayan Otomata (NFA), Sonlu Otomata(DFA) Dönüşümü 

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

Q = { q0, q1, q2  } 

Σ = { a, b }

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

F = { q1 }
δ = { q0, a } =  q1 
δ* = { q0, aa } = q1

1. aşamada NFA'da belirlenen başlangıç durumu (initial state) oluşturulur. 

Level I

 2. aşamada NFA'da q0 durumundayken a stringi gelirse hangi durumlara geçiş yapılır:

δ* ( q0, a ) = { q1, q2 }

Level II

 3. aşamada NFA'da q0 durumundayken b stringi gelirse hangi durumlara geçiş yapılır:

                                                                      δ* ( q0, b ) = Ø

Level III

 4. aşamada NFA'da q1 veya q2 durumundayken a stringi gelirse hangi durumlara geçiş yapılır:

                                                δ* ( q1, a ) = { q1, q2 }   U δ* ( q2, a ) = Ø

Level IV

 5. aşamada NFA'da q1 veya q2 durumundayken b stringi gelirse hangi durumlara geçiş yapılır:
                                                  δ* ( q1, b ) = { q0 }   U δ* ( q2, b ) = { q0 }

Level V

 6. aşamada NFA'da a ve b ile tüm durumlara geçişler kontrol edilir. Durumlardan trap state kendi üzerinden a ve b ile geçiş sağlanır.
                                                                     
                                                                    

Level VI

 7. aşamada NFA'da accept(kabul edilen) durumu belirlenir. Bunun için NFA'da accept durumunda olan durum DFA da accept state kabul edilir.

                                                                        { q1, q2 } ∈ F 

Level VII

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