To Chapter 1 Indo.docx

KATA PENGANTAR Buku ini dirancang untuk sebuah pengantar saja pada bahasa formal, automata, computability, dan hal-hal terkait. Topik-topik ini membentuk utama bagian dari apa yang dikenal sebagai teori komputasi. Sebuah kursus ini subyek sekarang standar dalam kurikulum ilmu komputer dan sering diajarkan cukup awal dalam program ini. Oleh karena itu, calon penonton untuk buku ini terutama terdiri dari mahasiswi dan yunior jurusan ilmu komputer atau teknik komputer. Prasyarat untuk materi dalam buku ini adalah pengetahuan tentang beberapa bahasa pemrograman tingkat tinggi (umumnya C, C ++, atau Java ™) dan keakraban dengan dasar-dasar struktur data dan algoritma. SEBUAH Tentu saja dalam matematika diskrit yang mencakup teori himpunan, fungsi, hubungan, logika, dan unsur-unsur penalaran matematika adalah penting. Seperti itu kursus adalah bagian dari ilmu komputer pengantar standar kurikulum. Studi tentang teori komputasi memiliki beberapa tujuan, yang paling penting (1) untuk membiasakan siswa dengan dasar-dasar dan prinsip-prinsip ilmu komputer, (2) untuk mengajarkan materi yang berguna dalam berikutnya kursus, dan (3) untuk memperkuat kemampuan siswa untuk melaksanakan formal dan argumen matematika yang ketat. Presentasi saya telah memilih untuk teks ini nikmat dua tujuan pertama, meskipun saya berpendapat bahwa hal itu juga melayani ketiga. Untuk mempresentasikan ide secara jelas dan untuk memberikan siswa wawasan materi, teks menekankan motivasi intuitif dan ilustrasi ide melalui contoh. Ketika ada pilihan, saya lebih memilih argumen yang mudah digenggam untuk mereka yang ringkas dan elegan namun sulit dalam konsep. Saya menyatakan definisi dan teorema tepat dan memberikan motivasi untuk bukti, tetapi sering meninggalkan rincian rutin dan membosankan.

Saya percaya bahwa ini adalah diinginkan untuk alasan pedagogis. Banyak bukti yang aplikasi tanpa kegirangan induksi atau bertentangan dengan perbedaan yang khusus untuk masalah tertentu. Menyajikan argumen tersebut secara penuh detail tidak hanya tidak perlu, tetapi mengganggu aliran cerita. Oleh karena itu, beberapa dari bukti-bukti yang singkat dan seseorang yang bersikeras kelengkapan mungkin menganggap mereka kurang rinci. Saya tidak melihat ini sebagai kekurangan. keterampilan matematika bukan produk sampingan dari membaca seseorang argumen lain, tetapi berasal dari berpikir tentang esensi masalah, menemukan ide-ide yang cocok untuk membuat titik, kemudian membawa mereka keluar di detail yang tepat. Keterampilan yang terakhir tentu harus dipelajari, dan saya berpikir bahwa sketsa bukti dalam teks ini memberikan titik awal yang sangat tepat untuk praktek tersebut. mahasiswa ilmu komputer kadang-kadang melihat kursus dalam teori perhitungan sebagai tidak perlu abstrak dan tidak ada konsekuensinya praktis. Untuk meyakinkan mereka sebaliknya, salah satu kebutuhan untuk menarik khusus mereka kepentingan dan kekuatan, seperti keuletan dan keahlian dalam menangani sulit memecahkan masalah. Karena itu, pendekatan saya menekankan belajar melalui pemecahan masalah. Dengan pendekatan pemecahan masalah, saya berarti bahwa siswa belajar bahan terutama melalui masalah-jenis contoh ilustrasi yang menunjukkan motivasi di balik konsep-konsep, serta hubungan mereka dengan teorema dan definisi. Pada saat yang sama, contoh mungkin melibatkan Aspek trivial, yang siswa harus menemukan solusi. Dalam seperti Pendekatan, latihan PR berkontribusi bagian utama dari pembelajaran proses. Latihan di akhir setiap bagian dirancang untuk menerangi dan menggambarkan materi dan memanggil problemsolving siswa kemampuan di berbagai tingkatan. Beberapa latihan yang cukup sederhana, mengambil tempat diskusi dalam teks daun off dan meminta siswa untuk melanjutkan untuk langkah atau dua. latihan lain yang sangat sulit,

menantang bahkan pikiran terbaik. Sebuah campuran yang baik dari latihan tersebut dapat menjadi alat pengajaran yang sangat efektif. Siswa tidak perlu diminta untuk menyelesaikan semua masalah, tetapi harus ditugaskan mereka yang mendukung tujuan dari kursus dan sudut pandang instruktur. kurikulum ilmu komputer berbeda dari lembaga ke lembaga; sementara beberapa menekankan sisi teoritis, yang lain hampir seluruhnya berorientasi praktis aplikasi. Saya percaya bahwa teks ini dapat melayani salah satu dari ekstrim ini, asalkan latihan hati-hati dipilih dengan siswa latar belakang dan kepentingan dalam pikiran. Pada saat yang sama, kebutuhan instruktur untuk menginformasikan siswa tentang tingkat abstraksi yang diharapkan dari mereka. Hal ini terutama berlaku dari latihan bukti-oriented. Ketika saya bicara “Membuktikan bahwa” atau “menunjukkan bahwa,” Saya ada dalam pikiran bahwa siswa harus berpikir tentang bagaimana bukti dapat dibangun dan kemudian menghasilkan argumen yang jelas. Bagaimana resmi bukti tersebut seharusnya kebutuhan akan ditentukan oleh instruktur, dan siswa harus diberikan pedoman ini di awal Tentu saja. Isi teks sesuai untuk kursus satu semester. Paling material dapat ditutup, meskipun beberapa pilihan penekanan akan harus dibuat. Di kelas saya, saya biasanya mengabaikan bukti-bukti, memberikan hanya cakupan cukup untuk membuat hasil yang masuk akal, dan kemudian meminta siswa untuk membaca sisa sendiri. Secara keseluruhan, meskipun, sedikit dapat dilewati seluruhnya tanpa kesulitan potensial di kemudian hari. Beberapa bagian, yang ditandai dengan tanda bintang, dapat dihilangkan tanpa kerugian materi kemudian. Sebagian besar material, bagaimanapun, adalah penting dan harus ditutupi.

Lampiran B secara singkat memperkenalkan JFLAP, alat perangkat lunak interaktif yang adalah membantu dalam kedua belajar dan mengajar materi dalam buku ini. Saya t bantu dalam memahami konsep-konsep dan menghemat waktu dalam sebenarnya pembangunan solusi untuk latihan. Saya sangat merekomendasikan menggabungkan JFLAP ke kursus. sumber instruktur untuk JFLAP adalah tersedia di website teks ini: go.jblearning.com/LinzJPAK. Dalam edisi keenam saya telah menambahkan sejumlah fitur yang dirancang untuk membawa beberapa materi yang lebih sulit dalam fokus yang lebih tajam. setiap bab didahului oleh ringkasan yang tidak hanya memperkenalkan konsep utama, tetapi juga menghubungkan konsep-konsep ini untuk apa yang telah terjadi sebelum dan apa akan dibahas kemudian. Ringkasan membentuk sinopsis cerita dikembangkan dalam buku ini. Di mana abstraksi sulit diperlukan, saya harus menambahkan diskusi beton yang menggambarkan alasan spesifik bentuk abstraksi. Akhirnya, pengguna instruktur telah direvisi dan diperluas sehingga sekarang berisi solusi rinci untuk semua latihan dalam buku ini. Peter Linz

BAB 1 PENGANTAR TEORI KOMPUTASI BAB RINGKASAN Bab ini mempersiapkan Anda untuk apa yang akan datang. Dibagian 1.1. kami meninjau beberapa ide utama dari matematika yang terbatas dan membangun notasi yang digunakan dalam teks. terutama penting adalah teknik bukti, khususnya bukti dengan induksi dan bukti dengan kontradiksi. bagian 1.2 memberi Anda pertama melihat ide-ide yang di Inti dari buku: automata, bahasa, tata bahasa, mereka

definisi, dan hubungan mereka. Dalam bab-bab selanjutnya, kita akan memperluas ide-ide ini dan mempelajari sejumlah jenis automata dan tata bahasa. Di bagian 1.3, Kita menemukan beberapa contoh sederhana dari peran konsep-konsep ini bermain di ilmu komputer, khususnya di bahasa pemrograman, desain digital, dan pengolahan teks. Kita tidak memukul masalah ini di sini, karena Anda akan menemukan aplikasi konsep-konsep ini dalam sejumlah program lainnya CS. Subyek buku ini, teori komputasi, termasuk beberapa topik: teori automata, bahasa formal dan tata bahasa, computability, dan kompleksitas. Bersama-sama, bahan ini merupakan landasan teoritis dari ilmu komputer. Longgar berbicara kita dapat memikirkan automata, tata bahasa, dan komputabilitas sebagai studi tentang apa yang bisa dilakukan oleh komputer pada prinsipnya, sementara kompleksitas membahas apa yang bisa dilakukan dalam praktek. Dalam buku ini kita fokus hampir seluruhnya pada pertama kekhawatiran ini. Kami akan mempelajari berbagai automata, melihat bagaimana mereka terkait untuk bahasa dan tata bahasa, dan menyelidiki apa yang bisa dan tidak bisa dilakukan oleh komputer digital. Meskipun teori ini memiliki banyak kegunaan, itu adalah inheren abstrak dan matematika. ilmu komputer adalah disiplin praktis. Mereka yang bekerja di dalamnya sering memiliki preferensi ditandai untuk masalah berguna dan nyata lebih spekulasi teoritis. Hal ini memang benar dari ilmu komputer siswa yang bersangkutan terutama dengan aplikasi yang sulit dari dunia nyata. pertanyaan teoritis menarik perhatian mereka hanya jika mereka membantu dalam menemukan solusi yang baik. Sikap ini adalah tepat, karena tanpa Aplikasi akan ada sedikit minat dalam komputer. Tetapi mengingat ini orientasi praktis, satu mungkin bertanya “mengapa teori belajar?” Jawaban pertama adalah bahwa teori menyediakan konsep dan prinsipprinsip yang

