Teori Automata

Teori Automata- bagian dari matematika diskrit, mempelajari automata abstrak - komputer yang disajikan dalam bentuk model matematika - dan masalah yang dapat mereka pecahkan.

Teori automata paling erat hubungannya dengan teori algoritma: robot mengubah informasi diskrit dalam langkah-langkah menjadi momen waktu diskrit dan membentuk hasil dalam langkah-langkah dari algoritma yang diberikan.

Terminologi

Simbol- setiap blok data atom yang dapat berpengaruh pada mesin. Paling sering, simbol adalah huruf dalam bahasa yang sama, tetapi bisa juga, misalnya, elemen grafis dari diagram.

• Kata- serangkaian karakter yang dibuat melalui penggabungan (koneksi).
• Alfabet- satu set terbatas karakter yang berbeda (banyak karakter)
• Bahasa- kumpulan kata yang dibentuk oleh simbol alfabet yang diberikan. Mungkin terbatas atau tidak terbatas.

Mesin Mesin- urutan (tupel) dari lima elemen , di mana: Kata Automaton membaca string terakhir dari karakter a 1 ,a 2 ,…., a n , di mana a i , dan disebut kata. Himpunan semua kata ditulis sebagai *. Kata yang Diterima Sebuah kata w * diterima oleh robot jika q n F.

Bahasanya disebut L membaca (diterima) oleh otomat M jika terdiri dari kata-kata w berdasarkan alfabet sedemikian rupa sehingga jika kata-kata ini dimasukkan ke dalam M, pada akhir pemrosesan ia datang ke salah satu negara penerima F:

Biasanya, otomat bertransisi dari keadaan ke keadaan menggunakan fungsi transisi, sambil membaca satu karakter dari input. Ada juga automata yang bisa bertransisi ke keadaan baru tanpa membaca karakter. Fungsi lompat tanpa membaca karakter disebut -transisi(transisi epsilon).

Aplikasi

Dalam praktiknya, teori automata digunakan dalam pengembangan lexer dan parser untuk bahasa formal (termasuk bahasa pemrograman), serta dalam konstruksi compiler dan pengembangan bahasa pemrograman itu sendiri.

Aplikasi penting lainnya dari teori automata adalah penentuan secara matematis yang ketat dari solvabilitas dan kompleksitas masalah.

Tugas khas

• Konstruksi dan minimalisasi automata- konstruksi otomat abstrak dari kelas tertentu yang memecahkan masalah tertentu (menerima bahasa tertentu), mungkin dengan minimalisasi berikutnya dalam hal jumlah status atau jumlah transisi.
• Sintesis automata- membangun sistem dari "automata dasar" yang diberikan, setara dengan robot yang diberikan. Robot seperti itu disebut struktural. Ini digunakan, misalnya, dalam sintesis sirkuit listrik digital pada basis elemen tertentu.

Lihat juga

literatur

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman Pengantar Teori Automata, Bahasa, dan Komputasi. - M .: Williams, 2002. - S. 528. - ISBN 0-201-44124-1
• Kasyanov V.N. Kuliah tentang teori bahasa formal, automata dan kompleksitas komputasi. - Novosibirsk: NSU, 1995. - C. 112.

Tautan

Yayasan Wikimedia. 2010 .

Lihat apa itu "Teori Automata" di kamus lain:

Teori Automata

Teori Automata- bagian dari sibernetika teoretis yang mempelajari model matematika (disebut automata atau mesin di sini) dari perangkat nyata atau mungkin yang memproses informasi diskrit dalam siklus diskrit. utama ... ... Kamus Ekonomi dan Matematika

teori automata- Cabang sibernetika teoretis yang mempelajari model matematika (disebut automata atau mesin di sini) dari perangkat nyata atau mungkin yang memproses informasi diskrit dalam siklus diskrit. Konsep utama dari teori ini ... ... Buku Pegangan Penerjemah Teknis

Ada., Jumlah sinonim: 1 tavt (1) Kamus Sinonim ASIS. V.N. Trishin. 2013 ... Kamus sinonim

