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.
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.