membantu kita memahami sifat umum dari disiplin. Bidang ilmu komputer mencakup berbagai topik khusus, dari mesin desain untuk pemrograman. Penggunaan komputer di dunia nyata melibatkan kekayaan detail tertentu yang harus dipelajari untuk sukses aplikasi. Hal ini membuat ilmu komputer sangat beragam dan luas disiplin. Tapi terlepas dari keragaman ini, ada beberapa umum prinsip-prinsip yang mendasari. Untuk mempelajari prinsip-prinsip dasar, kita membangun model abstrak dari komputer dan komputasi. Model ini mewujudkan fitur penting yang umum untuk hardware dan software dan yang penting untuk banyak konstruksi khusus dan kompleks kami hadapi saat bekerja dengan komputer. Bahkan ketika model tersebut terlalu sederhana untuk dapat diterapkan segera untuk situasi dunia nyata, yang wawasan yang kita peroleh dari belajar mereka memberikan dasar yang pembangunan yang spesifik didasarkan. Pendekatan ini, tentu saja, tidak unik untuk ilmu Komputer. Pembangunan model adalah salah satu hal penting dari setiap disiplin ilmu, dan kegunaan dari disiplin sering tergantung pada keberadaan sederhana, namun kuat, teori dan hukum. Kedua, dan mungkin tidak begitu jelas, jawabannya adalah bahwa ide-ide kita akan mendiskusikan memiliki beberapa aplikasi langsung dan penting. Bidang desain digital, bahasa pemrograman, dan compiler adalah yang paling contoh jelas, tetapi ada banyak orang lain. Konsep yang kita belajar di sini berjalan seperti benang melalui banyak ilmu komputer, dari operasi sistem untuk pengenalan pola. Jawaban ketiga adalah salah satu yang kami berharap untuk meyakinkan pembaca. Itu materi pelajaran secara intelektual merangsang dan menyenangkan. Ini menyediakan banyak menantang, teka-teki seperti masalah yang dapat menyebabkan beberapa malam tanpa tidur. Ini adalah pemecahan pada dasarnya murni masalah. Dalam buku ini, kita akan melihat model yang mewakili fitur pada intinya dari semua komputer dan aplikasi mereka. Untuk model perangkat keras dari

komputer, kami memperkenalkan gagasan tentang automaton (jamak, automata). Robot adalah membangun yang memiliki semua fitur yang sangat diperlukan dari komputer digital. Ia menerima input, menghasilkan output, mungkin memiliki beberapa penyimpanan sementara, dan dapat membuat keputusan dalam mentransformasikan input menjadi hasil. SEBUAHbahasa formal adalah abstraksi dari umum karakteristik bahasa pemrograman. Sebuah bahasa formal terdiri dari set simbol dan beberapa aturan pembentukan dimana simbol-simbol ini dapat digabungkan menjadi entitas disebut kalimat. Sebuah bahasa formal adalah himpunan semua kalimat diizinkan oleh aturan-aturan pembentukan. Meskipun beberapa bahasa formal yang kita belajar di sini lebih sederhana daripada bahasa pemrograman, mereka memiliki banyak fitur penting yang sama. Kita bisa belajar banyak tentang pemrograman bahasa dari bahasa formal. Akhirnya, kita akan memformalkan konsep perhitungan mekanik dengan memberikan tepat definisi istilah algoritma dan mempelajari jenis masalah yang (Dan tidak) cocok untuk solusi dengan cara mekanis seperti. Dalam program studi kami, kami akan menunjukkan hubungan erat antara ini abstraksi dan menyelidiki kesimpulan yang kita dapat berasal dari mereka. Dalam bab pertama, kita melihat ide-ide dasar dalam cara yang sangat luas untuk mengatur panggung untuk kemudian bekerja. Dibagian 1.1, Kami meninjau gagasan utama dari matematika yang akan dibutuhkan. Sementara intuisi akan sering menjadi kami membimbing dalam mengeksplorasi ide-ide, kesimpulan yang kita ambil akan didasarkan pada argumen yang ketat. Hal ini akan melibatkan beberapa mesin matematika, meskipun persyaratan yang tidak luas. pembaca akan membutuhkan pemahaman yang cukup baik dari terminologi dan hasil dasar dari menetapkan teori, fungsi, dan hubungan. Pohon dan struktur grafik akan sering digunakan, meskipun sedikit yang dibutuhkan di luar definisi label, grafik diarahkan. Mungkin persyaratan paling ketat adalah

kemampuan untuk mengikuti bukti dan pemahaman tentang apa yang merupakan tepat penalaran matematika. Ini termasuk keakraban dengan bukti dasar teknik deduksi, induksi, dan bukti dengan kontradiksi. Kami akan berasumsi bahwa pembaca memiliki latar belakang yang diperlukan ini. bagian 1.1 aku s termasuk untuk meninjau beberapa hasil utama yang akan digunakan dan untuk membangun kesamaan notasi untuk diskusi berikutnya. Di bagian 1.2, Kita melihat pertama pada konsep pusat bahasa, tata bahasa, dan automata. Konsep-konsep ini terjadi dalam berbagai bentuk tertentu seluruh buku. Dibagian 1.3, Kami memberikan beberapa aplikasi sederhana ide-ide umum untuk menggambarkan bahwa konsep-konsep ini memiliki kegunaan luas dalam ilmu komputer. Pembahasan dalam dua bagian ini akan menjadi intuitif bukan ketat. Kemudian, kami akan membuat semua ini jauh lebih tepat; tapi untuk saat ini, tujuannya adalah untuk mendapatkan gambaran yang jelas tentang konsep-konsep dengan yang kita hadapi.

1.1 PENDAHULUAN MATEMATIKA DAN NOTASI set SEBUAH set adalah kumpulan dari elemen-elemen, tanpa struktur selain keanggotaan. Untuk menunjukkan bahwax adalah elemen dari himpunan S, kami menulis x ∈ S. pernyataan bahwax tidak di S ditulis x ∉ S. Satu set dapat ditentukan dengan melampirkan beberapa deskripsi dari elemen dalam kurung kurawal; sebagai contoh, himpunan bilangan bulat 0, 1, 2 ditampilkan sebagai

S = {0, 1, 2}. Elips digunakan setiap kali arti yang jelas. Dengan demikian, {a, b, ..., z} berdiri untuk semua huruf kecil dari alfabet Inggris, sementara {2, 4, 6, ...}

menunjukkan himpunan semua bilangan bulat bahkan positif. Ketika kebutuhan muncul, kita menggunakan notasi lebih eksplisit, di mana kita menulis S = {saya : i> 0, saya Bahkan} (1.1) untuk contoh terakhir. Kita membaca ini sebagai “S adalah himpunan semua saya, seperti yang saya aku s lebih besar dari nol, dan saya Bahkan,”menyiratkan, tentu saja, bahwa saya adalah bilangan bulat. Operasi himpunan yang Persatuan (∪), persimpangan (∩), Dan perbedaan (-) didefinisikan sebagai S1 ∪ S2 = {x : x ∈ S1 atau x ∈ S2}, S1 ∩ S2 = {x : x ∈ S1 dan x ∈ S2}, S1 - S2 = {x : x ∈ S1 dan x ∉ S2}. operasi dasar lain adalah komplementasi. Komplemen dari set S, Dilambangkan dengan, terdiri dari semua elemen tidak di S. Untuk membuat ini bermakna, kita perlu tahu apa yang universal set U dari semua kemungkinan elemen ini. JikaU yang ditentukan, maka Set tanpa elemen, yang disebut himpunan kosong atau set nol, aku s dilambangkan dengan ∅. Dari definisi set, jelas bahwa Berikut identitas berguna, yang dikenal sebagai hukum DeMorgan. (1.2) (1.3) diperlukan pada beberapa kesempatan. Satu set S1 dikatakan menjadi bagian dari S jika setiap elemen S1 juga unsur S. Kami menulis ini sebagai S1 ⊆ S. Jika S1 ⊆ S, tapi S mengandung unsur tidak S1, Kita mengatakan bahwa S1 adalah layak bagian dari S; kita menulis ini sebagai S1 ⊂ S. Jika S1 dan S2 tidak memiliki elemen umum, yaitu, S1 ∩ S2 = ∅, Maka set dikatakan menguraikan.

