Sonlu Durum Makinaları (DFA,NFA)

SONLU DURUM MAKİNASI
Bir dil için “tanıyıcı” dendiği zaman, verilen bir katarın o cümlede anlamlı olup olmadığı kontrol edilmektedir. Tanıma işini yapmak için geçiş diyagramları kullanılır, bunlar sonlu durum makinaları olarak adlandırılmaktadır.
İki farklı sonlu durum makinası var, Deterministic Finite Automaton (DFA) ve Non-Deterministic Automaton (NFA). Bunların farkları, DFA daha hızlı tanıma yaparken, daha fazla alan kaplayabilmektedir.
(a|b)*abb ifadesi, a veya b ile başlayan katar kümelerinin abb katarı ile sonlandığını gösterir. Örneğin, aaaababb, abbbbbaabb ifadeleri…
NFA
1- S durumlar kümesi
2-Girdi sembolleri kümesi Σ
3-Geçiş Fonksiyonu, o anki durum değişkenine göre, başka durumlara geçmeyi sağlayan fonksiyon
4- s0 başlangıç durumu olarak tanımlanan bir değişken
5-F olarak tanımlanan son durumlar

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s