Otomata Teorisi

OTOMATA TEORİSİ

Otomata Teorisine Giriş

Otomat teorisi (özdevinim) ya da otomata teorisi, teorik bilgisayar biliminde soyut makineleri ve bu makineleri kullanarak hesaplama problemlerinin çözülebilmesini araştıran daldır. Bu soyut makinelere otomat denir. Özdevinimler hesaplama kuramı, derleyici tasarımı ve çözümlemede önemli bir rol oynamaktadır.

Özdevinim Sınıfları

·         Deterministik sonlu özdevinim

·         Deterministik olmayan sonlu özdevinim

·         Deterministik olmayan sonlu özdevinim e-geçişli

·         Yığıtlı özdevinim

·         Doğrusal özdevinim

·         Turing makinesi

·         Zamanlı özdevinim

·         Deterministik Büchi Özdevinim

·         Deterministik olmayan Büchi özdevinim

·         Deterministik/ Deterministik olmayan Rabin özdevinim

·         Deterministik/ Deterministik olmayan Streett özdevinim

·         Deterministik/ Deterministik olmayan perite özdevinim

·         Deterministik/ Deterministik olmayan Muller özdevinim

Düzenli İfadeler

Bir düzenli ifade, çoğunlukla desen olarak geçen, dizgeler seti tanımlayan bir ifadedir. Genellikle tüm elemanları listelemeden setin kısa bir tanımını vermek için kullanılırlar. Bilgisayarcılıkta düzenlemeli ifadeler, ele alınan metindeki kimi katarların kısa yoldan ve esnek bir biçimde belirlenmesini sağlar. Bu katarlar belli karakterler, kelimeler veya karakter örüntüleri olabilir. Düzenlemeli ifadeler, bir biçimsel dil kullanarak yazılır ve bir düzenlemeli ifade işleyici tarafından yorumlanır. Bir düzenlemeli ifade işleyici, ya ayrıştırıcı üreteci olarak hizmet eden ya da metni inceleyip verilen tarife uygun kısımlarını belirleyen bir programdır. Aşağıdaki bir düzenlemeli ifade ile ifade edebilecek tariflere birkaç örnek görülebilir. Kullanım alanı özellikle bilgisayar ve veri girişi olan her yerde kullanım alanı vardır. Düzenli ifadeler, hesaplama alanında belirli yazılım kurallarına göre düzenlenmiş, bir dizge setini tanımlayan veya onunla uyuşan dizgelerdir. Düzenli ifadeler birçok metin düzenleyici, arama araçları ve metin tabanlı belirli desenleri idare etme araçları tarafından kullanılır. Birçok programlama dili dizgeleri idare etmek için düzenli ifadeleri destekler. Örneğin Perl ve Tcl direk kendi yazık kurallarına gömülü, güçlü düzenli ifadelere sahiptir.

Turing Makineleri

Turing makinesi, karmaşık matematiksel hesapların belirli bir düzenek tarafından yapılmasını sağlayan hesap makinesi.

Çalışma Prensibi

Bu tablo Turing makinesinin çalıştırdığı algoritmadır. Turing makinesi, her adımda

·         O anda kafanın görmekte olduğu sembolü okur.

·         Geçiş tablosunda okuduğu sembol ve o anki durumunu içeren bir girdi arar:

·         Eğer girdi olursa, yazılacak sembolü yazar veya kafasını hareket ettirir ve yeni duruma geçer. Makine, yeni durum ve kafanın okuduğu yeni sembol ile çalışmaya devam edecektir.

·         Eğer öyle bir girdi bulamaz ise, durur

NP

NP, belirsiz Turing Makinesi ile çokterimli zamanda çözülebilen karar problemlerini içeren karmaşıklık sınıfıdır. Bu sınıftaki problemler belirli Turing Makinesi ile çokterimli zamanda doğrulanabilirler ve bu şekilde doğrulanabilen her problem NP sınıfıdır. Bu nedenle NP, çokterimli zamanda doğrulanabilen problemlerin sınıfı olarak da tanımlanabilir. Belirli Turing Makinesi aynı zamanda belirsiz Turing makinesi olduğundan, P sınıfındaki bütün problemler aynı zamanda NP ’dir.

NP – Zor

En az bir NP problem kadar zor olan problemlerin bulunduğu sınıfa NP-Zor denir. Başka bir değişle, NP-Zor sınıfındaki herhangi bir problem çok terimli zamanda çözülebilirse, NP sınıfındaki bütün problemler çok terimli zamanda çözülebilir.

NP – Tam

NP-Tam, hem NP olup hem NP-Zor olan problemlerin sınıfıdır. Dolayısıyla bu sınıftaki problemler NP sınıfının en zor problemleridir. Herhangi biri çokterimli zamanda çözülebilirse, bütün hepsi çok terimli zamanda çözülebilir.