Teori automata, automata terhingga
Struktur, reka bentuk, prinsip operasi pelbagai mesin sebahagian besarnya ditentukan oleh tujuan fungsinya. Bezakan antara mesin teknologi, pengangkutan, pengkomputeran, ketenteraan dan lain-lain. Keseluruhan kompleks automatik yang direka untuk melaksanakan proses teknologi yang kompleks diperkenalkan secara meluas dalam pelbagai industri. Automata direka dan dibina yang melaksanakan pelbagai fungsi logik (mesin logik).
Teori automata — bahagian sibernetik, yang timbul di bawah pengaruh keperluan teknologi komputer digital dan mesin kawalan. Automata diskret yang dikaji dalam teori automata ialah model abstrak sistem sebenar (kedua-dua teknikal dan biologi) yang memproses maklumat diskret (digital) pada langkah masa diskret.
Teori automata didasarkan pada konsep matematik yang tepat yang memformalkan idea intuitif tentang fungsi (tingkah laku) automaton dan tentang strukturnya (struktur dalaman).
Dalam kes ini, transformasi maklumat sentiasa difahami sebagai operasi yang mengubah jujukan input yang terdiri daripada huruf daripada abjad input kepada jujukan output yang terdiri daripada huruf daripada abjad output.
Radas logik matematik, algebra, teori kebarangkalian, kombinatorik dan teori graf digunakan secara meluas.
Masalah dengan teori automata dalam beberapa bahagiannya (teori struktur automata) berkembang daripada teori litar hubungan geganti, yang mula terbentuk pada akhir 1930-an. inklusif kaedah algebra logik.
Dalam teori struktur automata, pelbagai jenis skema dikaji, direka bentuk untuk menerangkan bagaimana automata yang kompleks dicipta daripada komponen yang lebih ringkas (elemen) yang disambungkan dengan betul dalam sistem.
Satu lagi arah, yang dipanggil teori abstrak automata, mengkaji tingkah laku automata (iaitu, sifat transformasi maklumat yang dijalankan oleh mereka), sambil mengabstraksi daripada spesifik struktur dalaman mereka, dan timbul pada tahun 1950-an.
Dalam kerangka teori abstrak automata, kandungan konsep "automaton" dan "mesin" pada dasarnya telah habis oleh penerangan standard transformasi maklumat yang dijalankan oleh automaton. Transformasi sedemikian boleh bersifat deterministik, tetapi ia juga boleh bersifat probabilistik.
Yang paling dikaji ialah mesin deterministik (automata), yang merangkumi automata terhingga — objek utama kajian dalam teori automata.
Mesin keadaan terhingga dicirikan oleh jumlah memori yang terhad (bilangan keadaan dalaman) dan ditakrifkan menggunakan fungsi peralihan.Dengan beberapa idealisasi yang munasabah, semua mesin matematik moden dan juga otak, dari sudut fungsinya, boleh dianggap sebagai automata terhingga.
Istilah "mesin berjujukan", "automaton Milly", "automaton Moore" digunakan dalam kesusasteraan (dan tidak seragam oleh semua pengarang) sebagai sinonim bagi istilah "automaton terhingga" atau untuk menekankan ciri-ciri tertentu dalam fungsi peralihan sesuatu terhingga. automaton.
Automata dengan memori tanpa had ialah mesin Turing yang mampu melakukan (berpotensi) sebarang transformasi maklumat yang cekap. Konsep "Mesin Turing" timbul lebih awal daripada konsep "mesin keadaan terhingga" dan terutamanya dikaji dalam teori algoritma.
Teori automata abstrak berkait rapat dengan teori algebra yang terkenal, contohnya teori semikumpulan. Dari sudut pandangan yang digunakan, hasil yang mencirikan transformasi maklumat dalam automasi dari segi saiz memori adalah menarik.
Ini berlaku, sebagai contoh, dalam masalah dengan eksperimen pada automata (kerja oleh E.F. Moore, dsb.), di mana satu atau lain maklumat tentang fungsi peralihan automaton atau tentang kapasiti ingatannya diperoleh daripada hasil eksperimen.
Tugas lain adalah untuk mengira tempoh urutan keluaran, berdasarkan maklumat yang tersedia tentang saiz memori automaton dan tempoh urutan input.
Sangat penting ialah pembangunan kaedah untuk meminimumkan ingatan mesin keadaan terhingga dan mengkaji tingkah laku mereka dalam persekitaran rawak.
Dalam teori automata abstrak, masalah sintesis adalah seperti berikut.Dari segi beberapa bahasa yang diformalkan dengan jelas, syarat ditulis untuk tingkah laku automaton yang direka (untuk acara yang diwakili dalam automaton). Dalam kes ini, adalah perlu untuk membangunkan kaedah yang mengikut setiap syarat bertulis:
1) ketahui sama ada wujud mesin keadaan sedemikian yang maklumat yang diubah olehnya memenuhi syarat ini;
2) jika ya, maka fungsi peralihan mesin keadaan terhingga itu dibina atau saiz ingatannya dianggarkan.
Penyelesaian tugas sintesis dalam rumusan sedemikian mengandaikan penciptaan awal bahasa yang mudah untuk merekodkan keadaan operasi automaton dengan algoritma yang mudah untuk peralihan daripada rakaman kepada fungsi transitif.
Dalam teori struktur automata, masalah sintesis terdiri daripada membina rantaian unsur jenis tertentu yang merealisasikan automata terhingga yang diberikan oleh fungsi peralihannya. Dalam kes ini, mereka biasanya menyatakan beberapa kriteria optimum (contohnya, bilangan minimum elemen) dan berusaha untuk mendapatkan skema optimum.
Seperti yang ternyata kemudian, ini bermakna bahawa beberapa kaedah dan konsep yang dibangunkan sebelum ini berhubung dengan litar hubungan geganti boleh digunakan untuk litar jenis lain.
Sehubungan dengan perkembangan teknologi elektronik, yang paling meluas adalah skim daripada elemen berfungsi (rangkaian logik). Kes khas rangkaian logik ialah rangkaian saraf abstrak, yang unsur-unsurnya dipanggil neuron.
Banyak kaedah sintesis telah dibangunkan, bergantung pada jenis litar dan transformasi maklumat yang dimaksudkan (Sintesis peranti geganti).
Lihat -Pengurangan litar gabungan, peta Carnot, sintesis litar
Mesin keadaan terhingga — model matematik sistem kawalan dengan saiz ingatan tetap (tidak mampu meningkat semasa operasi).
Konsep mesin keadaan terhingga ialah abstraksi matematik yang mencirikan ciri umum set sistem kawalan (contohnya, peranti geganti berbilang gelung). Semua sistem sedemikian mempunyai ciri-ciri biasa yang wajar diterima sebagai takrifan automaton terhingga.
Setiap automaton yang lengkap mempunyai pintu masuk yang terdedah kepada pengaruh luaran dan unsur dalaman. Untuk kedua-dua elemen input dan dalaman, terdapat bilangan tetap keadaan diskret yang boleh diambil oleh mereka.
Perubahan dalam keadaan input dan elemen dalaman berlaku pada momen diskret dalam masa, selang antara yang dipanggil ticks. Keadaan dalaman (keadaan dalaman) pada penghujung pita ditentukan sepenuhnya oleh keadaan dalaman dan keadaan input pada permulaan pita.
Semua takrifan lain bagi automaton terhingga boleh dikurangkan kepada ciri ini, khususnya takrifan yang menganggap bahawa automaton terhingga mempunyai output yang bergantung pada keadaan dalaman automaton pada masa tertentu.
Dari segi ciri sedemikian, sifat input dan keadaan dalamannya tidak relevan dengan perihalan automaton yang lengkap. Daripada input dan keadaan, anda hanya boleh melihat nombor mereka dalam penomboran rawak.
Mesin keadaan akan ditetapkan jika pergantungan nombor keadaan dalamannya pada nombor keadaan dalaman sebelumnya dan nombor keadaan input sebelumnya ditentukan. Tugasan sedemikian boleh dalam bentuk jadual akhir.
Satu lagi cara biasa untuk menentukan automaton lengkap ialah pembinaan apa yang dipanggil gambar rajah peralihan. Keadaan input sering dipanggil hanya input, dan keadaan dalaman hanyalah keadaan.
Mesin keadaan terhingga boleh menjadi model kedua-dua peranti teknikal dan beberapa sistem biologi. Automata jenis pertama adalah, sebagai contoh, peranti geganti dan pelbagai komputer elektronik, termasuk. pengawal logik boleh atur cara.
Dalam kes peranti geganti, peranan keadaan input dimainkan oleh gabungan keadaan elemen sensitif peranti geganti (setiap gabungan keadaan tersebut ialah «keadaan kompleks», dicirikan oleh petunjuk semua elemen sensitif bagi diskret ini menyatakan bahawa mereka ada dalam masa tertentu). Begitu juga, gabungan keadaan elemen perantaraan peranti geganti bertindak sebagai keadaan dalaman.
Pengawal logik boleh atur cara (PLC) ialah contoh peranti tindakan geganti yang boleh dipanggil mesin keadaan berdiri sendiri.
Malah, apabila program telah dimasukkan ke dalam PLC dan pengawal telah mula mengira, ia tidak terdedah kepada pengaruh luar dan setiap keadaan berikutnya ditentukan sepenuhnya oleh keadaan sebelumnya. Kita boleh menganggap bahawa input mempunyai keadaan yang sama dalam setiap kitaran jam.
Sebaliknya, mana-mana mesin keadaan terhingga yang mempunyai satu-satunya keadaan input yang mungkin secara semula jadi dipanggil autonomi, kerana dalam kes ini persekitaran luaran tidak membawa maklumat yang mengawal kelakuannya.
Lihat juga:
Penggunaan sistem mikropemproses dalam kejuruteraan elektrik pada contoh penggunaan PLC