Otomat teorisi özdevinim kuramı ya da otomata teorisi teorik bilgisayar biliminde soyut makineleri ya da daha uygun bi

Otomat teorisi (özdevinim kuramı ya da otomata teorisi), teorik bilgisayar biliminde soyut makineleri (ya da daha uygun bir deyimle soyut 'matematiksel' makineleri veya sistemleri) ve bu makineleri kullanarak hesaplama problemlerinin çözülebilmesini araştıran daldır. Bu soyut makinelere otomat denir. Otomat kelimesinin kökeni Yunanca "Grekçe: αὐτόματα" kelimesi olup "kendi kendine hareket eden" demektir.

Bir otomat örneği. Otomat teorisinde, bu gibi otomatların matematiksel özellikleri incelenir.

Biçimsel dil kuramı ile yakından ilgilidir. Özdevinirler derleyici tasarımı ve ayrıştırmasında önemli rol oynar.

Otomatlar hesaplama teorisi, derleyici tasarımı ve (İngilizce: parsing) önemli bir rol oynamaktadır.

Otomat

Bir otomat 5 elemanlı bir demet ile tanımlanır ⟨Q,∑,δ,q₀,F⟩:

Q sonlu durumların kümesi
∑ sonlu simgelerin kümesi
δ transition fonksiyonudur: δ: Q × ∑ → Q
q₀, başlangıç durumu (q₀ ∈ Q koşuluyla)
F, Q'nun durumlarıdır (F ⊆ Q)

Özdevinim sınıfları

Deterministik sonlu özdevinim (Deterministic finite automata)
(Nondeterministic finite automata)
Deterministik olmayan sonlu özdevinim ε-geçişli (Nondeterministic finite automata with ε-transitions
(Pushdown automata)
(Linear bounded automata)
Turing makinesi
(Timed automata)
(Deterministic Büchi automata)
(Nondeterministic Büchi automata)
(Nondeterministic/Deterministic Rabin automata)
(Nondeterministic/Deterministic Streett automata)
(Nondeterministic/Deterministic parity automata)
(Nondeterministic/Deterministic Muller automata)

Ayrıca bakınız

Sonlu durum makinesi