NFA, DFA, Regex, CFG, PDA

Özet

Hesaplama kuramında öğrenip unuttuğum bazı teorik bilgileri yeniledim. Unuttuğum ve en önemli olan kısım: Regex: NFA , CFG: PDA ikililerinin birbirleriyle bu kadar içli dışlı olduklarıydı. İyi oldu. Güzel oldu.

NFA, DFA, Regex, CFG, PDA

Finite Automata (Sonlu Otomat)

Sonlu otomatlar, düzenli dilleri kabul eden ya da fark eden basit bilgisayarlar/hesaplama sistemleridir. Sonlu otomat, bir alfabeden, bir durumlar kümesinden, bir geçiş fonksiyonundan, bir başlangıç ve bir ya da birden fazla kabul durumundan oluşur.
Şöyle gösterilir.
M = (Q, E, &, q0, F)
Q: Durumlar kümesi
E: Alfabe
&: Q x E -> Q şeklinde geçiş fonksiyonu
F: Kabul durumlar kümesi

Deterministic Finite Automata (Belirli Sonlu Otomat)

Belirli bir otomattır. Aynı anda makina aynı anda sadece bir durumda bulunabilir.

Non-Deterministic Finite Automata (Belirsiz Sonlu Otomat)

Epsilonun, yani boş karakteri girdi olarak kabul eden. Aynı anda birden çok durumda bulunabilen makinelerdir.

Regular Expressions (Düzenli ifadeler)

Düzenli ifadeler (regex), dilleri tanımlamak için kullanılan bir gösterim şeklidir. Üzerinde çalışması kolay olduğundan ötürü, genel olarak diller regexte tanımlanıp daha sonra NFA ya da DFA'e çevrilir.
Kuralları:
1|0 -> 1 ya da 0
10 -> 1 ve peşisıra 0
1* -> sıfır tane ya da daha fazla 1
* Örnek *
r = ( 00*1*00* ) | ( 11*0*11*)
Tanımlanan dil için geçerli girdiler.
00000
11111
11000111
11011
11001111111
010
00
11
...
Bu dil şöyle türkçe ile şöyle tanımlanabilir.
M : {x | x ayni sayiyla başlayıp aynı sayiyla biter}
DFA gösterimi
E : {1,0} /* Alfabe */
q0 : D1


Q : { D1, D2, D3, D4, D5} /* Durumlar */
& : {(D1, 1) -> D2 , (D3, 1) -> D3 , .. }
D1 durumundayken 1 gelirse D2 durumuna geçer.
D3 durumundayken 1 gelirse D3 durumuna geçer.
D4 durumundayken 0 gelirse D4 durumuna geçer.
F: {D4, D5} /* Kabul durumları */
Sonlu otomatlar ve düzenli ifadeler birbirlerine denktirler. Birbirlerine dönüştürülebilirler.
Düzenli ifadeler ve sonlu otomatlar bazı dilleri tanımlamak için yeterince güçlü değillerdir.
Örneğin: E = {$0^n1^n$ | n > 0 } gibi basit bir dili tanımlayamazlar.

Pushdown Automata

Pushdown Makineleri NFA lere çok benzer tek farkları fazladan bir stack bulundurmalarıdır.
stack: Son giren ilk çıkar türünde bir veri yapısıdır. Genelde şu iki fonksiyonu içinde barındırır. Push ve Pop. Push yığının tepesine yeni bir eleman ekler. Pop en üstteki elemanı çıkartır.

Context-free Gramer (İçerikten bağımsız gramer)

Regex NFA DFA için ne ise CFG de pushdown otomat için odur. Bir dil gösterim şeklidir. Kendini çağırmayı bilir.
Termialler ve non-terminaller vardır. CFG ler genişlerler. Non-terminaller genişler terminaller genişlemez. Bu bir örnekte anlaşılır.
S -> (S) | €; /* € epsilonu temsil ediyor. */
Bu gramerdeki terminaller: € , (, )
Non-terminal: S
Genişletiyorum.
S
(S)
((S))
(((S)))
((()))
Kendirini çağırabilirler derken kastettiğim buydu. S gidiyor ve (S) olarak bir daha kendini çağırıyor.
Örnek: CFG ile E = {$0^n1^n$ | n > 0 } gibi basit bir dilini tanımlıyoruz.
S -> 0S1 | €;
Bu kadar.
Pushdown ile aynı dili tanımlıyoruz.


~ ~TODO ~~
Bu post için düzenlenmesi gereken çok yer var.