Satu set dikatakan terbatas jika mengandung jumlah terbatas elemen; kalau tidak tak terbatas. Ukuran dari himpunan berhingga adalah jumlah elemen di dalamnya; ini dilambangkan dengan |S|. Sebuah himpunan biasanya memiliki banyak himpunan bagian. Himpunan semua himpunan bagian dari suatu himpunanS disebut Powerset dari S dan dilambangkan dengan 2S. Perhatikan bahwa 2S adalah satu set set. CONTOH 1.1 Jika S adalah himpunan {a, b, c}, Maka Powerset adalah 2S = {∅, {Sebuah}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. Berikut |S| = 3 dan | 2S| = 8. Ini adalah sebuah contoh dari hasil umum; jikaS terbatas, maka | 2S| = 2|S|. Dalam banyak contoh kita, unsur-unsur dari suatu himpunan yang memerintahkan urutan dari unsur set lain. set tersebut dikatakanCartesian produk set lainnya. Untuk produk Cartesian dari dua set, yang dengan sendirinya adalah himpunan pasangan memerintahkan, kita menulis S = S1 × S2 = {(x, y): x ∈ S1. y ∈ S2}. CONTOH 1.2 Membiarkan S1 = {2, 4} dan S2 = {2, 3, 5, 6}. Kemudian S1 × S2 = {(2, 2), (2, 3), (2, 5), (2, 6), (4, 2), (4, 3), (4, 5), (4,

6)}. Perhatikan bahwa urutan di mana unsur-unsur sepasang ditulis hal. Pasangan (4, 2) adalah diS1 × S2, Tetapi (2, 4) tidak. notasi diperpanjang dengan cara yang jelas untuk Cartesian produk lebih dari dua set; umumnya S1 × S2 × ··· × Sn = {(x1. x2. ..., xn): xsaya ∈ Ssaya}. Satu set dapat dibagi dengan memisahkannya menjadi beberapa himpunan bagian. Seharusnya bahwa S1. S2, ..., Sn adalah himpunan bagian dari himpunan S dan bahwa berikut ini berlaku: 1. The subset S1. S2, ..., Sn saling beririsan;

2. S1 ∪ S2 ∪ ... ∪ Sn = S; 3. tak satupun dari Ssaya kosong. Kemudian S1. S2, ..., Sn disebut sekat dari S.

Fungsi dan Hubungan SEBUAH fungsi adalah aturan yang memberikan unsur-unsur dari satu set elemen yang unik dari set. Jikaf menunjukkan fungsi, maka set pertama disebut domain dari f, Dan set kedua adalah yang jarak. Kami menulis f : S1 → S2 untuk menunjukkan bahwa domain f adalah bagian dari S1 dan bahwa berbagai f adalah bagian dari S2. Jika domainf adalah semua S1, Kita mengatakan bahwa f adalah fungsi Total di S1; jika tidakf dikatakan menjadi fungsi parsial. Dalam banyak aplikasi, domain dan berbagai fungsi yang terlibat berada di himpunan bilangan bulat positif. Selain itu, kami sering tertarik hanya dalam perilaku fungsi-fungsi ini sebagai argumen mereka menjadi sangat besar. Dalam kasus seperti pemahaman tentang tingkat pertumbuhan mungkin cukup dan urutan umum notasi besarnya dapat digunakan. Membiarkanf (n) dan g (n) menjadi fungsi yang domain adalah bagian dari bilangan bulat positif. Jika ada konstanta positif c sehingga untuk semua cukup besar n

f (n) ≤ c|g (n) |, kita mengatakan bahwa f memiliki Agar paling g. Kami menulis ini sebagai

f (n) = HAI (g (n)). Jika

| f (n) | ≥c |g (n) |, kemudian f memiliki Agar setidaknya g, Yang kami gunakan

f (n) = Ω (g (n)). Akhirnya, jika terdapat konstanta c1 dan c2 seperti yang c1 |g (n) | ≤ |f (n) | ≤c2 |g (n) |, f dan g punya urutan yang sama besarnya, diekspresikan sebagai

f (n) = Θ (g (n)). Dalam rangka-of-besarnya notasi, kita mengabaikan konstanta perkalian

Ketentuan dan lebih rendah-order yang menjadi diabaikan sebagai n meningkatkan. CONTOH 1.3 Membiarkan f (n) = 2n2 + 3n. g (n) = n3. h (n) = 10n2 + 100. Kemudian f (n) = HAI (g (n)), g (n) = Ω (h (n)), f (n) = Θ(h (n)). Dalam rangka-of-besarnya notasi, simbol = tidak harus diartikan sebagai kesetaraan dan ketertiban-of-besarnya ekspresi tidak bisa diperlakukan seperti ekspresi biasa. Manipulasi seperti

HAI (n) + HAI (n) = 2HAI (n) tidak masuk akal dan dapat menyebabkan kesimpulan yang salah. Namun, jika digunakan benar, urutan-of-besarnya argumen dapat efektif, seperti yang kita akan melihat di bab berikutnya. Beberapa fungsi dapat diwakili oleh satu set pasangan {(x1. y1), (x2. y2), ...}, dimana xsaya adalah elemen dalam domain fungsi, dan ysaya adalah sesuai nilai dalam jangkauan. Untuk set tersebut untuk menentukan fungsi, masing-masing xsaya dapat terjadi pada sebagian besar sekali sebagai elemen pertama dari pasangan. Jika hal ini tidak puas, set ini disebut hubungan. Hubungan yang lebih umum dari fungsi: Dalam fungsi setiap elemen dari domain memiliki tepat satu terkait elemen dalam kisaran; dalam relasi mungkin ada beberapa seperti elemen dalam jangkauan. Salah satu jenis hubungan adalah bahwa dari persamaan derajatnya, Generalisasi dari Konsep kesetaraan (identitas). Untuk menunjukkan bahwa pasangan (x, y) Adalah dalam kesetaraan relasi, kita menulis

x ≡ y.

Suatu relasi dilambangkan dengan ≡ dianggap sebagai kesetaraan jika memenuhi tiga aturan: aturan refleksivitas

x ≡ x untuk semua x; aturan simetri

jika x ≡ y, kemudian y ≡ x; dan aturan transitivitas

jika x ≡ y dan y ≡ z, kemudian x ≡ z. CONTOH 1.4 Pada himpunan bilangan bulat non-negatif, kita dapat mendefinisikan relasi

x≡y jika dan hanya jika

x mod 3 = y mod 3. kemudian 2 ≡ 5, 12 ≡ 0, dan 0 ≡ 36. Jelas ini adalah hubungan ekuivalensi, karena memenuhi refleksivitas, simetri, dan transitivitas. Jika S adalah satu set di mana kita memiliki relasi ekivalen didefinisikan, maka kita dapat menggunakan kesetaraan ini untuk partisi set ke kelas kesetaraan. Setiap kelas kesetaraan berisi semua dan hanya setara elemen.

Grafik dan Pohon Sebuah grafik adalah membangun terdiri dari dua set terbatas, set V = {v1. v2. ..., vn} dari simpul dan set E = {e1. e2. ..., em} dari ujung-ujungnya. Setiap sisi adalah sepasang simpul dari V, contohnya, esaya = (vj. vk) adalah tepi dari vj untuk vk. Kami mengatakan bahwa tepiesaya adalah tepi keluar untuk vj dan keunggulan yang masuk untuk vk. Seperti membangun sebuah sebenarnya diarahkan grafik (Digraf), karena kita kaitkan arah (dari vj untuk vk) Dengan masing-masing tepi. Grafik dapat diberi label, label menjadi nama atau informasi lain terkait dengan bagian-bagian dari grafik. Kedua titik dan sisi mungkin berlabel. Grafik yang nyaman divisualisasikan oleh diagram di mana simpul

direpresentasikan sebagai lingkaran dan ujung-ujungnya sebagai garis dengan panah yang menghubungkan simpul. Grafik dengan simpul {v1. v2. v3} Dan tepi {(v1. v3), (v3. v1), (v3. v2), (v3. v3)} Digambarkan dalam Gambar 1.1. GAMBAR 1.1

Sebuah urutan tepi (vsaya. vj), (vj. vk), ..., (vm. vn) Dikatakan menjadi berjalan dari vsaya untuk vn. Panjang jalan adalah jumlah total dari tepi dilalui di pergi dari titik awal untuk yang terakhir. Berjalan di mana tidak ada tepi adalah diulang dikatakan menjadi path; jalan adalahsederhana jika tidak ada titik diulang. SEBUAH berjalan kaki dari vsaya untuk dirinya sendiri tanpa tepi diulang disebut sepeda dengan mendasarkan vsaya. Jika tidak ada simpul lain selain dasar diulang dalam siklus, maka dikatakan sederhana. DiGambar 1.1, (v1. v3), (v3. v2) Adalah jalan sederhana dari v1 untuk v2. Urutan tepi (v1. v3), (v3. v3), (v3. v1) Adalah sebuah siklus, tetapi tidak sederhana satu. Jika tepi grafik diberi label, kita bisa bicara tentang label dari berjalan. label ini adalah urutan label tepi ditemui ketika jalan dilalui. Akhirnya, tepi dari titik ke dirinya sendiri disebutputaran. Di Gambar 1.1, Ada loop pada vertex v3. Pada beberapa kesempatan, kami akan merujuk pada suatu algoritma untuk menemukan semua jalur sederhana antara dua simpul diberikan (atau semua siklus sederhana didasarkan pada puncak). Jika kita tidak menyibukkan diri dengan efisiensi, kita dapat menggunakan mengikuti metode yang jelas. Mulai dari titik yang diberikan, mengatakanvsaya, Daftar semua tepi keluar (vsaya. vk), (vsaya. vl), .... Pada titik ini, kita memiliki semua jalur panjang satu awal di vsaya. Untuk semua simpulvk. vl. ... sehingga tercapai, kita daftar semua keluar tepi selama mereka tidak mengarah ke setiap simpul sudah digunakan di jalan kita

sedang membangun. Setelah kita melakukan ini, kita akan memiliki semua jalur yang sederhana panjang dua berasal di vsaya. Kami terus ini sampai semua kemungkinan dicatat untuk. Karena hanya ada jumlah terbatas simpul, kita akan akhirnya daftar jalur semua sederhana dimulai pada vsaya. Dari ini kita memilih orang-orang berakhir di vertex diinginkan. Pohon jenis tertentu dari grafik. Sebuah pohon adalah grafik diarahkan yang memiliki tidak ada siklus dan yang memiliki satu titik yang berbeda, yang disebut akar, Seperti yang ada tepat satu jalur dari akar ke setiap simpul lainnya. definisi ini menyiratkan bahwa akar tidak memiliki tepi yang masuk dan bahwa ada beberapa simpul tanpa tepi keluar. Ini disebutDaun-daun pohon. Jika ada kelebihan dari vsaya untuk vj, kemudian vsaya dikatakan menjadi induk dari vj, dan vj itu anak dari vsaya. Itutingkat terkait dengan setiap simpul adalah jumlah tepi di jalur dari akar ke simpul. Itutinggi pohon adalah jumlah tingkat terbesar dari titik apapun. Istilah-istilah ini diilustrasikan dalam Gambar 1.2. Di kali, kita ingin mengasosiasikan pemesanan dengan node pada setiap tingkat; dalam kasus seperti kita berbicara tentang pohon memerintahkan. Rincian lebih lanjut tentang grafik dan pohon dapat ditemukan di sebagian besar buku-buku tentang matematika diskrit.

Teknik bukti Merupakan syarat penting untuk membaca teks ini adalah kemampuan untuk mengikuti bukti. Dalam argumen matematika, kami mempekerjakan aturan umum penalaran deduktif, dan banyak bukti hanya urutan seperti tangga. Dua teknik bukti khusus yang digunakan begitu sering bahwa itu adalah yang tepat untuk meninjau mereka secara singkat. ini adalahbukti dengan induksi dan

bukti dengan kontradiksi. GAMBAR 1.2

Induksi adalah teknik dimana kebenaran dari sejumlah pernyataan dapat disimpulkan dari kebenaran beberapa kasus tertentu. Misalkan kita memiliki urutan laporan P1. P2. ... kami ingin membuktikan untuk menjadi kenyataan. Selanjutnya, misalkan juga bahwa berikut ini berlaku: 1. Untuk beberapa k ≥ 1, kita tahu bahwa P1. P2. ..., Pk adalah benar. 2. Masalahnya adalah seperti bahwa untuk setiap n ≥ k, Kebenaran P1. P2. ..., Pn menyiratkan kebenaran Pn1. Kita kemudian dapat menggunakan induksi untuk menunjukkan bahwa setiap pernyataan dalam urutan ini adalah benar. Dalam bukti dengan induksi, kami berpendapat sebagai berikut: Dari Kondisi 1 kami tahu bahwa pertama k pernyataan yang benar. Kemudian Kondisi 2 memberitahu kita bahwa Pk1 juga harus benar. Tapi sekarang kita tahu bahwa yang pertamak + 1 pernyataan yang benar, kita dapat menerapkan Kondisi 2 lagi untuk mengklaim bahwa Pk2 harus benar, dan sebagainya. Kita perlu secara eksplisit terus argumen ini, karena pola yang jelas. Rantai penalaran dapat diperpanjang untuk pernyataan. Oleh karena itu, setiap pernyataan benar. Laporan mulai P1. P2. ... Pk disebut dasar dari induksi. Langkah menghubungkanPn dengan Pn1 disebut langkah induktif. Langkah induktif umumnya dibuat lebih mudah oleh asumsi induktif bahwa P1. P2. ..., Pn yang benar, maka berpendapat bahwa kebenaran pernyataan ini menjamin kebenaran Pn1. Dalam argumen induktif formal, kami menampilkan semua tiga bagian secara eksplisit. CONTOH 1.5 Sebuah pohon biner adalah pohon di mana tidak ada orang tua dapat memiliki lebih dari dua anak-anak. Buktikan bahwa pohon biner tinggin memiliki paling banyak 2n Daun-daun.

Bukti: Jika kita menunjukkan jumlah maksimum daun dari pohon biner tinggi n oleh l (n), Maka kita ingin menunjukkan bahwa l (n) ≤ 2n. Dasar: Jelas l (0) = 1 = 20 karena pohon tinggi 0 dapat memiliki node selain akar, yaitu, ia memiliki paling banyak satu daun. Asumsi induktif: l (saya) ≤ 2saya, untuk saya = 0, 1, ..., n. (1.4) Langkah induktif: Untuk mendapatkan sebuah pohon biner tinggi n + 1 dari salah satu tinggi n, Kita dapat membuat, paling banyak, dua daun di tempat masingmasing sebelumnya satu. Karena itu,

l (n 1) = 2l (n). Sekarang, dengan menggunakan asumsi induktif, kita mendapatkan l (n 1) ≤ 2 × 2n = 2n1. Jadi, jika klaim kita benar untuk n, Itu juga harus berlaku untuk n + 1. Karena n dapat menjadi nomor apapun, pernyataan itu harus benar untuk semua n. Di sini kami memperkenalkan simbol ▪ yang digunakan dalam buku ini untuk menunjukkan akhir bukti. penalaran induktif bisa sulit untuk dipahami. Ini membantu untuk melihat hubungan erat antara induksi dan rekursi dalam pemrograman. Untuk Misalnya, definisi rekursif dari suatu fungsi f (n), Di mana n adalah setiap bilangan bulat positif, sering memiliki dua bagian. Satu melibatkan definisif (n 1) dalam hal f (n), f (n - 1), ..., f (1). Ini sesuai dengan induktif langkah. Bagian kedua adalah “melarikan diri” dari rekursi, yang dicapai dengan mendefinisikan f (1), f (2), ..., f (k) Nonrecursively. Ini sesuai dengan dasar induksi. Seperti di induksi, rekursi memungkinkan kita untuk menarik kesimpulan tentang semua contoh dari masalah, mengingat hanya beberapa nilai awal dan menggunakan sifat rekursif dari masalah. Kadang-kadang, masalah terlihat kesulitan sampai kita melihat itu hanya kanan cara. Sering melihat secara rekursif menyederhanakan hal-hal sangat. CONTOH 1.6 Satu set l1. l2. ..., ln saling berpotongan garis lurus membagi

Pesawat ke sejumlah daerah yang dipisahkan. Sebuah garis tunggal membagi Pesawat menjadi dua bagian, dua baris menghasilkan empat wilayah, tiga baris membuat tujuh wilayah, dan sebagainya. Hal ini mudah diperiksa secara visual sampai tiga garis, tetapi sebagai jumlah baris meningkat menjadi sulit untuk menemukan sebuah pola. Mari kita mencoba untuk memecahkan masalah ini secara rekursif. Melihat Gambar 1.3 untuk melihat apa yang terjadi jika kita menambahkan baris baru ln1 untuk ada n baris. Wilayah di sebelah kiril1 dibagi menjadi dua baru daerah, sehingga merupakan daerah di sebelah kiri l2, Dan seterusnya sampai kita sampai ke baris terakhir. Pada baris terakhir, wilayah di sebelah kananln juga dibagi. Masing-masing dari n persimpangan kemudian menghasilkan satu wilayah baru, dengan satu ekstra di akhir. Jadi, jika kita membiarkanSEBUAH(n) Menunjukkan jumlah daerah dihasilkan oleh n garis, kita melihat bahwa

SEBUAH(n 1) = SEBUAH(n) + n 1, n = 1, 2, .... dengan SEBUAH(1) = 2. Dari rekursi sederhana ini kita kemudian menghitung SEBUAH(2) = 4, SEBUAH(3) = 7, SEBUAH(4) = 11, dan seterusnya. Untuk mendapatkan rumus untuk SEBUAH(n) Dan untuk menunjukkan bahwa itu adalah benar, kita menggunakan induksi. Jika kita menduga bahwa kemudian GAMBAR 1.3

membenarkan langkah induktif. dasar mudah diperiksa, menyelesaikan argumen. Dalam contoh ini kita telah sedikit kurang formal dalam mengidentifikasi dasar, asumsi induktif, dan langkah induktif, tetapi mereka ada dan sangat penting. Untuk menjaga diskusi berikutnya kami menjadi terlalu formal, kita akan umumnya lebih memilih gaya contoh kedua ini. Namun, jika Anda mengalami kesulitan dalam mengikuti atau membangun bukti, kembali ke bentuk yang lebih eksplisit contoh 1.5.

Bukti dengan kontradiksi adalah teknik lain yang kuat yang sering bekerja ketika segala sesuatu yang lain gagal. Misalkan kita ingin membuktikan bahwa beberapa pernyataan P adalah benar. Kami kemudian berasumsi, untuk saat ini, yangP adalah palsu dan melihat di mana asumsi yang menuntun kita. Jika kita sampai pada kesimpulan bahwa kita tahu adalah salah, kita bisa meletakkan menyalahkan asumsi awal dan menyimpulkan bahwa P harus benar. Berikut ini adalah contoh klasik dan elegan. CONTOH 1.7 Sejumlah rasional adalah nomor yang dapat dinyatakan sebagai rasio dua bilangan bulat n dan m yang seperti itu n dan m tidak memiliki faktor umum. A real jumlah yang tidak rasional dikatakan tidak rasional. Tampilkan yang irasional. Seperti dalam semua bukti oleh kontradiksi, kita asumsikan sebaliknya dari apa yang kami ingin menunjukkan. Di sini kita mengasumsikan bahwa adalah bilangan rasional sehingga dapat ditulis sebagai (1.5) dimana n dan m adalah bilangan bulat tanpa faktor umum. menata ulang (1,5), kita memiliki 2m2 = n2. Karena itu, n2 harus bahkan. Ini berarti bahwan Bahkan, sehingga kita bisa menulis n = 2k atau 2m2 = 4k2. dan m2 = 2k2. Karena itu, m bahkan. Tapi ini bertentangan asumsi kita bahwan dan m tidak memiliki faktor umum. Demikian,m dan n di (1,5) tidak bisa eksis dan bukan bilangan rasional. Contoh ini menunjukkan esensi dari bukti dengan kontradiksi. Oleh membuat asumsi tertentu kita menyebabkan kontradiksi dari asumsi atau fakta diketahui. Jika semua langkah di argumen kita secara logis suara, kita harus menyimpulkan bahwa asumsi awal kami adalah palsu.

LATIHAN 1. Dengan S1 = {2, 3, 5, 7}, S2 = {2, 4, 5, 8, 9}, dan U = {1: 10}, menghitung . 2. Dengan S1 = {2, 3, 5, 7} dan S2 = {2, 4, 5, 8, 9}, menghitung S1 × S2 dan S2 × S1. 3. Untuk S = {2, 5, 6, 8} dan T = {2, 4, 6, 8}, menghitung |S ∩ T| + |S ∪ T|. 4. Apa hubungan antara dua set S dan T harus memegang sehingga |S ∪T | = |S| + |T |? 5. Tunjukkan bahwa untuk semua set S dan T,. 6. Buktikan hukum DeMorgan, Persamaan (1.2) dan (1.3), dengan menunjukkan bahwa jika elemen x adalah di set di satu sisi kesetaraan, maka harus juga berada di set di sisi lain dari kesetaraan. 7. Menunjukkan bahwa jika S1 ⊆ S2, kemudian . 8. Menunjukkan bahwa S1 = S2 jika dan hanya jika S1 ∪ S2 = S1 ∩ S2. 9. Gunakan induksi pada ukuran S untuk menunjukkan bahwa jika S adalah himpunan berhingga, maka | 2S| = 2|S|. 10. Menunjukkan bahwa jika S1 dan S2 adalah himpunan berhingga dengan |S1| =n dan |S2| =m. kemudian | S1 ∪ S2| ≤n + m. 11. Jika S1 dan S2 adalah set terbatas, menunjukkan bahwa |S1 × S2| = |S1||S2|. 12. Pertimbangkan hubungan antara dua set yang didefinisikan oleh S1 ≡ S2 jika dan hanya jika | S1| = |S2|. Tunjukkan bahwa ini merupakan relasi ekivalen. 13. Kadang-kadang, kita perlu menggunakan serikat dan persimpangan simbol dalam cara yang analog dengan tanda penjumlahan Σ. kita mendefinisikan dengan notasi analog untuk persimpangan beberapa set. Dengan notasi ini, undang-undang yang DeMorgan jenderal ditulis sebagai dan Buktikan identitas ini ketika P adalah himpunan berhingga. 14. Menunjukkan bahwa 15. Menunjukkan bahwa S1 = S2 jika dan hanya jika

HAI

16. Menunjukkan bahwa 17. Menunjukkan bahwa hukum distributif S1 ∩ (S2 ∪ S3) = (S1 ∩ S2) ∪ (S1 ∩ S3) berlaku untuk set. 18. Menunjukkan bahwa S1 × (S2 ∪ S3) = (S1 × S2) ∪ (S1 × S3). 19. Berikan kondisi di S1 dan S2 perlu dan cukup untuk memastikan bahwa S1 = (S1 ∪ S2) - S2. 20. Gunakan kesetaraan didefinisikan dalam contoh 1.4 untuk partisi himpunan {2, 4, 5, 6, 9, 22, 24, 25, 31, 37} ke dalam kelas kesetaraan. 21. Menunjukkan bahwa jika f (n) = HAI (g (n)) Dan g (n) = HAI (f (n)), kemudian f (n) = Θ(g (n)). 22. Tunjukkan bahwa 2n = HAI (3n), Tapi 2n ≠ Θ(3n). 23. Menunjukkan bahwa urutan-of-besarnya hasil sebagai berikut terus. (Sebuah) n2 + 5 log n = HAI (n2). (B) 3n = HAI (n!). (C) n! =HAI (nn). 24. Menunjukkan bahwa (n3 - 2n)/(n 1) = Θ(n2). 25. Menunjukkan bahwa tetapi tidak HAI(n2). 26. Apa yang salah dengan argumen berikut? x = HAI(n4), y = HAI(n2), karena itu x / y = HAI(n2). 27. Apa yang salah dengan argumen berikut? x = Θ(n4), y = Θ(n2), Oleh karena itu. 28. Buktikan bahwa jika f (n) = HAI (g (n)) Dan g (n) = HAI (h (n)), kemudian f (n) = HAI (h (n)). 29. Menunjukkan bahwa jika f (n) = HAI (n2) dan g (n) = HAI (n3), kemudian f (n) + g (n) = HAI (n3) dan f (n) g (n) = HAI (n5). Dalam hal ini, apakah benar bahwa g (n) / f (n) = HAI (n)? 30. Asumsikan bahwa f (n) = 2n2 + n dan g (n) = HAI (n2). Apa yang salah dengan argumen berikut? f (n) = HAI (n2) + HAI (n),

yang seperti itu

f (n) - g (n) = HAI (n2) + HAI (n) - HAI (n2). Karena itu,

f (n) - g (n) = HAI (n). 31. Menunjukkan bahwa jika f(n) = Θ(log2 n), kemudian f(n) = Θ(log10 n). 32. Menggambar grafik dengan simpul {v1. v2. v3} Dan tepi {(v1. v1), (v1. v2), (v2. v3), (v2. v1), (v3. v1)}. Menghitung semua siklus dengan basis v1. 33. Membangun grafik dengan lima simpul, sepuluh tepi, dan tidak ada siklus. 34. Membiarkan G = (VE) Menjadi grafik apapun. Buktikan klaim berikut: Jika ada setiap berjalan antara vsaya ∈ V dan vj ∈ V, Maka harus ada sederhana jalan panjang tidak lebih besar dari |V | - 1 antara dua simpul tersebut. 35. Pertimbangkan grafik di mana ada paling banyak satu ujung antara setiap dua simpul. Menunjukkan bahwa di bawah kondisi ini grafik dengann simpul memiliki paling n2 tepi. 36. Menunjukkan bahwa 37. Menunjukkan bahwa 38. Buktikan bahwa untuk semua n ≥ 4 ketimpangan 2n
f(n + 2) = f(n + 1) + f(n), n = 1, 2, .... dengan f(1) = 1, f(2) = 1. Tunjukkan bahwa (Sebuah) f(n) = HAI(2n), (B) f(n) = Ω (1,5n). 40. Tunjukkan bahwa √8 bukan nomor rasional. 41. Tunjukkan bahwa 2 - adalah tidak rasional. 42. Tunjukkan bahwa adalah tidak rasional. 43. Membuktikan atau menyangkal pernyataan berikut. (A) Jumlah rasional dan bilangan irasional harus irasional. (B) jumlah dari dua angka irasional positif harus rasional. (C) Produk yang rasional nol dan bilangan irasional harus tidak rasional. 44. Menunjukkan bahwa setiap bilangan bulat positif dapat dinyatakan sebagai produk dari bilangan prima.

45. Buktikan bahwa himpunan semua bilangan prima adalah tak terbatas. 46. Sepasang utama terdiri dari dua bilangan prima yang berbeda dengan dua. Ada banyak pasangan prima, misalnya, 11 dan 13, 17 dan 19. kembar tiga Perdana tiga angka n ≥ 2, n + 2, n + 4 yang semuanya prima. Menunjukkan bahwa satu-satunya triplet utama adalah (3, 5, 7). https://sanet.st/blogs/polatebooks/

1.2 TIGA KONSEP DASAR Tiga ide-ide dasar adalah tema utama buku ini: bahasa. tata bahasa, dan automata. Dalam program studi kami, kami akan mengeksplorasi banyak hasil tentang konsep-konsep ini dan tentang hubungan mereka satu sama lain. Pertama, kita harus memahami arti dari istilah.

Bahasa Kita semua akrab dengan gagasan bahasa alami, seperti bahasa Inggris dan Perancis. Namun, kebanyakan dari kita mungkin akan merasa sulit untuk mengatakan dengan tepat apa kata “bahasa” berarti. Kamus mendefinisikan istilah informal sebagai sistem yang cocok untuk ekspresi ide-ide tertentu, fakta, atau konsep, termasuk satu set simbol dan aturan untuk manipulasi mereka. sementara ini memberi kita gambaran intuitif apa bahasa, itu tidak cukup sebagai definisi untuk studi bahasa formal. Kita perlu definisi yang tepat untuk istilah ini. Kita mulai dengan yang terbatas, set nonempty Σ simbol, yang disebut alfabet. Dari simbol individu kita membangun string, Yang terbatas urutan simbol dari alfabet. Sebagai contoh, jika alfabetΣ = {a, b}, kemudian abab dan aaabbba adalah string pada Σ. Dengan beberapa pengecualian, kita akan menggunakan huruf kecil a, b, c, ... untuk unsur-unsur Σ dan u, v, w ... string nama. Kami akan menulis, misalnya,

w = abaaa untuk menunjukkan bahwa string bernama w memiliki nilai tertentu abaaa. Itu rangkaian dari dua string w dan v adalah string yang diperoleh menambahkan simbol-simbol v ke ujung kanan w, Yaitu, jika

w = Sebuah1Sebuah2 ··· Sebuahn dan

v = b1b2 ··· bm. maka gabungan dari w dan v, Dilambangkan dengan wv, aku s wv = Sebuah1Sebuah2 ··· Sebuahnb1b2 ··· bm. Itu membalikkan string diperoleh dengan menulis simbol terbalik memesan; jikaw adalah string seperti yang ditunjukkan di atas, maka kebalikannya wR aku s wR = Sebuahn ··· Sebuah2Sebuah1. Itu panjangnya string w, Dinotasikan dengan |w|, Adalah jumlah simbol dalam string. Kami akan sering perlu untuk merujuk padastring kosong, yang mana string tanpa simbol sama sekali. Ini akan dilambangkan denganλ. Pengikut hubungan sederhana |λ| = 0, λw = wλ = w berlaku untuk semua w. String simbol berturut-turut dalam beberapa w dikatakan menjadi substring dari w. Jika

w = vu. maka substring v dan u dikatakan menjadi awalan dan akhiran dari w. masing-masing. Sebagai contoh, jikaw = abbab, kemudian {λ, Sebuah, ab, abb, abba, abbab} aku s himpunan semua prefiks dari w, sedangkan bab, ab, b adalah beberapa akhiran nya. Sifat-sifat sederhana dari string, seperti panjang mereka, sangat intuitif dan mungkin perlu sedikit elaborasi. Sebagai contoh, jikau dan v adalah string, maka panjang Rangkaian mereka adalah jumlah panjang individu, yang aku s, | uv| = |u| + |v|. (1.6) Tapi meskipun hubungan ini jelas, hal ini berguna untuk dapat membuat itu tepat dan membuktikannya. Teknik-teknik untuk melakukan hal yang penting dalam lebih situasi yang rumit. CONTOH 1.8

Tunjukkan bahwa (1,6) berlaku untuk setiap u dan v. Untuk membuktikan ini, pertama kita perlu definisi panjang string. Kami membuat definisi tersebut dalam rekursif fashion dengan

| a| = 1, | wa| = |w| 1, untuk semua Sebuah ∈ Σ dan w setiap string pada Σ. Definisi ini formal Pernyataan dari pemahaman intuitif kita dari panjang string: The panjang simbol tunggal adalah satu, dan panjang setiap string bertambah satu jika kita menambahkan simbol lain untuk itu. Dengan formal definisi, kami siap untuk membuktikan (1,6) oleh karakter induksi. Menurut definisi, (1,6) berlaku untuk semua u dari setiap panjang dan semua v panjang 1, sehingga kita memiliki dasar. Sebagai asumsi induktif, kami mengambil (1,6) berlaku untuk semua u dari setiap panjang dan semua v panjang 1, 2, ..., n. sekarang ambil apa saja v panjang n + 1 dan menuliskannya sebagai v = wa. Kemudian,

| v| = |w| 1, | uv| = |uwa| = |uw| 1. Dengan hipotesis induktif (yang berlaku sejak w adalah panjang n),

| uw| = |u| + |w| yang seperti itu

| uv| = |u| + |w| 1 = |u| + |v|. Oleh karena itu, (1,6) berlaku untuk semua u dan semua v panjang sampai dengan n1, menyelesaikan langkah induktif dan argumen. Jika w adalah string, maka wn singkatan string yang diperoleh dengan mengulangi wn waktu. Sebagai kasus khusus, kita mendefinisikan w0 = λ. untuk semua w. Jika Σ adalah alfabet, maka kita gunakan Σ* Untuk menunjukkan set string yang diperoleh dengan menggabungkan nol atau lebih simbol-simbol dari Σ. SetΣ* selalu mengandung λ. Untuk mengecualikan string kosong, kita mendefinisikan

Σ+ = Σ * - {λ}. Sementara Σ terbatas oleh asumsi, Σ* dan Σ+ selalu terbatas karena ada ada batasan pada panjang string di set ini. Sebuah bahasa didefinisikan sangat umum sebagai bagian dari Σ*. Sebuah string dalam bahasaL akan disebut kalimat dari L. Definisi ini cukup luas; setiap set string pada alfabet Σ dapat dianggap bahasa. Nanti kita akan belajar metode-metode yang bahasa tertentu dapat didefinisikan dan dijelaskan; ini akan memungkinkan kita untuk memberikan beberapa struktur konsep agak luas ini. Untuk saat ini, meskipun, kita hanya akan melihat pada contoh-contoh spesifik beberapa. CONTOH 1.9 Membiarkan Σ = {a, b}. Kemudian

Σ* = {λ, A, b, aa, ab, ba, bb, aaa, aab, ...}. Set

{A, aa, aab} adalah bahasa pada Σ. Karena memiliki jumlah terbatas kalimat, kita sebut itu bahasa yang terbatas. Set L = {Sebuahnbn : n ≥ 0} juga merupakan bahasa pada Σ. stringaabb dan aaaabbbb di bahasa L, Tapi string abb tidak di L. Bahasa ini adalah tak terbatas. Kebanyakan bahasa yang menarik tak terbatas. Karena bahasa adalah set, serikat, persimpangan, dan perbedaan dari dua bahasa segera ditetapkan. Komplemen dari suatu bahasa adalah didefinisikan sehubungan dengan Σ*; yaitu, komplemen dariL aku s Kebalikan dari bahasa adalah himpunan semua pembalikan string, yang adalah, LR = {wR : w ∈ L}. Rangkaian dua bahasa L1 dan L2 adalah himpunan semua string diperoleh dengan menggabungkan unsur dari L1 dengan unsur L2; secara khusus, L1L2 = {xy : x ∈ L1. y ∈ L2}. kita mendefinisikan Ln sebagai L concatenated dengan dirinya sendiri n kali, dengan kasus-kasus khusus L0 = {λ} dan

L1 = L untuk setiap bahasa L. Akhirnya, kita mendefinisikan Bintang-penutupan dari bahasa sebagai L* = L0 ∪ L1 ∪ L2 ··· dan penutupan positif sebagai L+ = L1 ∪ L2 ···. CONTOH 1.10 Jika L = {Sebuahnbn : n ≥ 0}, kemudian L2 = {SebuahnbnSebuahmbm : n ≥ 0, m ≥ 0}. Perhatikan bahwa n dan m di atas adalah tidak berhubungan; stringaabbaaabbb aku s di L2. Kebalikan dari L mudah dijelaskan dalam notasi set sebagai LR = {bnSebuahn : n ≥ 0}, tapi itu jauh lebih sulit untuk menjelaskan atau L* cara ini. Beberapa mencoba akan cepat meyakinkan Anda tentang keterbatasan notasi yang ditetapkan untuk spesifikasi bahasa yang rumit.

tata bahasa Untuk mempelajari bahasa matematis, kita perlu sebuah mekanisme untuk menggambarkan mereka. bahasa sehari-hari adalah tidak tepat dan ambigu, sehingga tidak resmi deskripsi dalam bahasa Inggris sering tidak memadai. set notasi yang digunakan dalam contoh 1.9 dan 1.10 lebih cocok, tapi terbatas. Seperti kita lanjutkan kita akan belajar tentang beberapa mekanisme bahasa-definisi yang berguna dalam keadaan yang berbeda. Di sini kami memperkenalkan salah satu umum dan kuat, gagasan tentang tatabahasa. Sebuah tata bahasa untuk bahasa Inggris memberitahu kita apakah tertentu

Kalimat terbentuk dengan baik atau tidak. Aturan khas tata bahasa Inggris adalah” kalimat dapat terdiri dari frase kata benda yang diikuti oleh predikat.”Lebih ringkas kita menulis ini sebagai

→ <predikat>. dengan interpretasi yang jelas. Hal ini, tentu saja, tidak cukup untuk menangani dengan kalimat yang sebenarnya. Kita sekarang harus memberikan definisi untuk yang baru konstruksi diperkenalkan dan <predikat>. Jika kita melakukannya dengan

→ <artikel> . <predikat> → . dan jika kita kaitkan kata-kata yang sebenarnya “a” dan “” dengan <artikel>, “Anak” dan “anjing” dengan , Dan “berjalan” dan “jalan-jalan” dengan , Maka tata memberitahu kita bahwa kalimat “anak laki-laki berjalan” dan “anjing berjalan” yang benar terbentuk. Jika kita untuk memberikan tata bahasa lengkap, maka secara teori, setiap kalimat yang tepat dapat dijelaskan dengan cara ini. Contoh ini menggambarkan definisi konsep umum dalam hal yang sederhana. Kita mulai dengan konsep tingkat atas, di sini, dan berturut-turut mengurangi ke blok bangunan tereduksi dari bahasa. Generalisasi ide-ide ini membawa kita ke tata bahasa formal. DEFINISI 1.1 Sebuah tata bahasa G didefinisikan sebagai quadruple

G = (V, T, S, P), dimana V adalah himpunan berhingga obyek yang disebut variabel. T adalah himpunan berhingga obyek yang disebut simbol terminal. S ∈ V adalah simbol khusus yang disebut mulai variabel, P adalah himpunan berhingga produksi. Ini akan diasumsikan tanpa menyebutkan lebih lanjut bahwa set V dan T adalah tidak kosong dan menguraikan.

Aturan produksi adalah jantung dari tata bahasa; mereka menentukan bagaimana tata mengubah satu string menjadi lain, dan melalui ini mereka mendefinisikan bahasa terkait dengan tata bahasa. Dalam diskusi kami, kami akan menganggap bahwa semua aturan produksi dalam bentuk

x → y. dimana x adalah unsur (V ∪ T)+ dan y adalah di (V ∪ T) *. produksi diterapkan dengan cara berikut: Mengingat string w form

w = uxv. kita mengatakan produksi x → y berlaku untuk string ini, dan kami dapat menggunakannya untuk menggantikan x dengan y, Dengan demikian memperoleh string baru

z = uyv. Hal ini ditulis sebagai

w ⇒ z. Kami mengatakan bahwa w atau diperoleh z atau itu z berasal dari w. string berturut-turut adalah berasal dengan menerapkan produksi dari tata bahasa dalam rangka sewenang-wenang. SEBUAH produksi dapat digunakan setiap kali itu berlaku, dan dapat diterapkan sebagai sesering yang diinginkan. Jika w1 ⇒ w2 ⇒ ··· ⇒ wn. kita mengatakan bahwa w1 atau diperoleh wn dan tulis Itu * menunjukkan bahwa jumlah yang tidak ditentukan langkah-langkah (termasuk nol) dapat diambil untuk menurunkan wn dari w1. Dengan menerapkan aturan produksi dalam urutan yang berbeda, diberikan tata bahasa biasanya dapat menghasilkan banyak string. Himpunan semua string terminal tersebut bahasa ditentukan atau yang dihasilkan oleh tata bahasa. DEFINISI 1.2 Membiarkan G = (V, T, S, P) Menjadi tata bahasa. Kemudian set

adalah bahasa yang dihasilkan oleh G. Jika w ∈ L (G), Maka urutan S ⇒ w1 ⇒ w2 ⇒ ··· ⇒ wn ⇒ w adalah penurunan kalimat w. stringS, w1. w2. ..., wn, yang berisi variabel serta terminal, disebut bentuk sentensial dari penurunan. CONTOH 1.11 Pertimbangkan tata bahasa

G = ({S}, {a, b}, S, P), dengan P diberikan oleh S → ASB. S → λ. Kemudian

S ⇒ ASB ⇒ aaSbb ⇒ aabb. sehingga kita dapat menulis string aabb adalah kalimat dalam bahasa yang dihasilkan oleh G, sedangkan aaSbb adalah bentuk sentensial. Sebuah tata bahasa G benar-benar mendefinisikan L (G), Tetapi mungkin tidak mudah untuk mendapatkan deskripsi yang sangat eksplisit bahasa dari tata bahasa. Di sini, bagaimanapun, jawabannya adalah cukup jelas. Hal ini tidak sulit untuk berspekulasi bahwa L (G) = {Sebuahnbn : n ≥ 0}, dan mudah untuk membuktikannya. Jika kita melihat bahwa aturanS → ASB aku s rekursif, bukti dengan induksi siap menunjukkan itu sendiri. Kami pertunjukan pertama bahwa semua bentuk sentensial harus memiliki bentuk wsaya = SebuahsayaSbsaya. (1.7) Misalkan (1,7) berlaku untuk semua bentuk sentensial wsaya panjang 2saya 1 atau kurang. Untuk mendapatkan bentuk sentensial lain (yang bukan kalimat), kita bisa hanya berlaku produksi S → ASB. Ini membuat kita SebuahsayaSbsaya ⇒ Sebuahsaya1Sbsaya1.

sehingga setiap bentuk sentensial panjang 2saya + 3 juga dari bentuk (1,7). Sejak (1,7) jelas benar untuk saya = 1, memegang dengan induksi untuk semua saya. Akhirnya, untuk mendapatkan sebuah kalimat, kita harus menerapkan produksi S → λ, dan kita Lihat itu mewakili semua derivasi mungkin. Demikian,G dapat memperoleh hanya string formulir Sebuahnbn. Kami juga harus menunjukkan bahwa semua string dari formulir ini dapat diturunkan. Ini mudah; kita hanya menerapkanS → ASB sebanyak yang diperlukan, diikuti oleh S → λ. CONTOH 1.12 Cari tata bahasa yang menghasilkan L = {Sebuahnbn1 : n ≥ 0}. Ide di balik contoh sebelumnya dapat diperpanjang untuk kasus ini. Semua kita perlu lakukan adalah menghasilkan tambahan b. Hal ini dapat dilakukan dengan produksi S → ab, Dengan produksi lain yang dipilih sehingga SEBUAH bisa berasal bahasa pada contoh sebelumnya. Penalaran dalam mode ini, kita mendapatkan tata bahasa G = ({S, A}, {a, b}, S, P), Dengan produksi S → ab. SEBUAH → Aab. SEBUAH → λ. Turunkan kalimat tertentu beberapa untuk meyakinkan diri sendiri bahwa ini bekerja. Contoh sebelumnya adalah yang cukup mudah, sehingga argumen yang ketat mungkin tampak berlebihan. Tetapi sering tidak begitu mudah untuk menemukan tata bahasa untuk bahasa dijelaskan dengan cara yang informal atau memberikan intuitif karakterisasi bahasa didefinisikan oleh tata bahasa. Untuk menunjukkan bahwa bahasa tertentu memang dihasilkan oleh tata bahasa tertentu G, Kita harus mampu menunjukkan (a) bahwa setiap w ∈ L dapat diturunkan dari S menggunakan G dan B)