teori automata- automat teorija status sebagai T sritis automatika atitikmenys: angl. teori automata vok. Automatentheorie, f rus. teori automata, pranc. theorie des automates, f … Automatikos terminų odynas

Istilah ini memiliki arti lain, lihat Diagram Negara. Diagram keadaan adalah grafik berarah untuk otomat berhingga, di mana simpul menunjukkan keadaan busur menunjukkan transisi antara dua keadaan Dalam praktiknya ... ... Wikipedia

Teori mesin dan mekanisme (TMM) adalah disiplin ilmu tentang metode umum penelitian, konstruksi, kinematika dan dinamika mekanisme dan mesin dan tentang dasar ilmiah dari desain mereka. Daftar isi 1 Sejarah perkembangan disiplin ilmu 2 Konsep dasar ... Wikipedia

TEORI- (1) sistem ide dan prinsip ilmiah yang merangkum pengalaman praktis, yang mencerminkan hukum dan peraturan alam objektif yang membentuk (lihat) atau bagian dari ilmu apa pun, serta seperangkat aturan di bidang segala jenis pengetahuan ... ... Ensiklopedia Politeknik Hebat

Teori Algoritma Kamus Ekonomi dan Matematika

Teori Algoritma- cabang matematika yang mempelajari sifat-sifat umum dari algoritma. Masalah membangun suatu algoritma dengan sifat-sifat tertentu disebut masalah algoritmik, unsolvability-nya berarti tidak adanya algoritma yang sesuai; jika… … Kamus Ekonomi dan Matematika

Buku

• Teori automata. Buku teks untuk studi sarjana dan pascasarjana, Kudryavtsev V.B. Buku teks berisi materi yang luas tentang teori automata. Ini memperkenalkan konsep robot, memberikan teori ...

verifikasi sistem proses yang berinteraksi;

Bahasa deskripsi untuk dokumen dan program berorientasi objek;

Optimalisasi program logika dll.

Hal ini dapat dinilai dari presentasi di seminar "Software 2000 ..." oleh para ilmuwan dan spesialis.

Doug Ross: "...80 atau bahkan 90% ilmu komputer (Computer Science) di masa depan akan didasarkan pada teori finite automata ..."

Herver Gallaire: "Saya tahu orang-orang Boeing yang mengerjakan sistem stabilisasi pesawat menggunakan teori automata murni. Sulit membayangkan apa yang telah mereka lakukan dengan teori ini."

Brian Randell: "Banyak teori automata telah berhasil digunakan dalam program sistem dan filter teks di UNIX OS. Hal ini memungkinkan banyak orang untuk bekerja pada tingkat tinggi dan mengembangkan program yang sangat efektif."

1.1. Konsep dasar dan definisi.

Konverter informasi paling sederhana (Gbr. 1.1, a) memetakan sekumpulan elemen informasi tertentu yang datang ke input ke himpunan tertentu pada output Y. Jika himpunan X dan Y berhingga dan diskrit, yaitu transformasi dilakukan pada waktu diskrit, maka pengubah informasi semacam itu disebut pengubah hingga. Tetapkan elemen X dan Y dalam hal ini dikodekan sebelumnya dengan kode biner dan transformasi dari satu set ke set lainnya dibangun.

Hasil transformasi seringkali tidak hanya bergantung pada informasi apa yang muncul pada input saat ini, tetapi juga pada apa yang terjadi sebelumnya, yaitu pada sejarah transformasi. Misalnya, masukan yang sama - permintaan maaf dari tetangga setelah dia menginjak kaki Anda di bus yang penuh sesak - akan membuat Anda bereaksi untuk pertama kali dan reaksi yang sama sekali berbeda untuk kelima kalinya.

Beras. 1.1.

