Finite Automaton
Sonlu sayıda durum ve geçişle bir girdi dizgesini sembol sembol işleyerek kabul veya ret kararı veren soyut makine modeli.
Sonlu otomat, belleğini sonlu bir durum kümesiyle sınırlar. Temel model Q, alfabe Σ, geçiş işlevi δ, başlangıç durumu q0 ve kabul durumları F bileşenleriyle tanımlanır.
Deterministik modelde her durum ve girdi sembolü için tek sonraki durum vardır. Nondeterministik model birden çok olası geçişe izin verebilir; buna rağmen DFA ve NFA aynı düzenli dil sınıfını tanır.
Sözcüksel çözümlemede sonlu otomat karakter akışından token tanır. İç içe parantezler gibi sınırsız eşleme gerektiren sözdizimsel yapılar ise genel durumda yığın belleği gerektirir; bunlar için bağlamdan bağımsız gramer ve pushdown automaton modelleri kullanılır. Sonlu otomatla token tanıma, bütün programlama dili sözdizimini doğrulamakla eşdeğer değildir.
Bir sonlu otomatın dili, başlangıç durumundan başlayıp kabul durumunda bitiren dizgeler kümesidir. Gramer tarafındaki karşılığı için Sağ Doğrusal Dilbilgisi, bütün konu için Otomatlar Kuramı ve Biçimsel Diller kullanılabilir.