bahwa setiap string yang begitu berasal di L. CONTOH 1.13 Mengambil Σ = {a, b}, dan biarkan nSebuah (w) dan nb (w) Menunjukkan jumlah Sebuah'S dan b'S dalam string w, Masing-masing. Kemudian tata bahasaG dengan produksi S → SS. S → λ. S → ASB. S → Bsa menghasilkan bahasa L = {w : nSebuah (w) = nb (w)}. Klaim ini tidak begitu jelas, dan kami perlu menyediakan meyakinkan argumen. Pertama, jelas bahwa setiap bentuk sentensial G memiliki jumlah yang sama dari Sebuah'S dan b'S, karena satu-satunya produksi yang menghasilkan Sebuah, yaitu S → ASB dan S → Bsa, Secara bersamaan menghasilkan b. Oleh karena itu, setiap unsur L (G) Adalah di L. Ini adalah sedikit lebih sulit untuk melihat bahwa setiap string dalamL dapat diturunkan dengan G. Mari kita mulai dengan melihat masalah secara garis besar, mengingat berbagai bentuk w ∈ L bisa memperoleh. Seharusnyaw dimulai dengan Sebuah dan berakhir dengan b. Kemudian memiliki bentuk w = aw1b. dimana w1 juga di L. Kami bisa memikirkan hal ini sebagai berasal dimulai dengan