Jadi, ada trafo informasi (IT) yang lebih kompleks, yang responsnya tidak hanya bergantung pada sinyal input saat ini, tetapi juga pada apa yang terjadi sebelumnya, pada riwayat input. PI semacam itu disebut automata (sirkuit memori). Dalam hal ini, seseorang berbicara tentang transformasi informasi secara otomatis (Gbr. 1.1, b). Otomaton dapat bereaksi secara berbeda terhadap sinyal input yang sama, tergantung pada keadaannya. Otomaton mengubah statusnya dengan setiap sinyal input.

Mari kita lihat beberapa contoh.

Contoh 1 1 Karpov Yu.G. Teori automata-St. Petersburg: St. Petersburg, 2003. Sebuah robot yang menggambarkan perilaku seorang ayah yang "pintar".

Mari kita uraikan perilaku seorang ayah yang anaknya pergi ke sekolah dan membawa deuces dan fives. Sang ayah tidak ingin mengambil ikat pinggang setiap saat, segera setelah putranya mendapat deuce, dan memilih taktik pengasuhan yang lebih halus. Kami mendefinisikan otomat seperti itu dengan grafik di mana simpul sesuai dengan keadaan, dan busur dari keadaan s ke keadaan q, berlabel x/y, digambar ketika otomat dari keadaan s di bawah pengaruh sinyal input x diteruskan ke keadaan q dengan reaksi keluaran y. Grafik otomat yang mensimulasikan perilaku cerdas orang tua ditunjukkan pada Gambar. 1.2. Robot ini memiliki empat status , dua sinyal input - evaluasi dan sinyal output , yang akan kita tafsirkan sebagai tindakan induk sebagai berikut:

Ambil ikat pinggang;

memarahi anak;

Tenangkan anak itu;

Harapan;

bersuka cita;

Bersuka cita.

Beras. 1.2.

Seorang putra yang menerima nilai yang sama - seorang deuce, mengharapkan reaksi yang sama sekali berbeda dari ayahnya di rumah, tergantung pada latar belakang studinya. Misalnya, setelah deuce ketiga dalam sejarah, anak laki-laki akan disambut dengan ikat pinggang, dan dalam sejarah mereka akan diyakinkan, dll.

Mesin negara dapat diimplementasikan baik dalam perangkat lunak maupun perangkat keras. Implementasi perangkat lunak bisa dilakukan di mana saja bahasa tingkat tinggi cara yang berbeda. Gambar 1.3 menunjukkan diagram blok program yang mengimplementasikan perilaku otomat dari contoh 1. Sangat mudah untuk melihat bahwa topologi diagram blok program mengulangi topologi grafik transisi otomat. Setiap keadaan diasosiasikan dengan operasi NEXT , yang menjalankan fungsi menunggu acara berikutnya dari kedatangan sinyal input baru dan membacanya ke dalam beberapa buffer standar x , serta analisis selanjutnya dari jenis sinyal apa itu. Bergantung pada sinyal apa yang masuk ke input, fungsi ini atau itu dijalankan dan transisi ke status baru terjadi.

Beras. 1.3.

Implementasi perangkat keras dari otomat akan dipertimbangkan di bagian kedua dari bagian ini.

Contoh 2. "Mahasiswa"

Robot , model yang ditunjukkan pada Gambar. 1.4, menggambarkan perilaku siswa dan guru.

Beras. 1.4.

menyatakan;

- sinyal masukan: "n", "2" dan "5".

Reaksi keluaran:

Contoh 3 1 . Jam elektronik (Gbr. 1.5).

Jam elektronik dengan berbagai fungsi adalah salah satu perangkat elektronik yang paling banyak digunakan dalam kehidupan sehari-hari, yang kontrolnya dibangun berdasarkan model otomat terbatas. Mereka biasanya menunjukkan: waktu, tanggal; mereka memiliki fungsi seperti "mengatur waktu dan tanggal", "stopwatch", "jam alarm", dll. disederhanakan skema struktural jam elektronik ditunjukkan pada Gambar.1.5

Beras. 1.5.

