Otomata teorisi, sonlu otomata
Çeşitli makinelerin yapısı, tasarımı, çalışma prensibi büyük ölçüde işlevsel amacına göre belirlenir. Teknolojik, ulaşım, bilgi işlem, askeri ve diğer makineler arasında ayrım yapın. Karmaşık teknolojik süreçleri gerçekleştirmek için tasarlanmış tüm otomatik kompleksler, çeşitli endüstrilerde yaygın olarak kullanılmaktadır. Otomatlar, çeşitli mantıksal işlevleri (mantıksal makineler) gerçekleştirecek şekilde tasarlanmış ve üretilmiştir.
otomata teorisi — sibernetik bölümü, dijital bilgisayarlar ve kontrol makineleri teknolojisinin gereksinimlerinin etkisi altında ortaya çıkan. Otomat teorisinde incelenen ayrık otomatlar, ayrık (dijital) bilgiyi ayrık zaman adımlarında işleyen gerçek sistemlerin (hem teknik hem de biyolojik) soyut modelleridir.
Otomata teorisi, otomatın işleyişi (davranışı) ve yapısı (iç yapısı) hakkında sezgisel fikirleri resmileştiren kesin matematiksel kavramlara dayanır.
Bu durumda bilgi dönüşümü her zaman, giriş alfabesindeki harflerden oluşan girdi dizilerini, çıktı alfabesindeki harflerden oluşan çıktı dizilerine dönüştüren bir işlem olarak anlaşılmaktadır.
Matematiksel mantık, cebir, olasılık teorisi, kombinatorik ve grafik teorisi aparatı yaygın olarak kullanılmaktadır.
Bazı kısımlarında otomata teorisi ile ilgili sorun (otomata yapısal teorisi) büyüdü röle kontak devreleri teorisinden1930'ların sonlarında şekillenmeye başlayan. dahil mantıksal cebir yöntemleri.
Otomatların yapısal teorisinde, bir sisteme uygun şekilde bağlanmış daha basit bileşenlerden (öğeler) karmaşık bir otomatın nasıl oluşturulduğunu açıklamak için tasarlanmış farklı şema türleri incelenir.
Soyut otomat teorisi olarak adlandırılan başka bir yön, otomatların davranışını (yani, onlar tarafından gerçekleştirilen bilgi dönüşümünün doğasını) incelerken, iç yapılarının özelliklerinden soyutlayarak ve 1950'lerde ortaya çıktı.
Soyut otomata teorisi çerçevesinde, "otomat" ve "makine" kavramlarının içeriği, bir otomat tarafından gerçekleştirilen bilgi dönüşümünün standart tanımıyla esasen tükenmiştir. Böyle bir dönüşüm deterministik olabilir, ancak doğası gereği olasılıksal da olabilir.
En çok çalışılan, otomata teorisinde çalışmanın ana amacı olan sonlu otomatları içeren deterministik makinelerdir (otomatlar).
Bir sonlu durum makinesi, sınırlı miktarda bellek (dahili durumların sayısı) ile karakterize edilir ve bir geçiş işlevi kullanılarak tanımlanır.Makul bir idealleştirmeyle, tüm modern matematik makineleri ve hatta beyin, işleyişleri açısından sonlu otomatlar olarak kabul edilebilir.
"Sıralı makine", "Milly otomat", "Moore otomat" terimleri literatürde (ve tüm yazarlar tarafından aynı şekilde değil) "sonlu otomat" teriminin eşanlamlıları olarak veya sonlu bir geçiş fonksiyonlarındaki belirli özellikleri vurgulamak için kullanılmaktadır. otomat.
Sınırsız belleğe sahip otomata, herhangi bir verimli bilgi dönüşümünü (potansiyel olarak) gerçekleştirebilen bir Turing makinesidir. "Turing makinesi" kavramı, "sonlu durum makinesi" kavramından daha önce ortaya çıktı ve esas olarak algoritma teorisinde inceleniyor.
Soyut otomata teorisi, yarıgrup teorisi gibi iyi bilinen cebirsel teorilerle yakından ilişkilidir. Uygulamalı bir bakış açısından, bir otomattaki bilgilerin dönüşümünü bellek boyutu açısından karakterize eden sonuçlar ilgi çekicidir.
Bu, örneğin, otomat deneyleriyle ilgili problemlerde (E.F. Moore, vb. tarafından yapılan çalışmalar), otomatın geçiş işlevleri veya belleğinin kapasitesi hakkında şu veya bu bilginin sonuçlarından elde edildiği durumdur. deneyler.
Başka bir görev, otomatın bellek boyutu ve giriş dizilerinin periyotları hakkında mevcut bilgilere dayanarak çıkış sekanslarının periyotlarını hesaplamaktır.
Sonlu durum makinelerinin belleğini en aza indirmek ve davranışlarını rastgele ortamlarda incelemek için yöntemlerin geliştirilmesi büyük önem taşımaktadır.
Soyut otomata teorisinde sentez problemi şudur.Açıkça biçimlendirilmiş bir dil açısından, tasarlanan otomatın davranışı için koşullar yazılır (otomatta temsil edilen olay için). Bu durumda, yazılan her koşula göre yöntemler geliştirmek gerekir:
1) kendisi tarafından dönüştürülen bilgilerin bu koşulu karşıladığı böyle bir durum makinesi olup olmadığını öğrenin;
2) evet ise, böyle bir sonlu durum makinesinin geçiş fonksiyonları oluşturulur veya hafıza boyutu tahmin edilir.
Böyle bir formülasyonda sentez görevinin çözümü, kayıttan geçişli fonksiyonlara geçiş için uygun algoritmalarla bir otomatın çalışma koşullarını kaydetmek için uygun bir dilin ön oluşturulmasını gerektirir.
Otomatların yapısal teorisinde, sentez problemi, geçiş fonksiyonları tarafından verilen sonlu bir otomatı gerçekleştiren belirli bir tipte bir elemanlar zincirinin inşa edilmesinden oluşur. Bu durumda, genellikle bazı optimallik kriterleri (örneğin, minimum eleman sayısı) belirtirler ve optimal bir şema elde etmeye çalışırlar.
Daha sonra ortaya çıktığı gibi, bu, daha önce röle kontak devreleriyle ilgili olarak geliştirilen bazı yöntem ve kavramların başka tipteki devrelere uygulanabileceği anlamına gelir.
Elektronik teknolojilerin gelişmesiyle bağlantılı olarak, en yaygın olanı şemalardır. işlevsel öğelerin (mantıksal ağlar). Mantık ağlarının özel bir durumu, öğeleri nöron olarak adlandırılan soyut sinir ağlarıdır.
Devrelerin türüne ve amaçlandıkları bilginin dönüştürülmesine bağlı olarak birçok sentez yöntemi geliştirilmiştir (Röle cihazlarının sentezi).
Bakmak -Kombinasyonel devrelerin minimizasyonu, Carnot haritaları, devre sentezi
Sonlu durum makinesi — sabit (çalışma sırasında artamayan) bellek boyutuna sahip bir kontrol sisteminin matematiksel modeli.
Sonlu durum makinesi kavramı, bir dizi kontrol sisteminin (örneğin, çok döngülü bir röle cihazı) genel özelliklerini karakterize eden matematiksel bir soyutlamadır. Bu tür sistemlerin tümü, sonlu bir otomatın tanımı olarak kabul edilmesi doğal olan ortak özelliklere sahiptir.
Tamamlanan her otomatın dış etkilere ve iç unsurlara açık bir girişi vardır. Hem girdi hem de iç öğeler için, alabilecekleri sabit sayıda ayrık durum vardır.
Girdi ve dahili öğelerin durumlarındaki değişiklik, zaman içinde ayrık anlarda meydana gelir ve aralarındaki aralıklara tikler adı verilir. Bandın sonundaki dahili durum (dahililerin durumu), tamamen dahili durum ve bandın başlangıcındaki girdinin durumu tarafından belirlenir.
Sonlu bir otomatın diğer tüm tanımları, özellikle sonlu bir otomatın belirli bir zamanda otomatın dahili durumuna bağlı bir çıktıya sahip olduğunu varsayan tanımlar bu özelliğe indirgenebilir.
Böyle bir özellik açısından, girdilerinin ve iç durumlarının doğası, tam bir otomatın tanımıyla ilgisizdir. Girişler ve durumlar yerine, rastgele bir numaralandırmada sayılarına bakabilirsiniz.
Durum makinesi, dahili durum numarasının önceki dahili durum numarasına ve önceki giriş durum numarasına bağımlılığı belirtilirse kurulacaktır. Böyle bir görev, bir final tablosu şeklinde olabilir.
Tam bir otomat tanımlamanın başka bir yaygın yolu, sözde yapımıdır. geçiş diyagramları. Girdi durumları genellikle basit girdiler olarak adlandırılır ve dahili durumlar basit durumlardır.
Bir sonlu durum makinesi, hem teknik cihazların hem de bazı biyolojik sistemlerin bir modeli olabilir. Birinci tipteki otomatlar, örneğin röle cihazları ve çeşitli elektronik bilgisayarlar, dahil. programlanabilir mantık denetleyicileri.
Bir röle cihazı söz konusu olduğunda, giriş durumlarının rolü, röle cihazının hassas elemanlarının durum kombinasyonları tarafından oynanır (bu tür durumların her bir kombinasyonu, cihazın tüm hassas elemanlarının bir göstergesi ile karakterize edilen "karmaşık bir durumdur"). belirli bir anda sahip oldukları bu ayrık durumlar). Benzer şekilde, bir röle cihazının ara elemanlarının durum kombinasyonları da dahili durumlar olarak işlev görür.
Programlanabilir bir mantık denetleyicisi (PLC), bağımsız durum makinesi olarak adlandırılabilecek bir röle eylem aygıtı örneğidir.
Aslında, program PLC'ye girdikten ve kontrolör hesaplamaya başladıktan sonra, dış etkilere maruz kalmaz ve sonraki her durum tamamen önceki durumu tarafından belirlenir. Girişin her saat döngüsünde aynı duruma sahip olduğunu varsayabiliriz.
Tersine, tek olası girdi durumuna sahip herhangi bir sonlu durum makinesine doğal olarak otonom denir, çünkü bu durumda dış ortam davranışını kontrol eden hiçbir bilgi taşımaz.
Ayrıca bakınız:
PLC kullanımı örneği üzerinde elektrik mühendisliğinde mikroişlemcili sistemlerin kullanımı