S ⇒ ASB jika S memang berasal string apapun di L. Argumen yang sama bisa dibuat jika w dimulai dengan b dan berakhir dengan Sebuah. Tapi ini tidak mengurus semua kasus, karena string di L dapat dimulai dan diakhiri dengan simbol yang sama. Jika kita menuliskan serangkaian jenis ini, mengatakan aabbba, Kita melihat bahwa hal itu dapat dianggap sebagai gabungan dari dua string yang lebih pendek aabb dan ba.

yang keduanya di L. Apakah ini benar secara umum? Untuk menunjukkan bahwa ini adalah memang begitu, kita dapat menggunakan argumen berikut: Misalkan, mulai di ujung kiri string, kita menghitung 1 untuk Sebuah dan -1 untuk b. Jika sebuah tali w dimulai dan berakhir dengan Sebuah, Maka hitungan akan +1 setelah simbol paling kiri dan -1 segera sebelum yang paling kanan. Oleh karena itu, menghitung harus melalui nol suatu tempat di tengah string, menunjukkan bahwa string tersebut harus memiliki bentuk w = w1w2. di mana kedua w1 dan w2 berada di L. Kasus ini dapat diurus oleh produksi S → SS. Setelah kita melihat argumen intuitif, kami siap untuk melanjutkan lebih ketat. Sekali lagi kita menggunakan induksi. Asumsikan bahwa semuaw ∈ L dengan | w| ≤ 2n dapat diturunkan dengan G. mengambilw ∈ L panjang 2n 2. Jikaw = aw1b, kemudian w1 adalah di L, Dan |w1| = 2n. Oleh karena itu, dengan asumsi, Kemudian adalah mungkin, dan w dapat diturunkan dengan G. Jelas, argumen yang sama dapat dilakukan jika w = bw1Sebuah. Jika w tidak dari formulir ini, yaitu, jika dimulai dan berakhir dengan sama simbol, maka penghitungan argumen memberitahu kita bahwa itu harus memiliki bentuk w = w1w2, dengan w1 dan w2 baik dalam L dan panjang kurang dari atau sama dengan 2n. Oleh karena itu sekali lagi kita melihat bahwa adalah mungkin. Karena asumsi induktif jelas puas n = 1, kita memiliki dasar, dan klaim ini berlaku untuk semua n, Menyelesaikan argumen kita. Biasanya, bahasa tertentu memiliki banyak tata bahasa yang menghasilkan itu. Bahkan meskipun tata bahasa ini berbeda, mereka setara dalam arti. Kami mengatakan bahwa dua tata bahasa G1 dan G2 adalah setara jika mereka menghasilkan bahasa yang sama, yaitu, jika