Register menampilkan waktu, atau tanggal, atau stopwatch, tergantung pada "Kontrol". Perangkat kontrol dibangun atas dasar model otomat terbatas. Mesin status merespons penekanan tombol "a" pada badan dengan beralih ke status "Atur menit", di mana peristiwa menekan tombol "b" akan menyebabkan angka bertambah.

Mesin komputasi disajikan dalam bentuk model matematika - dan tugas yang dapat mereka selesaikan.

Teori automata paling erat hubungannya dengan teori algoritma: robot mengubah informasi diskrit dalam langkah-langkah menjadi momen waktu diskrit dan menghasilkan hasil dalam langkah-langkah dari algoritma yang diberikan.

YouTube ensiklopedis

1 / 3

Pelajaran 12. Dasar-dasar teori automata. Logika matematika. Pelajaran ilmu komputer

Cara menguasai dunia dengan mempelajari hanya satu model sederhana!

Pelajaran 15. Memecahkan masalah terapan dalam teori automata. Logika matematika. Pelajaran ilmu komputer

Subtitle

Terminologi

Simbol- setiap blok data atom yang dapat berpengaruh pada mesin. Paling sering, simbol adalah huruf dalam bahasa yang sama, tetapi bisa juga, misalnya, elemen grafis dari diagram.

• Kata- serangkaian karakter yang dibuat melalui penggabungan (koneksi).
• Alfabet- satu set terbatas karakter yang berbeda (banyak karakter)
• Bahasa- kumpulan kata yang dibentuk oleh simbol alfabet yang diberikan. Mungkin terbatas atau tidak terbatas.

Automata Deterministik finite automaton (DFA)- urutan (tupel) dari lima elemen (Q , , , S 0 , F) (\displaystyle (Q,\Sigma ,\delta ,S_(0),F)), di mana: Mesin keadaan hingga (NFA) non-deterministik- urutan (tupel) dari lima elemen (Q , , , S , F) (\displaystyle (Q,\Sigma ,\Delta ,S,F)), di mana: Word Automaton membaca string terakhir karakter a 1 ,a 2 ,…., a n , di mana a i , yang disebut kata masukan. Himpunan semua kata ditulis sebagai *. Kata yang Diterima Sebuah kata w * diterima oleh robot jika q n F.

Bahasanya disebut L membaca (diterima) otomat M jika terdiri dari kata-kata w berdasarkan alfabet (\displaystyle \Sigma ) sedemikian rupa sehingga jika kata-kata ini dimasukkan ke dalam M, pada akhir pemrosesan, kata-kata ini akan menjadi salah satu status penerima F:

L = ( w | ^ (S 0 , w) F ) (\displaystyle L=\(w\in \Sigma ^(\star )|(\hat (\delta ))(S_(0) ,w)\di F\))

Biasanya, otomat bergerak dari satu keadaan ke keadaan lain menggunakan fungsi transisi (\displaystyle \delta ), saat membaca satu karakter dari input. Ada automata yang dapat bertransisi ke keadaan baru tanpa membaca karakter. Fungsi lompat tanpa membaca karakter disebut (\displaystyle \epsilon )-transisi(transisi epsilon) Kompleksitas tugas.

Tugas khas

• Konstruksi dan minimalisasi automata- konstruksi otomat abstrak dari kelas tertentu yang memecahkan masalah tertentu (menerima bahasa tertentu), mungkin dengan minimalisasi berikutnya dalam hal jumlah status atau jumlah transisi.
• Sintesis automata- membangun sistem "automata dasar" yang diberikan, setara dengan robot yang diberikan. Robot seperti itu disebut struktural. Ini digunakan, misalnya, dalam sintesis sirkuit listrik digital pada basis elemen tertentu.

teori automata
Teori Automata- bagian dari matematika diskrit yang mempelajari automata abstrak - komputer yang disajikan dalam bentuk model matematika - dan tugas yang dapat mereka selesaikan.

Teori automata paling erat hubungannya dengan teori algoritma: robot mengubah informasi diskrit dalam langkah-langkah menjadi momen waktu diskrit dan menghasilkan hasil dalam langkah-langkah dari algoritma yang diberikan.

