algoritma |

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