Sonlu Durum Otomatları

Report
SONLU DURUM OTOMATLARI
Yılmaz Kılıçaslan
Sunum Planı
 Kısa Tarihçe
 Sonlu Durum Otomatlarına Formel Olmayan Giriş
 Deterministik Sonlu Durum Otomatı
 Deterministik Olmayan Sonlu Durum Otomatı
 Boş Geçişli Sonlu Durum Otomatı
 Çift Yönlü Sonlu Durum Otomatı
 Eş Güçte Sonlu Durum Otomatları
2
Kısa Tarihçe
 1930’lar – Turing Makinesi – Karar Problemi
 1940’lar
Sonlu Durum Otomatları
 1950’ler
Formel Gramerler
 1960’lar – ‘Tractability’ Problemi
3
NEHRİN KARŞI YAKASINA GEÇME PROBLEMİ
wgcM
gM→
w c
1.Adım
gM→
w c
2.Adım
←M
g
w
3.Adım
cM→
g
w
4.Adım
←gM
c
g
5.Adım
wM →
c
g
6.Adım
←M
w
c
7.Adım
gM→
w gc M
c
m
m
g
Start
MWGC-Ø
WC-GM
MWC-G
m
g
w
w
c
c
C-MWG
g
W-CMG
g
CMG-W
g
Ø-MWGC
g
c
GM-WC
g
m
m
g
g
WMG-C
c
w
w
G-MWC
w
Açma/Kapama Düğmesi
13
‘then’ Sözcüğünün Tanınması
14
Dil – Problem İlişkisi
15
Deterministik Sonlu Durum Otomatı
16
Geçiş Diyagramı
17
‘01’ dizilimlerini içeren katarları tanıyan
deterministik sonlu durum otomatı
18
Çift sayıda 0 ve çift sayıda 1 içeren
sembol katarlarını tanıyan otomat
19
Deterministik Olmayan Sonlu
Durum Otomatları
20
‘01’ ile biten bütün dizilimleri tanıyan
deterministik olmayan sonlu durum otomatı
21
‘web’ ve ‘ebay’ sözcüklerini arayan
otomat
22
Boş Geçişli Sonlu Durum Otomatları
23
Sözcük tanımada boş geçiş kullanımı
24
Eş Güçte Sonlu Durum Otomatları
 Aşağıdaki otomat türleri tanıyabilecekleri /
üretebilecekleri diller açısından eş güçtedirler:
–
–
–
–
Deterministik Sonlu Durum Otomatları
Deterministik Olmayan Sonlu Durum Otomatları
Boş Geçişli Sonlu Durum Otomatları
Çift Yönlü Sonlu Durum Otomatları
25
Kaynaklar
 Hopcroft, J.E, Motwani, R. and J.D. Ullman
(2001), Introduction to Automata Theory,
Languages and Computation, Addison-Wesley.
26

similar documents