• 1 Terminologi
• 2 Aplikasi
  • 2.1 Tugas umum
• 3 Lihat juga
• 4 Sastra
• 5 Tautan

Terminologi

Simbol- setiap blok data atom yang dapat berpengaruh pada mesin. Paling sering, simbol adalah huruf dalam bahasa yang sama, tetapi bisa juga, misalnya, elemen grafis dari diagram.

• Kata- serangkaian karakter yang dibuat melalui penggabungan (koneksi).
• Alfabet- satu set terbatas karakter yang berbeda (banyak karakter)
• Bahasa- kumpulan kata yang dibentuk oleh simbol alfabet yang diberikan. Mungkin terbatas atau tidak terbatas.

Automata

Automata dapat bersifat deterministik atau non-deterministik.

Deterministik Finite Automaton (DFA)

• adalah fungsi transisi sehingga
• - keadaan awal

Automaton Hingga Nondeterministik (NFA)- urutan (tupel) dari lima elemen, di mana:

• - set status otomat
• - alfabet bahasa yang dimengerti robot
• adalah hubungan transisi, di mana adalah kata kosong. Artinya, NFA dapat melompat dari keadaan q ke keadaan p, tidak seperti DFA, melalui kata kosong, dan juga berpindah dari q ke beberapa keadaan (yang lagi-lagi tidak mungkin di DFA)
• - set status awal
• - set status akhir.

Kata Automaton membaca string berhingga karakter a1,a2,…., an , di mana ai , yang disebut kata input. Himpunan semua kata ditulis sebagai *. Kata yang Diterima Sebuah kata w * diterima oleh otomat jika qn F.

Suatu bahasa L dikatakan terbaca (diterima) oleh otomat M jika terdiri dari kata-kata w berdasarkan abjad sedemikian rupa sehingga jika kata-kata ini dimasukkan ke dalam M, pada akhir pemrosesan datang ke salah satu keadaan penerima F:

Biasanya, otomat bertransisi dari keadaan ke keadaan menggunakan fungsi transisi, sambil membaca satu karakter dari input. Ada automata yang dapat bertransisi ke keadaan baru tanpa membaca karakter. Fungsi transisi tanpa membaca karakter disebut -jump (epsilon-jump).

Aplikasi

Teori automata mendasari semua teknologi digital dan perangkat lunak, misalnya, komputer adalah kasus khusus dari implementasi praktis mesin negara yang terbatas.

Bagian dari perangkat matematika teori automata langsung digunakan dalam pengembangan lexer dan parser untuk bahasa formal, termasuk bahasa pemrograman, serta dalam konstruksi kompiler dan pengembangan bahasa pemrograman itu sendiri.

Aplikasi penting lainnya dari teori automata adalah penentuan secara matematis yang ketat dari solvabilitas dan kompleksitas masalah.

Tugas khas

• Konstruksi dan minimalisasi automata- konstruksi otomat abstrak dari kelas tertentu yang memecahkan masalah tertentu (menerima bahasa tertentu), mungkin dengan minimalisasi berikutnya dalam hal jumlah status atau jumlah transisi.
• Sintesis automata- membangun sistem "automata dasar" yang diberikan, setara dengan robot yang diberikan. Otomat semacam itu disebut struktural. Ini digunakan, misalnya, dalam sintesis sirkuit listrik digital pada basis elemen tertentu.

Lihat juga

• Pompa Lemma
• Otomat abstrak
• Permainan "Hidup"
• Bentuk minimal otomat
• Teorema Shannon-Lupanov

literatur

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Pengantar Teori Automata, Bahasa, dan Komputasi = Pengantar Teori Automata, Bahasa, dan Komputasi. - M.: Williams, 2002. - S. 528. - ISBN 0-201-44124-1.
• Kasyanov VN Kuliah tentang teori bahasa formal, automata dan kompleksitas komputasi. - Novosibirsk: NSU, 1995. - C. 112.

Tautan

• Penerapan teori automata

teori automata