Özdevinim kuramı

Bir özdevinim örneği. Özdevinim kuramında, bu gibi özdevinimlerin matematiksel özellikleri incelenir.

Özdevinim kuramı, otomat kuramı ya da otomata kuramı, kuramsal 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 özdevinim ya da otomat denir. Otomat kelimesinin kökeni Yunanca'dır (αὐτόματα) ve "kendi kendine hareket eden" anlamına gelir.

Özdevinimler hesaplama kuramı, derleyici tasarımı ve çözümlemede (parsing) önemli bir rol oynamaktadır.

Özdevinim sınıfları

• Deterministik sonlu özdevinim (Deterministic finite automata)
• Deterministik olmayan sonlu özdevinim (Nondeterministic finite automata)
• Deterministik olmayan sonlu özdevinim ε-geçişli (Nondeterministic finite automata with ε-transitions
• Yığıtlı özdevinim (Pushdown automata)
• Doğrusal sınırlı özdevinim (Linear bounded automata)
• Turing makinesi
• Zamanlı özdevinim (Timed automata)
• Deterministik Büchi özdevinim (Deterministic Büchi automata)
• Deterministik olmayan Büchi özdevinim (Nondeterministic Büchi automata)
• Deterministik/Deterministik olmayan Rabin özdevinim (Nondeterministic/Deterministic Rabin automata)
• Deterministik/Deterministik olmayan Streett özdevinim (Nondeterministic/Deterministic Streett automata)
• Deterministik/Deterministik olmayan perite özdevinim (Nondeterministic/Deterministic parity automata)
• Deterministik/Deterministik olmayan Muller özdevinim (Nondeterministic/Deterministic Muller automata)

Ayrıca bakınız

• Biçimsel dil kuramı
• Sonlu durum makinası
• Otomat