L (G1) = L (G2). Seperti yang akan kita lihat nanti, itu tidak selalu mudah untuk melihat apakah dua tata bahasa yang setara. CONTOH 1.14 Pertimbangkan tata bahasa G1 = ({SEBAGAI}, {a, b}, S, P1), Dengan P1 yang terdiri dari produksi S → Aab|λ. SEBUAH → Aab|λ. Di sini kami memperkenalkan notasi singkat yang nyaman di mana beberapa aturan produksi dengan sisi kiri yang sama ditulis pada yang sama line, dengan sisi kanan alternatif dipisahkan dengan |. Pada notasi ini S → Aab|λ singkatan dua produksi S → Aab dan S → λ. tata bahasa ini setara dengan tata bahasa G di contoh 1.11. kesetaraan ini mudah untuk membuktikan dengan menunjukkan bahwa L (G1) = {Sebuahnbn : n ≥ 0}. Kami meninggalkan ini sebagai latihan.

automata Robot adalah model abstrak dari sebuah komputer digital. Dengan demikian, setiap automaton mencakup beberapa fitur penting. Ia memiliki mekanisme untuk membaca masukan. Ini akan diasumsikan bahwa input string lebih dari satu diberikan alfabet, ditulis pada file input, Yang otomat dapat membaca tapi tidak perubahan. GAMBAR 1.4

