ZA 79 Teori senapan mesin: pedoman pelatihan praktek untuk spesialisasi 230101 / T.Z. Aralbaev,<...>Pedoman ini membahas isu-isu berikut: metode presentasi logis fungsi ( JIKA); transformasi aljabar JIKA; metode minimalisasi Quine dan McClassky, menggunakan peta Carnot; formulir tugas terakhir senapan mesin; sintesis kombinasional skema di dasar “ DAN-TIDAK” (“ATAU-TIDAK") pada logis elemen seri K155 dan K561.<...>Instruksi metodis dimaksudkan untuk mengatur kelas praktik pada mata kuliah “ Teori senapan mesin” untuk siswa tahun ke-2 pada spesialisasi 230101 “Komputer, kompleks, sistem dan jaringan.”<...>Meminimalkan fungsi logis di seluruh peta Carnot ……………………….. <...>41 3 Pendahuluan Pedoman ini berisi materi untuk menyelenggarakan kelas praktik pada salah satu bagian utama disiplin ilmu “Teori” senapan mesin” – “Dasar Logis digital senapan mesin”. <...>1.1 Bentuk tabel representasi LF Fungsi logika paling jelas diwakili oleh tabel kebenaran(TI) dan kartu Carnot. <...> Meja kebenaran- Ini meja, di mana setiap himpunan nilai argumen biner xi (i = 1, n) dikaitkan dengan nilai fungsi Y = f (x1, x2,..., xi,..., xn) pada set ini. <...>Peta Carnaugh adalah tabel berbentuk persegi panjang yang berisi n 2 sel, dengan masing-masing sel terletak pada perpotongan baris ke-i dan kolom ke-j, ai dan aj merupakan elemen penyusunnya. biner perekrutan n – LF lokal.<...>1) setiap pasangan sel yang berdekatan secara vertikal atau horizontal, serta setiap pasangan sel yang terletak secara simetris pada peta secara vertikal atau horizontal, bersesuaian biner set, berbeda nilai hanya pada satu variabel (yaitu berbeda satu digit);<...>2) di sel kartu Carnot menunjukkan nilai fungsi pada himpunan yang sesuai;<...>3) kumpulan argumen biner yang menandai baris, serta kumpulan argumen biner yang menandai kolom<...>

Teori_automata.pdf

UDC 004.3(076.5) BBK 32.97ya73 A 79 Reviewer: Doktor Ilmu Teknik, Profesor A.M. Pishchukhin Aralbaev, T.Z A 79 Teori automata: instruksi metodologis untuk latihan praktis untuk spesialisasi 230101 / T.Z. Aralbaev, I.V. Zhukalina. - Orenburg: Lembaga Pendidikan Negeri OSU, 2009. – 41 hal. Pedoman tersebut membahas isu-isu berikut: metode merepresentasikan fungsi logis (LF); transformasi aljabar LF; Metode minimalisasi Quine dan McClassky menggunakan peta Karnaugh; formulir untuk menentukan mesin negara yang terbatas; sintesis rangkaian kombinasional berdasarkan “AND-NOT” (“OR-NOT”) pada elemen logika seri K155 dan K561. Pedoman ini dimaksudkan untuk menyelenggarakan kelas praktik pada mata kuliah “Teori Automata” untuk siswa tahun ke-2 pada spesialisasi 230101 “Komputer, kompleks, sistem dan jaringan.” BBK 32.97ya73 © Aralbaev T.Z., 2009 © Zhukalina I.V., 2009 © Lembaga Pendidikan Negeri OSU, 2009 2

Halaman 2

Daftar Isi Pendahuluan................................................ ............................................... ......... ...................4 1 Pelajaran Praktek No.1. Metode merepresentasikan fungsi logika………………………….… 5 1.1 Bentuk tabel penyajian LF…………………………………….5 1.2 Bentuk analisis penyajian LF …………………………………….8 2 Pelajaran Praktek No.2. Transformasi Aljabar Rumus Fungsi Logika…….…..12 2.1 Hukum Aljabar Boolean………………………………………………………12 2.2 Aksioma dan Teorema Aljabar Boolean ……………………………………………..12 3 Pelajaran Praktek No.3. Metode minimalisasi Quine dan McClassky…….……………………….15 3.1 Menemukan semua implikan prima……………………………..15 3.2 Konstruksi tabel cakupan Quine matriks……………………………16 3.3 Mencari cakupan minimum suatu fungsi…………………………………….16 3.4 Memperoleh bentuk minimum LF……… … …………16 4 Pelajaran Praktek No.4. Minimalkan fungsi logika menggunakan peta Karnaugh…………………..20 4.1 Konstruksi DNF minimal………………………………………...21 4.2 Konstruksi CNF minimal… ………………………………………...22 4.3 Meminimalkan LF yang tidak terdefinisi secara lengkap……………………………..23 5 Pelajaran praktis No. 5 Bentuk untuk menentukan terbatas mesin negara…………………………………….……..25 6 Pelajaran Praktek No. 6 Sintesis rangkaian kombinasional berdasarkan “AND-NOT” (“OR-NOT”)………. ………30 7 Pelajaran Praktek No.7. Sintesis rangkaian kombinasional berdasarkan elemen logika seri K155 dan K561………………………………………………………………………………………………….… …35 Daftar sumber yang digunakan.... ........................................ ................ ...............40 Lampiran……………………………………… …………………………………...41 3

Halaman 3

Pendahuluan Pedoman ini berisi materi untuk melakukan kelas praktik pada salah satu bagian utama dari disiplin ilmu “Teori Automata” - “Landasan Logis Automata Digital”. Tujuan dari kelas ini adalah untuk mengkonsolidasikan pengetahuan secara praktis tentang bentuk representasi dan metode untuk mengubah fungsi logika, serta metodologi untuk mensintesis rangkaian kombinasional. Setiap pelajaran praktek mencakup pernyataan tujuan pelajaran, materi teori singkat tentang topik, contoh-contoh tipikal, soal tes dan latihan untuk kerja mandiri. Sebelum melaksanakan pembelajaran, siswa harus memahami tujuannya dan menjawab pertanyaan kontrol. Untuk persiapan mandiri kelas, siswa disarankan untuk membaca literatur yang disajikan dalam daftar sumber yang digunakan. Selama pelajaran, contoh dianalisis dan latihan dilakukan berdasarkan pilihan. Pengendalian pengetahuan dilakukan berdasarkan hasil menjawab soal tes dan menyelesaikan latihan. 4

Halaman 4

1 Pelajaran Praktek No.1. Bentuk representasi fungsi logika Ada beberapa bentuk representasi fungsi logika (LF) yang digunakan pada berbagai tahapan perancangan rangkaian kombinasional, khususnya: verbal, tabular, analitis, geometri, kubik. Tujuan dari pembelajaran praktik ini adalah mempelajari bentuk tabel dan analitis dari representasi LF serta algoritma transisi dari deskripsi tabel LF ke deskripsi analitis. 1.1 Bentuk tabel representasi LF Fungsi logika paling jelas direpresentasikan melalui tabel kebenaran (TI) dan peta Karnaugh. Tabel kebenaran adalah tabel yang setiap himpunan nilai argumen biner xi (i = 1, n) dikaitkan dengan nilai fungsi Y = f (x1, x2,..., xi,..., xn) pada set ini. Tabel 1.1 menunjukkan fungsi TI untuk tiga argumen sebagai contoh. Fungsi Y mengambil nilai 1 atau 0 pada setiap set. Jika nilai fungsi tidak ditentukan, maka tanda hubung ditempatkan pada posisi TI yang sesuai. Tabel 1.1 – Tabel kebenaran fungsi logika N Х1 Х2 Х3 Y 0 0 0 0 1 1 0 0 1 1 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 1 0 1 7 1 1 1 1 Terkadang bentuk daftar representasi TI digunakan, yang menyediakan daftar himpunan satu dan nol. Jadi, fungsi yang diperhatikan dalam contoh dalam bentuk daftar dapat direpresentasikan sebagai: Y = F Х Х Х) = ∨ (0, 1, 3, 6, 7) Y = ∧ (2, 4, 5) (0 1, 2 , 3 1 5

Informasi awal tentang automata Mealy dan Moore abstrak diberikan. Diberikan cara yang mungkin representasi automata: teori himpunan, grafik, tabel dan matriks, konsep respon automata dan automata setara. Metode untuk transformasi automata yang saling setara disajikan. Diberikan informasi umum tentang pengendalian mikroprogram, konsep instruksi mikro, operasi mikro, program mikro, metode penyajian mikroprogram dalam bentuk diagram grafik algoritma (GDA), rumus terjemahan, matriks dan diagram logika algoritma. Metode penandaan GSA dan aturan untuk membuat automata Mealy dan Moore menggunakannya diberikan. Konsep robot gabungan dan cara merepresentasikannya diberikan. Metode sintesis kanonik automata struktural dipertimbangkan. Contoh sintesis memori dari otomat struktural berdasarkan RS-, T- dan D-flip-flop diberikan.

Konsep dasar dan definisi.
Pengonversi informasi paling sederhana (Gbr. 1.1, a) menampilkan himpunan elemen informasi tertentu X yang tiba pada masukan ke himpunan tertentu pada keluaran Y. Jika himpunan X dan Y berhingga dan diskrit, maka transformasi dilakukan keluar pada saat-saat tertentu, maka informasi konverter tersebut disebut transformator akhir. Dalam hal ini, elemen himpunan X dan Y dikodekan sebelumnya dengan kode biner dan transformasi dari satu himpunan ke himpunan lainnya dibangun.

Hasil transformasi F: X → Y seringkali tidak hanya bergantung pada informasi apa yang ada di dalamnya saat ini muncul pada masukan, tetapi juga dari apa yang terjadi sebelumnya, yaitu dari prasejarah transformasi. Misalnya, masukan yang sama - permintaan maaf tetangga setelah dia menginjak kaki Anda di bus yang penuh sesak - akan menyebabkan Anda mendapat satu reaksi untuk pertama kalinya dan reaksi yang sangat berbeda untuk kelima kalinya.

Isi
Cetakan halaman sampul
Kuliah 1. Konsep dasar teori automata abstrak
Kuliah 2. Automata yang setara
Kuliah 3. Metode menjelaskan pengoperasian perangkat diskrit
Kuliah 4. Konstruksi automata abstrak menggunakan diagram grafik mikroprogram
Kuliah 5. Sintesis robot struktural
Kuliah 6. Memori robot struktural
Kuliah 7. Contoh sintesis otomat struktural menggunakan sandal jepit
Kuliah 8. Metode grafis sintesis otomat struktural pada pemicu.

Unduhan gratis buku elektronik dalam format yang nyaman, tonton dan baca:
Unduh buku Pengantar teori automata, Knyazkov V.S., Volchenskaya T.V., 2016 - fileskachat.com, unduh cepat dan gratis.

Unduh pdf
Anda dapat membeli buku ini di bawah harga terbaik dengan diskon dengan pengiriman ke seluruh Rusia.

Catatan kuliah singkat yang sangat bagus tentang subjek "teori automata" dalam file Pdf.

Sintesis automata digital untuk implementasi algoritma aritmatika biner

• Informasi umum tentang mesin digital. model Glushkov. Sintesis mesin yang beroperasi
• Contoh sintesis robot operasional untuk melakukan perkalian tidak langsung dari bilangan tak bertanda
• Jenis mesin kontrol. Struktur automata Mealy dan Moore.
• Contoh sintesis otomat kontrol dengan hard logic (UAL) untuk algoritma perkalian bilangan tak bertanda dalam kode langsung

• Jelaskan model konverter Glushkov diskrit.
• Apa tujuan dari Operational Automaton (OA)?
• Sebutkan tahapan sintesis OA dari jenis struktur kanonik prosedural.
• Melakukan sintesis OA untuk melakukan perkalian (gunakan yang disederhanakan
• algoritma untuk perkalian tidak langsung dari bilangan yang tidak ditandatangani).
• Berikan contoh perkalian bilangan dengan menggunakan algoritma perkalian tidak langsung.
• Jelaskan pilihan utama (skema) untuk perkalian tidak langsung.
• Buatlah diagram waktu OA untuk perkalian. Jelaskan itu.
• Sintesis algoritma untuk melakukan operasi aritmatika berdasarkan varian.
• Sintesis rangkaian OA sesuai dengan algoritma Anda.
• Apa tujuan dari Kontrol Otomatis (CA)?
• Peran informasi dan sinyal kontrol.
• Jenis UA.
• Sebutkan tahapan sintesis UA dengan logika kaku.
• Jelaskan dasar sandal jepit sebagai mesin keadaan dasar.
• Apa saja ciri-ciri sintesis UAZL pada jenis yang berbeda pemicu?
• Berikan diagram struktur automata Mealy dan Moore. Apa perbedaan mereka?
• Jelaskan model automata Mealy dan Moore yang abstrak.
• Bentuk deskripsi mesin keadaan terbatas abstrak apa yang Anda ketahui?
• Buatlah tabel transisi/output dan grafik automata sesuai skema
• algoritma.
• Sintesis UA untuk mengimplementasikan algoritma perkalian (gunakan
• algoritma yang disederhanakan untuk perkalian tidak langsung dari bilangan tak bertanda) sebagai
• Mili/Moore otomatis.
• Buatlah diagram waktu OA untuk perkalian. Jelaskan itu.
• Sintesis skema UASL untuk algoritme Anda sesuai dengan opsi.

Menggunakan ekspresi reguler (RE). Implementasi perangkat lunak automata

• Konsep ekspresi reguler dan pengenal automata
• Pengenalan singkat tentang ekspresi reguler (RE). Dialek RV.
• Penerapan RT dalam pemrograman
• Contoh pembentukan ekspresi reguler
• Contoh bekerja dengan ekspresi reguler untuk mengontrol alamat IP yang dimasukkan pengguna.
• Sintesis robot deterministik untuk pengenalan bahasa yang ditentukan oleh ekspresi reguler dan implementasi perangkat lunaknya.
• Konversi RF menjadi NKA dengan ε – transisi
• Konversi NKA dengan transisi ε menjadi NKA tanpa transisi ε
• Memperoleh DKA dari NKA tanpa transisi ε
• Minimalkan DFA
• Menerima RF dari pesawat luar angkasa
• Implementasi perangkat lunak pengenal DFA

Pertanyaan dari bagian pertama untuk pengendalian diri:

• Apa itu ekspresi reguler?
• Di mana RV digunakan?
• Metode apa yang Anda ketahui untuk menugaskan RV?
• Automata apa yang digunakan untuk mengenali bahasa yang ditentukan oleh RT?
• Apa itu NKA? DKA?
• Bagaimana cara membuat pengenal pesawat ruang angkasa menggunakan RV?
• Bagaimana cara membangun pengenal DKA menggunakan RV?
• Bagaimana cara menghilangkan transisi elektronik di pesawat ruang angkasa?
• Bagaimana cara meminimalkan CA - pengenal?
• Bagaimana RT digunakan di lingkungan VS?
• Bagaimana RT didukung di .NET Framework?
• Jelaskan rantai yang diberikan menggunakan RT.
• Rantai apa yang didefinisikan oleh RF ini (contoh, karakteristik).
• Strategi untuk menerapkan dukungan RT dalam sistem perangkat lunak.
• Cara menggunakan dukungan RT saat menulis program pengolah teks.
• Masalah pemrosesan teks apa yang dapat diselesaikan menggunakan RT?
• Daftarkan orang-orang yang Anda kenal sistem perangkat lunak, mendukung RV.

Kementerian Pendidikan Federasi Rusia Universitas Negeri Nizhny Novgorod dinamai menurut namanya. N.I. Lobachevsky

Fakultas Matematika Komputasi dan Sibernetika

Pengembangan pendidikan dan metodologi karya mandiri mahasiswa pada mata kuliah “Teori Algoritma dan Logika Matematika”

sambil mempelajari topik “Konsep mesin keadaan terbatas dan bahasa reguler. Operasi pada bahasa biasa"

Nizhny Novgorod 2000

Pengembangan metodologi ditujukan untuk karya mandiri mahasiswa spesialisasi “Informatika Terapan” pada materi topik “Konsep mesin keadaan terbatas dan bahasa reguler. Operasi pada bahasa reguler”, yang merupakan bagian dari kursus pelatihan “Teori Algoritma dan Logika Matematika”. Konsep bahasa formal dan operasi pada bahasa formal, termasuk operasi teori himpunan dasar, diperkenalkan. Konsep robot terbatas disajikan (dalam versi deterministik dan non-deterministik); bahasa reguler adalah kelas bahasa yang dikenali oleh mesin negara yang terbatas. Terlihat bahwa operasi, gabungan, perpotongan, penambahan, penggabungan, dan iterasi tidak keluar dari kelas bahasa reguler. Algoritma yang sesuai untuk sintesis mesin keadaan terbatas disajikan.

Disusun oleh:

guru Departemen Informatika dan Otomasi Penelitian Ilmiah Fakultas Matematika Komputasi dan Matematika UNN Associate Professor, Doktor Ilmu Teknik Kogan D.I. dan asisten Babkina T.S.

1. Konsep bahasa, contoh bahasa, operasi bahasa.

Alfabet adalah kumpulan simbol terbatas yang tidak kosong dan berubah-ubah; karakter alfabet sembarang disebut huruf. Sebagai contoh, kami akan menunjukkan alfabet Rusia (dengan atau tanpa penyertaan tanda baca), alfabet Latin, kombinasi alfabet ini, dan banyak digit sistem bilangan desimal atau biner. Secara umum kita mendefinisikan alfabet sebagai himpunan A = (a 1, a 2, ..., an); di antara huruf-huruf alfabet A mungkin juga terdapat karakter spasi khusus (huruf kosong); karakter ini biasanya dilambangkan dengan e (singkatan dari bahasa Inggris "empty" - kosong).

Sebuah kata dalam alfabet A adalah rangkaian huruf-hurufnya yang terbatas dan berubah-ubah; huruf yang sama dapat muncul beberapa kali dalam urutan ini. Panjang kata α (notasi l(α)) adalah banyaknya huruf pada kata tersebut. Simbol khusus λ akan menunjukkan satu-satunya kata yang panjangnya nol (kata kosong); seseorang harus membedakan antara kata kosong dan kata e, yang terdiri dari satu huruf kosong; panjang kata e (spasi) sama dengan satu. Dalam alfabet A = (a 1, a 2, ..., an) Anda dapat menulis n l kata-kata berbeda yang panjangnya l, di mana l = 0, 1, 2, .... Himpunan semua kata dalam alfabet A akan dilambangkan dengan A*. Mari kita perhatikan secara khusus bahwa kumpulan A* juga menyertakan kata kosong. Kardinalitas himpunan semua kata dalam alfabet A dapat dihitung.

Jika α dan β adalah dua kata arbitrer dalam alfabet A, maka αβ adalah hasil penugasan kata β ke kata α di sebelah kanan. Untuk kata apa pun α dan β kami berasumsi demikian

αλ= λα= α, αλβ= αβ.

Bahasa dalam alfabet A adalah himpunan bagian kata L dari A*. Kita menyebut suatu bahasa L terbatas jika bahasa tersebut berisi kumpulan kata yang terbatas; suatu bahasa L tidak terhingga jika mengandung jumlah kata yang tidak terhingga. Totalitas semua kata dalam bahasa Rusia dan semua kata dalam bahasa Inggris adalah contoh bahasa yang terbatas. Banyak catatan dari semua orang bilangan prima dalam sistem bilangan desimal atau biner adalah bahasa tak terbatas. Himpunan semua bahasa alfabet A mempunyai kardinalitas kontinum.

Suatu bahasa L yang berhuruf A disebut universal jika L=A*. Bahasa L

kita menyebutnya kosong jika himpunan L kosong (L =).

Misalkan L 1 dan L 2 adalah bahasa dalam alfabet A. Melalui L 1 L 2 dan L 1 ∩ L 2 kita akan melakukannya

masing-masing menunjukkan kesatuan dan perpotongan bahasa-bahasa ini. Kata α termasuk dalam gabungan dua bahasa jika setidaknya milik salah satu bahasa tersebut; kata α termasuk persilangan dua bahasa jika termasuk dalam bahasa yang satu dan bahasa yang lain. Misalkan L adalah bahasa dalam alfabet A; Misalkan L c menunjukkan komplemen dari bahasa ini. Bahasa L c dibentuk oleh kata-kata berhuruf A yang bukan bagian dari bahasa L: L c = A *\L. Operasi penyatuan, perpotongan, dan penjumlahan merupakan operasi teori himpunan dasar.

Misalkan L 1 dan L 2 adalah bahasa dalam alfabet A. Kami akan dilambangkan dengan L 1 \L 2

perbedaan antara bahasa L 1 dan L 2. Sebuah kata α dari A * dianggap milik L 1 \L 2 jika dan hanya jika kata tersebut termasuk dalam bahasa L 1, tetapi bukan milik bahasa L 2. Jelas sekali bahwa perbedaan operasi dapat direpresentasikan melalui teori dasar

beberapa operasi: L 1 \L 2 =L 1 ∩ (L 2 )с.

Selain itu, kami memperkenalkan beberapa operasi khusus pada bahasa. Misalkan L 1 dan L 2 adalah bahasa dalam alfabet A. Misalkan L 1 ( L 2 menunjukkan bahasa

didefinisikan sebagai berikut: kata α termasuk dalam bahasa L 1 ( L 2 jika dan hanya jika kata tersebut dapat dibagi menjadi dua bagian yang berurutan

(yaitu disajikan dalam bentuk α = α 1 α 2 ) sehingga bagian pertama adalah kata dari bahasa L 1 , dan bagian kedua adalah kata dari bahasa L 2 . Pengoperasian ( disebut penggabungan (linking) bahasa. Tanda ( sering dihilangkan, kemudian penggabungan bahasa L 1 dan L 2 ditulis L 1 L 2. Bahasa L 1 L 2 diperoleh dengan menjumlahkan kata dari bahasa L 2 ke kata-kata bahasa L 1 sebagai akhiran, bahwa jika kata kosong ditambahkan ke kata sembarang γ, maka hasilnya adalah kata γ. dan bahasa pertama berisi m kata, dan bahasa kedua berisi n kata, maka bahasa L 1 L 2. terdiri paling banyak mn kata. Jika salah satu bahasa L 1, L 2 kosong, maka L 1 L 2 juga merupakan bahasa kosong.

Mari kita perkenalkan operasi menaikkan bahasa menjadi suatu kekuatan. Kami percaya:

L 0 =(λ);

L1 = L;

L2 = LL; Ln +1 = Ln L, n=2, 3, ...;

dengan demikian, konsep derajat L i dari bahasa L didefinisikan untuk sembarang i =0, 1, 2, 3,

L* =U Li.

saya= 0

Operasi yang diperkenalkan disebut iterasi. Perhatikan bahwa kata kosong itu milik iterasi bahasa apa pun. Kata tak kosong α termasuk dalam iterasi bahasa L jika dan hanya jika kata tersebut dapat dibagi menjadi beberapa bagian (subkata) yang berurutan sehingga setiap bagian termasuk dalam bahasa L. Jika suatu bahasa L terdiri dari semua kata satu huruf dalam alfabet A, maka iterasi bahasa tersebut adalah bahasa universal A*. Perhatikan bahwa untuk bahasa apa pun L kita memiliki (L *)*=L *.

Dalam banyak bahasa, operator unary berikut ()+ terkadang dianggap:

(L )+ =U L saya .

saya= 1

Bahasa L* dan L+ berbeda satu sama lain hanya pada kata kosongnya. Kata λ selalu termasuk dalam bahasa L*. Ia termasuk dalam bahasa L + jika dan hanya jika ia termasuk dalam bahasa L .

2. Konsep mesin keadaan terbatas dan bahasa reguler.

Dalam sibernetika, automata adalah modul yang diimplementasikan secara teknis atau perangkat lunak yang dirancang untuk memproses informasi yang masuk. Mesin negara adalah modul yang memiliki sejumlah kemungkinan status terbatas dan beroperasi dalam waktu diskrit. Dalam tutorial ini, mesin keadaan terbatas dipelajari sebagai perangkat algoritmik abstrak yang dirancang untuk memproses kata-kata dengan alfabet masukan tetap. Kami berasumsi bahwa robot mulai memproses kata arbitrer α dalam alfabet masukan A dari keadaan awal yang dipilih secara khusus. Pada setiap jam waktu diskrit, huruf berikutnya dari kata yang diproses tiba di masukan mesin; Keadaan dimana mesin akan berjalan ditentukan oleh keadaan sebelumnya dan huruf yang dibaca dari kata masukan. Mesin bekerja pada sebuah kata dengan panjang l siklus. Hasil pengoperasian mesin ditentukan oleh keadaan mesin tersebut setelah selesai.

Secara formal, kita mendefinisikan otomat berhingga K sebagai himpunan

K=(Q, A, q0, g, F),

dimana Q =(q 0, q 1, q 2, ..., q m) – himpunan keadaan robot; A = (a 1, a 2, ..., an) – masukan alfabet; q 0 – keadaan mesin yang dipilih secara khusus, disebut keadaan awal; g – fungsi transisi dari mesin berhingga,

yang merupakan pemetaan bertipe Q xA → Q (jika g (q i,a j)=q k, maka robot dari keadaan q i di bawah pengaruh huruf a j harus menuju ke keadaan q k); F adalah himpunan bagian keadaan otomat yang dipilih secara khusus, yang secara konvensional kita sebut “baik”, F Q .

keadaan di mana robot K menemukan dirinya sendiri setelah t siklus mengerjakan kata ini (di sini t = 0, 1, 2, ..., p):

qα (0) =q0 ;

q α (1) = g (q α (0), a saya 1 )

q α (2) = g (q α (1), a saya 2 )

q α (p) = g (q α (p − 1), a saya p)

Kita akan mengatakan bahwa kata α diterima oleh otomat K jika q α (р) F.

Mari kita perkenalkan bahasa L(K): kata α termasuk dalam bahasa L(K) jika kata tersebut diterima oleh otomat K. Bahasa L(K) disebut bahasa yang dikenali oleh mesin keadaan terbatas ini. Kita menyebut suatu bahasa L reguler jika memungkinkan untuk membuat otomat terbatas yang mengenalinya.

Lebih mudah untuk mendefinisikan mesin keadaan terbatas melalui diagram transisinya. Diagram adalah graf berarah, yang simpul-simpulnya identik dengan keadaan robot; busur dari titik sudut q i ke titik sudut q k dengan huruf a j tertulis di atasnya digambarkan jika dan hanya jika g (q i,a j)=q k. Dalam hal transisi dari q i ke q k dilakukan di bawah pengaruh salah satu huruf dari himpunan bagian tertentu S, S A, semua huruf dari himpunan bagian ini ditandatangani di atas busur yang sesuai (alih-alih daftar semua huruf, yang entri yang disingkat “x S” atau sekadar “S” diperbolehkan). Jika keadaan sembarang q i termasuk dalam F, maka fakta ini ditandai pada diagram dengan lingkaran tebal yang menyorot titik puncak q i.

Jelasnya, setiap mesin keadaan terbatas sepenuhnya ditentukan oleh diagram transisinya. Selanjutnya, tugas membangun robot terbatas dengan sifat-sifat tertentu akan dipahami sebagai tugas membangun diagram transisinya.

Pada Gambar. Gambar 2.1 menunjukkan diagram robot K 1 yang mengerjakan kata-kata alfabet A =(a,b,c). Otomat tersebut mempunyai dua keadaan, q 0 dan q 1, dan hanya keadaan q 1 yang “baik”. Setelah mulai bekerja dalam keadaan q 0, mesin tidak meninggalkan keadaan ini di bawah pengaruh huruf a, b; di bawah pengaruh huruf c, transisi ke keadaan q 1 terwujud; surat yang masuk selanjutnya akan meninggalkan mesin dalam keadaan yang sama. Dengan demikian, otomat K 1 mengenali bahasa L 1 yang terdiri dari kata-kata yang mengandung huruf c. bahasa ini teratur.

q0 q1

Mari kita berikan beberapa contoh lagi bahasa biasa dalam alfabet yang sama: L 2 - sekumpulan kata yang huruf a muncul beberapa kali genap; L 3 - kumpulan kata yang dimulai dan diakhiri dengan huruf yang sama; L 4

Sekumpulan kata yang mengandung subkata α =abbc ; L 5 adalah himpunan kata, bila dibaca dari kiri ke kanan selisih jumlah huruf a dan b yang ditemui tidak pernah melebihi 2. Diagram mesin keadaan terbatas K 2 - K 5 yang mengenal bahasa L 2 - L 5 , masing-masing, disajikan pada Gambar 2.2 - 2.5. Mesin “mengingat” informasi tentang bagian kata masukan yang diproses berdasarkan statusnya. Jadi, misalnya robot K 5, setelah memproses beberapa bagian dari kata masukan, mendapati dirinya dalam keadaan q x jika pada bagian kata masukan yang dibacanya, jumlah huruf a yang ditemui melebihi jumlah huruf b yang ditemui oleh X; di sini x (-2, -1, 0, 1, 2); otomat dalam keadaan q buruk jika pada suatu saat dalam pengoperasian otomat nilai absolut selisih antara jumlah huruf a yang diproses dan jumlah huruf b yang diproses melebihi 2.

		sangat buruk

Kita menyebut keadaan otomat berhingga menyerap jika ada huruf masukan yang tidak mengeluarkan otomat dari keadaan ini. Sebut saja keadaan menyerap menyerap secara positif, jika itu milik F, dan menyerap secara negatif jika tidak. Dalam automata K 1 dan K 4, keadaan q 1 dan q 4 masing-masing menyerap secara positif; dalam automata K 5, keadaan q buruk menyerap secara negatif.

Kita dapat berasumsi bahwa setiap robot memiliki tidak lebih dari satu keadaan penyerap positif dan tidak lebih dari satu keadaan penyerap negatif (jika ada beberapa keadaan penyerap positif atau negatif, maka keadaan tersebut dapat dengan mudah digantikan oleh satu keadaan). Biasanya, keadaan penyerap negatif tidak digambarkan dalam diagram transisi; jika peralihan dari suatu keadaan tertentu tidak ditunjukkan dengan huruf tertentu, maka dianggap mengarah pada keadaan menyerap secara negatif. Mesin terbatas yang ditunjukkan pada Gambar 2.6 mengenali bahasa alfabet A yang terdiri dari kata-kata yang huruf c muncul tepat satu kali. Otomat ini mempunyai 3 keadaan, keadaan penyerap negatif q buruk (otomat masuk ke dalamnya dari keadaan q 1 sesuai huruf c) tidak ditunjukkan dalam diagram.

q0 q1

Mari kita perkenalkan alfabet B =(0, 1, 2, …, 9), setiap kata dalam alfabet ini diperlakukan sebagai bilangan bulat non-negatif. Misalkan L (p) menunjukkan himpunan kata - catatan dalam sistem bilangan desimal dari semua bilangan bulat non-negatif yang merupakan kelipatan dari konstanta alami p; kita akan berasumsi bahwa bahasa L (p)

selain itu kata kosong λ juga termasuk. Mari kita tunjukkan bahwa L (p) adalah bahasa biasa. Sebuah robot terbatas K(p) yang mengenali L(p) dapat dibuat sebagai berikut. Kami menganggap keadaan robot adalah q 0, q 1, q 2, q p –1; dari keadaan sembarang q i dengan angka x, x (0, 1, 2, ... ,9), mesin menuju ke

Buku teks ini berisi materi ekstensif tentang teori automata. Memperkenalkan konsep automata, memberikan teori automata abstrak dan struktural, serta mengungkap permasalahan dalam teori automata struktural dan struktur homogen. Buku ini dengan cukup lengkap mengulas hasil-hasil utama teori finite automata yang diperoleh penulis dalam dan luar negeri pada masa kemunculan dan perkembangan teori automata.

Langkah 1. Pilih buku dari katalog dan klik tombol “Beli”;

Langkah 2. Buka bagian “Keranjang”;

Langkah 3. Tentukan jumlah yang dibutuhkan, isi data pada blok Penerima dan Pengiriman;

Langkah 4. Klik tombol “Lanjutkan ke Pembayaran”.

Saat ini, pembelian buku cetak, akses elektronik, atau buku sebagai hadiah ke perpustakaan dapat dilakukan di situs web ELS hanya dengan pembayaran di muka 100%. Setelah pembayaran, Anda akan diberikan akses ke teks lengkap buku teks di Perpustakaan Elektronik atau kami akan mulai menyiapkan pesanan untuk Anda di percetakan.

Perhatian! Harap jangan mengubah metode pembayaran Anda untuk pesanan. Jika Anda telah memilih metode pembayaran dan gagal menyelesaikan pembayaran, Anda harus melakukan pemesanan ulang dan membayarnya menggunakan metode lain yang nyaman.

Anda dapat membayar pesanan Anda menggunakan salah satu metode berikut:

1. Metode tanpa uang tunai:
   • Kartu bank: Anda harus mengisi semua kolom formulir. Beberapa bank meminta Anda untuk mengonfirmasi pembayaran - untuk ini, kode SMS akan dikirimkan ke nomor telepon Anda.
   • Perbankan online: bank yang bekerja sama dengan layanan pembayaran akan menawarkan formulir sendiri untuk diisi.
     Silakan masukkan data dengan benar di semua kolom. Misalnya untuk" class="text-primary">Sberbank Online nomor yang diperlukan telepon genggam dan email. Untuk
   • " class="text-primary">Bank Alfa Anda memerlukan login ke layanan Alfa-Click dan email.