Günümüzün teknolojik çağında hem donanım hem de yazılım alanında muazzam bir gelişme görülmüştür. Donanım tasarım yöntemlerinde önemli gelişme alanlarından biri görüldü. İle büyüyen teknoloji , Donanım - Yazılım ortak tasarımı kavramını uygulamak mümkün oldu. Farklı yöntemler geliştirilerek, yazılım kullanmak Donanım sistemleri tamamen tasarlanabilir ve simüle edilebilir. Bu tür yöntemlerden biri Otomata Teorisidir. Otomata teorisi, bilgisayar Bilimi önceden belirlenmiş adım sırasını otomatik olarak izleyen bilgisayar cihazlarının soyut modelinin tasarlanmasıyla ilgilenir. Bu makale, otomata öğreticisiyle ilgili kısa bilgileri tartışır.
Otomata Teorisi nedir?
Otomata kelimesi, 'kendi kendine hareket eden' anlamına gelen Yunancadan türemiştir. Otomat, makinenin matematiksel bir modelidir. Otomat, durumlardan ve geçişlerden oluşur. Giriş otomata verildiğinde, geçiş fonksiyonuna bağlı olarak bir sonraki duruma geçiş yapar. Geçiş fonksiyonunun girdileri mevcut durum ve son sembollerdir. Bir Otomat, sonlu sayıda duruma sahipse, Sonlu Otomata olarak bilinir veya Sonlu durum makinesi . Sonlu otomatlar bir 5-tuple (Q, ∑, δ, qo, F) ile temsil edilir.
Nerede,
Q = Sonlu durum kümesi.
∑ = Otomata Alfabesi olarak da adlandırılan sonlu semboller kümesi.
δ = geçiş işlevi.
qo = girişin başlangıç durumu.
F = Q'nun son durumları kümesi.
Otomata Teorisinin Temel Terminolojileri
Otomata Teorisinin temel terminolojilerinden bazıları şunlardır:
1 . Alfabe : Otomata teorisindeki herhangi bir sonlu sembol kümesi Alfabe olarak bilinir. Harfi ile temsil edilen {a, b, c, d, e,} kümesi Alfabe kümesi olarak adlandırılırken, 'a', 'b', 'c', 'd', 'e' kümelerinin harfleri semboller.
iki . Dize : Otomatada, bir dize alphabet alfabe kümesinden alınan sonlu bir sembol dizisidir, Örneğin, S = 'adeaddadc' dizesi = {a, b, c, d, e,} alfabe seti üzerinde geçerlidir.
3 . Dize Uzunluğu : Dizede bulunan sembollerin sayısı Dizenin uzunluğu olarak bilinir. S = 'adaada' dizesi için dizenin uzunluğu | S | = 6. Dizenin uzunluğu 0 ise, boş dizge olarak adlandırılır.
4 . Kleen Yıldızı : Λ semboller kümesindeki tekli işleçtir, λ dahil tüm olası dizelerin sonsuz kümesini over kümesi üzerindeki tüm olası uzunluklar verir. Tarafından temsil edilir. Örneğin, Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……} kümesi için.
5 . Kleen Kapatma : Alfabe kümesinin λ hariç tüm olası dizilerinin sonsuz kümesidir. İle gösterilir. Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..} kümesi için.
6 . Dil : Dil, bazı Alfabe seti Σ için Kleene yıldız kümesinin * * alt kümesidir. Dil sonlu veya sonsuz olabilir. Örneğin, bir dil 2 uzunluğundaki tüm olası dizeleri Σ = {a, d} kümesi üzerinden alırsa, L = {aa, ad, da, dd}.
Biçimsel Diller ve Otomatlar
Otomata teorisinde, Biçimsel dil, her dizgenin sembollerden oluşur sonlu Alfabe kümesine ait Σ. Aşağıdaki sonsuz kümeden herhangi bir dizgeyi içerebilen bir kedi dili düşünelim ...
kafese koymak!
meww!
mewww !! ……
Kedi dili için alfabe seti Σ = {m, e, w,!} Şeklindedir. Bu setin Sonlu Durum Otomata Modeli-m için kullanılmasına izin verin. Daha sonra model m ile karakterize edilen biçimsel dil şu şekilde gösterilir:
L (m)
L (m) = {'mew!', 'Meww!', 'Mewww', ……}
Otomat, bir dili tanımlamak için kullanışlıdır çünkü sonsuz bir kümeyi kapalı bir biçimde ifade edebilir. Biçimsel diller, günlük yaşamımızda konuştuğumuz doğal dillerle aynı değildir. Biçimsel bir dil, normal dillerimizin aksine makinenin farklı durumlarını ifade edebilir. Biçimsel dil, sözdizimi vb. Gibi doğal dilin bir bölümünü modellemek için kullanılır… Biçimsel diller, sonlu durum otomatıyla tanımlanır. Sonlu durum otomatının iki ana perspektifi vardır: Bir dizginin dilde olup olmadığını anlayabilen alıcılar ve ikincisi, dilde yalnızca dizeleri üreten üreteçtir.
Deterministik Sonlu Otomata
Deterministik otomatlarda bir girdi verildiğinde, geçişin hangi duruma geleceğini her zaman belirleyebiliriz. Bu sonlu bir otomat olduğundan, buna Deterministik Sonlu Otomata denir.
Grafik Gösterim
Durum Diyagramı, Belirleyici Sonlu Otomatların grafiksel gösterimi için kullanılan digraflardır. Bir örnekle anlayalım. Belirleyici sonlu otomata…
S = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} ve geçiş işlevi
Grafik Gösterim Tablo Formu
Durum diyagramı
Deterministik Sonlu Durum Otomatının Durum Diyagramı
Durum diyagramından
- Durumlar köşelerle temsil edilir.
- Geçişler, bir giriş alfabesiyle etiketlenmiş yay ile temsil edilir.
- Gelen boş tek ark, ilk durumu temsil eder.
- Çift daireli durum son durumdur.
Belirleyici Olmayan Sonlu Otomata
Verilen giriş için çıkış durumunun belirlenemediği otomata Belirleyici Olmayan Otomata denir. Sonlu sayıda duruma sahip olduğu için Belirleyici Olmayan Sonlu Otomata olarak da adlandırılır. Belirleyici olmayan Sonlu Otomata, (Q, ∑, δ, qo, F)
Q = sonlu durum kümesi.
∑ = Alfabe seti.
δ = geçiş işlevi
nerede : 
qo = Başlangıç hali.
Grafik Gösterim
Belirleyici olmayan sonlu otomatlar, durum diyagramı yardımıyla temsil edilir. Belirleyici Olmayan Sonlu Otomata ...
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Geçişler
Grafik Gösterim Tablo Formu
Durum diyagramı
Belirleyici Olmayan Sonlu Otomatların Durum Diyagramı
Otomata Teorisi Uygulamaları
Uygulamaları otomata teorisi aşağıdakileri dahil edin.
- Otomata teorisi, hesaplama teorisi, derleyici üretimleri, AI vb. Alanlarda çok kullanışlıdır.
- Metin işleme derleyicileri ve donanım tasarımları için sonlu otomata önemli bir rol oynar.
- AI ve in uygulamalar için Programlama dilleri Bağlamdan bağımsız gramer çok kullanışlıdır.
- Biyoloji alanında, Hücresel otomatlar faydalıdır.
- Sonlu alanlar teorisinde, Otomata'nın uygulamasını da bulabiliriz.
Bu makalede, otomata teorisi dilleri ve hesaplamaya kısa bir giriş öğrendik. Otomata tarih öncesi dönemden beri var. Yeni teknolojilerin icat edilmesiyle bu alanda birçok yeni gelişme görülüyor. Hangi tür otomatlarla karşılaştınız?