File input dibagi ke dalam sel, yang masing-masing dapat menampung satu simbol. Mekanisme input dapat membaca file input dari kiri ke kanan, satu simbol pada suatu waktu. Mekanisme masukan juga dapat mendeteksi akhir string input (dengan merasakan kondisi end-of-file). otomat bisa menghasilkan output dari beberapa bentuk. Ini mungkin memiliki sementarapenyimpanan alat, yang terdiri dari jumlah yang tidak terbatas dari sel, masing-masing mampu memegang tunggal simbol dari alfabet (tidak harus satu sama dengan input

alfabet). otomat dapat membaca dan mengubah isi dari sel penyimpanan. Akhirnya, robot memilikiunit kontrol, Yang dapat di salah satu dari jumlah terbatas negara internal, Dan yang bisa mengubah keadaan dalam beberapa cara yang ditetapkan. Gambar 1.4 menunjukkan representasi skematik dari automaton umum. Robot diasumsikan untuk beroperasi dalam jangka waktu diskrit. Apapun diberikan waktu, unit kontrol dalam beberapa keadaan internal, dan input Mekanisme memindai simbol tertentu pada file input. internal keadaan unit kontrol pada saat langkah selanjutnya ditentukan oleh NextState atau fungsi transisi. Fungsi transisi ini memberikan negara berikutnya dalam hal kondisi saat ini, simbol masukan saat ini, dan informasi saat ini dalam penyimpanan sementara. Selama transisi dari satu interval waktu ke depan, output yang dapat dihasilkan atau informasi dalam penyimpanan sementara berubah. Syaratkonfigurasi akan digunakan untuk merujuk kepada negara tertentu dari unit kontrol, file input, dan penyimpanan sementara. Transisi dari otomat dari satu konfigurasi untuk selanjutnya akan disebut pindah. model umum ini mencakup semua automata kita akan membahas dalam hal ini Book. Sebuah kontrol terbatas-negara akan umum untuk semua kasus tertentu, tetapi perbedaan akan timbul dari cara di mana output dapat diproduksi dan sifat dari penyimpanan sementara. Seperti yang akan kita lihat, sifat penyimpanan sementara mengatur kekuatan dari berbagai jenis automata. Untuk diskusi berikutnya, maka akan diperlukan untuk membedakan antara automata deterministik dan automata nondeterministic. SEBUAH otomat deterministik adalah satu di mana masing-masing bergerak secara unik ditentukan oleh konfigurasi saat ini. Jika kita mengetahui keadaan internal, input, dan isi dari penyimpanan sementara, kita dapat memprediksi perilaku masa depan robot persis. Dalam nondeterministic otomat, ini tidak begitu. Pada setiap titik, robot nondeterministic

mungkin memiliki beberapa bergerak mungkin, sehingga kita hanya bisa memprediksi satu set kemungkinan tindakan. Hubungan antara deterministik dan non-deterministik automata dari berbagai jenis akan memainkan peran penting dalam penelitian kami. Robot yang respon output terbatas sederhana “ya” atau “Tidak ada” disebut accepter. Disajikan dengan string input, sebuah accepter baik menerima string atau menolaknya. Sebuah robot yang lebih umum, mampu menghasilkan string dari simbol-simbol sebagai output, disebut transduser.

LATIHAN 1. Berapa banyak substring aab berada di wwRw, di mana w = aabbab? 2. Gunakan induksi pada n untuk menunjukkan bahwa |un| =n |u| untuk semua stringu dan semua n. 3. Kebalikan dari string, diperkenalkan secara informal di atas, dapat didefinisikan lebih tepatnya oleh aturan rekursif SebuahR = Sebuah. (wa)R = awR. untuk semua Sebuah ∈ __________Σ. w ∈ Σ*. Gunakan ini untuk membuktikan bahwa (uv)R = vRuR. untuk semua u, v ∈ Σ+. 4. Buktikan bahwa untuk semua w ∈ Σ*. 5. Membiarkan L = {ab, aa, baa}. Manakah dari string berikut diL*: abaabaaabaa. aaaabaaaa. baaaaabaaaab. baaaaabaa? Yang string adalah di L4? 6. Membiarkan Σ = {a, b} dan L = {aa, bb}. Gunakan set notasi untuk menggambarkan. 7. Membiarkan L menjadi bahasa pada alphabet tidak kosong. Menunjukkan bahwaL dan tidak bisa berdua akan terbatas. 8. Apakah ada bahasa untuk 9. Buktikan bahwa untuk semua bahasa L1 dan L2.

10. Menunjukkan bahwa (L*) * = L* Untuk semua bahasa. 11. Membuktikan atau menyangkal klaim berikut. (A) untuk semua bahasa L1 dan L2. (B) untuk semua bahasa L. 12. Cari tata bahasa untuk bahasa L = {Sebuahn, Di mana n bahkan}. 13. Cari tata bahasa untuk bahasa L = {Sebuahn, di mana n Bahkan dan n> 3}. 14. Cari tata bahasa untuk Σ = {a, b} Yang menghasilkan set (Sebuah) semua string dengan tepat dua Sebuah'S. (B) semua string dengan setidaknya dua Sebuah'S. (C) semua string dengan tidak lebih dari tiga Sebuah'S. (D) semua string dengan setidaknya tiga Sebuah'S. (E) semua string yang dimulai dengan Sebuah dan diakhiri dengan b. (F) semua string dengan jumlah bahkan b'S. Dalam setiap kasus, memberikan argumen meyakinkan bahwa tata bahasa yang Anda berikan memang menghasilkan bahasa yang ditunjukkan. 15. Memberikan gambaran sederhana dari bahasa yang dihasilkan oleh tata bahasa dengan produksi S → aaa. SEBUAH → bS. S → λ. 16. Apa bahasa apakah tata bahasa dengan produksi ini menghasilkan? S → A A. SEBUAH → B. B → A A. 17. Membiarkan Σ = {a, b}. Untuk masing-masing bahasa berikut, menemukan tata bahasa yang menghasilkan itu. (Sebuah) L1 = {Sebuahnbm : n ≥ 0, m
(H) (saya) 18. Cari tata bahasa untuk bahasa berikut pada Σ = {Sebuah}. (Sebuah) L = {w : |w| mod 3> 0}. (B) L = {w : |w| mod 3 = 2}. (C) w = {|w| mod 5 = 0}. 19. Cari tata bahasa yang menghasilkan bahasa Memberikan pembenaran lengkap untuk jawaban Anda. 20. Menemukan tiga string dalam bahasa yang dihasilkan oleh

S → ASB|Bsa|Sebuah. 21. Lengkapi argumen di contoh 1.14, Menunjukkan bahwa L (G1) tidak pada kenyataannya menghasilkan bahasa tertentu. 22. Menunjukkan bahwa tata bahasa G = ({S}, {a, b}, S, P), Dengan produksi

S → SS |SSS| ASB |Bsa| λ. adalah setara dengan tata bahasa di contoh 1.13. 23. Menunjukkan bahwa tata bahasa

S → ASB|ab|λ dan

S → aaSbb|ASB|ab|λ adalah setara. 24. Menunjukkan bahwa tata bahasa

S → ASB|Bsa|SS|Sebuah dan

S → ASB|Bsa|Sebuah tidak setara.

1.3 BEBERAPA APLIKASI * Meskipun kami menekankan sifat abstrak dan matematika formal bahasa dan automata, ternyata konsep-konsep ini memiliki luas aplikasi dalam ilmu komputer dan, pada kenyataannya, tema umum yang menghubungkan banyak daerah khusus. Pada bagian ini, kami menyajikan beberapa sederhana contoh untuk memberikan pembaca beberapa jaminan bahwa apa yang kita belajar di sini tidak hanya koleksi abstraksi, tetapi adalah sesuatu yang membantu kita memahami banyak penting, masalah nyata.

bahasa formal dan tata bahasa yang digunakan secara luas dalam kaitannya dengan bahasa pemrograman. Dalam sebagian besar program kami, kami bekerja dengan lebih atau kurang intuitif pemahaman tentang bahasa yang kita tulis. Kadang-kadang meskipun, ketika menggunakan fitur asing, kita mungkin perlu mengacu pada deskripsi yang tepat seperti diagram sintaks ditemukan di sebagian besar teks pemrograman. Jika kita menulis compiler, atau jika kita ingin alasan tentang kebenaran program, deskripsi yang tepat dari bahasa adalah dibutuhkan di hampir setiap langkah. Di antara cara-cara di mana pemrograman bahasa dapat didefinisikan secara tepat, tata bahasa mungkin adalah yang paling banyak digunakan. Tata bahasa yang menggambarkan bahasa khas seperti Pascal atau C sangat luas. Sebagai contoh, mari kita bahasa yang lebih kecil yang merupakan bagian dari satu lebih besar. CONTOH 1.15 Aturan untuk identifier variabel dalam C adalah 1. Sebuah identifier adalah urutan huruf, angka, dan garis bawah. 2. Sebuah identifier harus dimulai dengan huruf atau garis bawah. 3. Identifier memungkinkan atas dan huruf kecil. Secara formal, aturan ini dapat dijelaskan oleh tata bahasa. → <Surat> <sisanya>| <sisanya> → <Surat> <sisanya>| <sisanya>| <sisanya>|λ <surat> → Sebuah|b|...|z|SEBUAH|B|...|Z → 0 | 1 |...| 9 → Dalam tata bahasa ini, variabel yang . <surat>. . , dan . The huruf, angka, dan garis bawah adalah terminal. SEBUAH derivasi dari Sebuah0 adalah ⇒ <surat>

⇒ Sebuah ⇒ Sebuah ⇒ Sebuah0 ⇒ Sebuah0. Definisi bahasa pemrograman melalui tata bahasa adalah umum dan sangat berguna. Tetapi ada alternatif yang sering mudah. Sebagai contoh, kita dapat menggambarkan bahasa oleh accepter, mengambil setiap string yang diterima sebagai bagian dari bahasa. Untuk berbicara tentang ini dengan cara yang tepat, kita perlu memberikan lebih formal definisi robot. Kami akan melakukan ini tak lama; untuk saat ini, mari kita lanjutkan dengan cara yang lebih intuitif. GAMBAR 1.5

Robot dapat diwakili oleh grafik di mana simpul memberikan negara internal dan ujung-ujungnya transisi. Label pada tepi menunjukkan apa yang terjadi (dalam hal input dan output) selama transisi. Sebagai contoh,Gambar 1.5 merupakan transisi dari Negara 1 Negara 2, yang diambil ketika simbol input Sebuah. Dengan ini gambar intuitif dalam pikiran, mari kita lihat cara lain untuk menjelaskan C pengidentifikasi. CONTOH 1.16 Gambar 1.6 adalah robot yang menerima semua C pengidentifikasi hukum. Beberapa interpretasi diperlukan. Kami berasumsi bahwa awalnya otomat adalah di Negara 1; kami menunjukkan ini dengan menggambar panah (tidak berasal dalam vertex) ke negara ini. Seperti biasa, string untuk diperiksa dibaca tersisa untuk kanan, satu karakter pada setiap langkah. Ketika simbol pertama adalah surat atau underscore, robot masuk ke Negara 2, setelah itu sisa string adalah tidak penting. Negara 2 oleh karena itu mewakili “ya” keadaan yang accepter. Sebaliknya, jika simbol pertama adalah angka, otomat akan masuk ke Negara 3, “tidak” negara, dan tetap di sana. Dalam solusi kami, kita asumsikan bahwa tidak ada masukan lain dari huruf, angka, atau garis bawah adalah

mungkin. GAMBAR 1.6

Compiler dan penerjemah lain yang mengkonversi program dari satu bahasa ke bahasa lain membuat ekstensif menggunakan ide-ide menyentuh di ini contoh. bahasa pemrograman dapat didefinisikan secara tepat melalui tata bahasa, seperti dalam contoh 1.15, Dan kedua tata bahasa dan automata memainkan peranan penting dalam proses pengambilan keputusan dimana bagian tertentu dari kode diterima sebagai memuaskan kondisi bahasa pemrograman. Contoh di atas memberikan petunjuk pertama tentang bagaimana hal ini dilakukan; berikut contoh akan memperluas pengamatan ini. Transduser akan dibahas secara singkat dalam Lampiran A; pengikut contoh preview subjek ini. CONTOH 1,17 Sebuah adder biner merupakan bagian integral dari setiap komputer tujuan umum. Seperti penambah mengambil dua string bit yang mewakili angka dan menghasilkan jumlah mereka sebagai output. Untuk mempermudah, mari kita asumsikan bahwa kita hanya berurusan dengan bilangan bulat positif dan yang kita gunakan representasi di yang x = Sebuah0Sebuah1 ··· Sebuahn singkatan integer Ini adalah representasi biner biasa secara terbalik. Sebuah penambah seri memproses dua nomor tersebut x = Sebuah0Sebuah1 ··· Sebuahn, dan y = b0b1 ··· bn, Sedikit demi sedikit, mulai dari ujung kiri. Setiap Selain sedikit menciptakan digit untuk jumlah serta carry digit untuk posisi yang lebih tinggi berikutnya. SEBUAH Selain biner meja (Gambar 1.7) Merangkum proses. Sebuah diagram blok dari jenis yang kita lihat ketika kami pertama kali dipelajari

komputer diberikan dalam Gambar 1.8. Ini memberitahu kita bahwa seorang penambah adalah kotak yang menerima dua bit dan menghasilkan mereka sum bit dan carry mungkin. Saya t menggambarkan apa penambah tidak, tapi menjelaskan sedikit tentang internalnya kerja. Robot (sekarang transduser) dapat membuat ini jauh lebih eksplisit. GAMBAR 1.7 GAMBAR 1.8 GAMBAR 1.9

Input ke transduser adalah pasangan bit (Sebuahsaya. bsaya); output akan menjadi jumlah bit dsaya. Sekali lagi, kami mewakili otomat oleh grafik sekarang label tepi (Sebuahsaya. bsaya) / dsaya. Carry dari satu langkah ke langkah berikutnya adalah diingat oleh otomat melalui dua negara internal berlabel “membawa” dan “tidak ada carry.” Awalnya, transduser akan berada dalam keadaan “tidak membawa.” Ini akan tetap dalam keadaan ini sampai sepasang bit (1, 1) adalah ditemui; ini akan menghasilkan carry yang mengambil otomat ke dalam “carry” negara. Itu Kehadiran carry kemudian diperhitungkan ketika pasangan bit berikutnya adalah Baca baca. Sebuah gambaran lengkap dari penambah seri diberikan dalamGambar 1.9. Ikuti melalui dengan beberapa contoh untuk meyakinkan diri sendiri bahwa itu bekerja dengan benar. Sebagai contoh ini menunjukkan, otomat berfungsi sebagai jembatan antara sangat tinggi tingkat, deskripsi fungsional dari sirkuit dan yang logis implementasi melalui transistor, gerbang, dan sandal jepit. Itu automaton jelas menunjukkan logika keputusan, namun cukup formal untuk meminjamkan dirinya untuk manipulasi matematika yang tepat. Untuk alasan ini, metode desain digital sangat bergantung pada konsep-konsep dari teori automata.

LATIHAN 1. Sementara password umumnya memiliki beberapa pembatasan, mereka biasanya tidak benar-benar gratis. Misalkan dalam sistem tertentu, password dapat panjang sewenang-wenang tetapi harus mengandung setidaknya satu huruf, Sebuah-z, dan satu nomor 0-9. Membangun tata bahasa yang menghasilkan himpunan tersebut password hukum. 2. Misalkan dalam beberapa bahasa pemrograman, jumlahnya dibatasi sebagai berikut: (Sebuah) Sejumlah dapat ditandatangani atau unsigned. (B) Bidang nilai terdiri dari dua bagian tak kosong, dipisahkan oleh titik desimal. (C) Ada adalah bidang eksponen opsional. Jika ada, bidang ini harus mengandung huruf e, Diikuti dengan menandatangani dua-digit integer. Desain tata bahasa mengatur nomor tersebut. 3. Berikan tata bahasa untuk himpunan bilangan integer dalam C. 4. Desain sebuah accepter untuk bilangan bulat di C. 5. Berikan sebuah tata bahasa yang menghasilkan semua konstanta nyata dalam C. 6. Misalkan bahwa izin bahasa pemrograman tertentu saja pengidentifikasi yang dimulai dengan huruf a, mengandung setidaknya satu tapi tidak lebih dari tiga digit, dan dapat memiliki sejumlah surat. memberikan tata bahasa dan accepter untuk satu set seperti pengenal. 7. Memodifikasi tata bahasa di contoh 1.15 sehingga pengidentifikasi memuaskan aturan berikut: (Sebuah) C aturan, kecuali bahwa garis bawah tidak bisa menjadi paling kiri simbol. (B) aturan C, kecuali bahwa ada dapat menjadi paling banyak satu garis bawah. (C) aturan C, kecuali bahwa garis bawah tidak bisa diikuti oleh digit. 8. Dalam sistem nomor Romawi, nomor diwakili oleh string pada alfabet {M, D, C, L, X, V, I}. Desain sebuah accepter yang menerima string tersebut hanya jika mereka benar terbentuk Roman angka. Untuk mempermudah, menggantikan “pengurangan” konvensi di

yang nomor sembilan diwakili oleh IX dengan tambahan setara yang menggunakan V IIII sebagai gantinya. 9. Kami berasumsi bahwa robot bekerja dalam kerangka diskrit waktu langkah, tetapi aspek ini memiliki sedikit pengaruh pada kami berikutnya diskusi. Dalam desain digital, bagaimanapun, waktu elemen mengasumsikan signifikansi yang cukup. Dalam rangka sinkronisasi sinyal tiba dari berbagai bagian komputer, penundaan sirkuit diperlukan. SEBUAH Unit-delay transduser adalah salah satu yang hanya mereproduksi input (Dilihat sebagai aliran terus-menerus dari simbol-simbol) satu satuan waktu kemudian. Secara khusus, jika transduser berbunyi sebagai masukan simbol Sebuah pada waktu t, saya t akan mereproduksi simbol bahwa sebagai output pada saat t + 1. Pada saat t = 0, transduser output apa-apa. Kami menunjukkan ini dengan mengatakan bahwa transduser menerjemahkan masukan Sebuah1Sebuah2 ° menjadi output λSebuah1Sebuah2 ···. Menggambar grafik yang menunjukkan bagaimana suatu unit-delay transduser mungkin dirancang untuk Σ = {a, b}. 10. Sebuah n-unit penundaan transduser adalah salah satu yang mereproduksi input n waktu unit kemudian; yaitu, inputSebuah1Sebuah2 ··· diterjemahkan ke dalam λnSebuah1Sebuah2 ···, berarti lagi bahwa transduser tidak menghasilkan output untuk pertama n slot waktu. (A) Buatlah dua unit delay transduser pada Σ = {a, b}. (B) Tunjukkan bahwa sebuah n-unit delay transduser harus memiliki setidaknya |Σ|n negara. 11. komplemen dua itu dari string biner, yang mewakili positif integer, dibentuk oleh pertama melengkapi setiap bit, kemudian menambahkan satu ke bit terendah-order. Desain transduser untuk menerjemahkan sedikit string ke mereka dua komplemen, dengan asumsi bahwa biner

nomor diwakili seperti di contoh 1,17, Dengan orde yang lebih rendah bit pada di sebelah kiri string. 12. Desain transduser untuk mengkonversi string biner ke oktal. Untuk Misalnya, bit string 001101110 harus menghasilkan output 156. 13. Membiarkan Sebuah1Sebuah2 ··· menjadi masukan bit string. Desain transduser yang menghitung paritas setiap substring dari tiga bit. Secara khusus, transducer harus menghasilkan output π1 = π2 = 0, πsaya = (Sebuahi-2 + Sebuahi-1 + Sebuahsaya) mod 2, saya = 3, 4, .... Sebagai contoh, input 110.111 harus menghasilkan 000.001. 14. Desain transduser yang menerima string bit Sebuah1Sebuah2Sebuah3... dan hitungan nilai biner dari setiap set tiga bit berturut-turut modulo lima. Lebih khusus, transduser harus menghasilkan m1. m2. m3. .... dimana m1 = m2 = 0, msaya = (4Sebuahsaya 2Sebuahi-1 + Sebuahi-2) mod 5, saya = 3, 4, .... 15. komputer digital biasanya mewakili semua informasi dengan bit string, menggunakan beberapa jenis encoding. Sebagai contoh, informasi karakter dapat dikodekan menggunakan sistem ASCII terkenal. Untuk latihan ini, mempertimbangkan dua huruf {a, b, c, d} Dan {0, 1}, masing-masing, dan encoding dari pertama ke kedua, didefinisikan oleh Sebuah → 00, b → 01, c → 10, d → 11. Buatlah sebuah transduser untuk string decoding pada {0, 1} ke pesan asli. Sebagai contoh, input 010.011 harus menghasilkan output buruk. 16. Membiarkan x dan y dua angka biner positif. Desain transduser Output yang adalah max (x, y).