Bagaimana cara menulis bukti menggunakan induksi pada panjang string input?

Dalam kursus Teori Komputasi saya, banyak masalah kami melibatkan penggunaan induksi pada panjang string input untuk membuktikan pernyataan tentang automata terbatas. Saya mengerti induksi matematika, namun ketika string mulai dimainkan, saya benar-benar tersandung. Saya akan sangat menghargai jika seseorang akan melalui proses pembuatan bukti setahap demi setahap.

Inilah contoh masalah (Latihan 2.2.10 dari Hopcroft dan Ullman 3rd Edition):

Pertimbangkan DFA dengan tabel transisi berikut:

        0 1
       ________
-> A | AB
  * B | BA

Uraikan secara tidak resmi bahasa yang diterima oleh DFA ini, dan buktikan dengan induksi pada panjang string input bahwa deskripsi Anda benar.

Ini adalah masalah yang dijawab dalam buku ini, jadi saya tidak mencari seseorang untuk mengerjakan pekerjaan rumah saya. Saya hanya perlu seseorang untuk menjelaskannya langsung kepada saya.

Jawaban Buku: (diambil dari sini )

Automaton memberi tahu apakah angka 1 yang terlihat genap (keadaan A) atau ganjil (keadaan B), menerima dalam kasus terakhir. Ini adalah induksi yang mudah di | w | untuk menunjukkan bahwa dh (A, w) = A jika dan hanya jika w memiliki bilangan genap 1's. Dasar: | w | = 0. Lalu w, string kosong pasti memiliki angka genap 1, yaitu nol 1, dan δ-topi (A, w) = A.

Induksi: Asumsikan pernyataan untuk string lebih pendek dari w. Kemudian w = za, di mana a adalah 0 atau 1.

• Kasus 1: a = 0. Jika w memiliki angka genap 1, begitu juga z. Dengan hipotesis induktif, δ-hat (A, z) = A. Transisi DFA memberi tahu kita δ-hat (A, w) = A. Jika w memiliki angka ganjil dari 1, maka demikian juga z. Dengan hipotesis induktif, δ-hat (A, z) = B, dan transisi DFA memberi tahu kita δ-hat (A, w) = B. Jadi, dalam hal ini, δ-hat (A, w) = A jika dan hanya jika w memiliki angka genap 1.

• Kasus 2: a = 1. Jika w memiliki angka genap 1, maka z memiliki angka ganjil 1. Dengan hipotesis induktif, δ-hat (A, z) = B. Transisi DFA memberi tahu kita δ-hat (A, w) = A. Jika w memiliki angka ganjil dari 1, maka z memiliki jumlah genap dari 1 Dengan hipotesis induktif, δ-hat (A, z) = A, dan transisi DFA memberi tahu kita δ-hat (A, w) = B. Dengan demikian, dalam hal ini juga, δ-hat (A, w ) = A jika dan hanya jika w memiliki angka genap 1.

Saya mengerti bagaimana membuktikan hal-hal seperti menggunakan induksi. Saya hanya bingung dengan bagaimana ini bekerja dengan membangun string. Saya bingung dengan bagian yang tebal. Saya tidak mengerti bagaimana mereka memunculkan / bagaimana ini benar-benar membuktikan apa yang diterima / bagaimana itu induktif.$\sum_{i=0}^{n}i = \frac{n(n+1)}{2}$

Omong-omong adalah fungsi transisi yang diperluas.

^{Karena tidak jelas di mana masalah Anda berada, saya akan mulai dari awal.}

Induksi matematika berfungsi seperti permainan bisikan Cina (dalam kasus yang ideal, yaitu semua komunikasi tidak rugi) atau (diatur dengan sempurna) domino : Anda memulai suatu tempat dan menunjukkan bahwa setiap langkah Anda berikutnya tidak merusak apa pun, dengan asumsi tidak ada yang rusak sampai kemudian.

Secara lebih formal, setiap bukti induksi terdiri dari tiga elemen dasar:

• Induksi jangkar , juga kasus dasar : Anda menunjukkan untuk kasus kecil¹ yang dimiliki oleh klaim.
• Hipotesis induksi : Anda menganggap bahwa klaim berlaku untuk subset tertentu dari set yang ingin Anda buktikan.
• Langkah induktif : Dengan menggunakan hipotesis, Anda menunjukkan bahwa klaim berlaku untuk lebih banyak elemen.

Tentu saja, langkah harus disetel sedemikian sehingga mencakup seluruh set dasar (dalam batas).

Catatan penting: orang yang percaya diri dengan keterampilan induksi mereka sering mengabaikan jangkar dan membiarkan hipotesis tersirat. Meskipun ini baik-baik saja ketika mempresentasikan karya Anda kepada audiens ahli (misalnya makalah), ini tidak dianjurkan saat melakukan pembuktian sendiri, terutama sebagai pemula. Tulis semuanya.

Pertimbangkan contoh sederhana di atas ; kami ingin menunjukkan bahwa ∑ n i = 0 i = n ( n + 1 $(\mathbb{N},\leq)$ berlaku untuk semuan∈N.$\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$$n \in \mathbb{N}$

• Anchor : Untuk , Σ n i = 0 i = 0 = n ( n + 1 $n=0$ jelas memegang.$\sum_{i=0}^{n} i = 0 = \frac{n(n+1)}{2}$
• Hipotesis : Asumsikan bahwa berlaku untuk sewenang-wenang, tetapi fixed²n∈N.$\sum_{i=0}^{k} i = \frac{k(k+1)}{2}$$n \in \mathbb{N}$

• Langkah : Untuk , menghitung penjumlahan:$n+1$

  $\qquad \displaystyle \sum_{i=0}^{n+1} i = (n+1) + \sum_{i=0}^{n} i \overset{\text{IH}}{=} n+1 + \frac{n(n+1)}{2} = \frac{(n+2)(n+1)}{2}$

  Jadi identitas berlaku untuk . (Kami mencatat bahwa kami hanya membutuhkan sebagian kecil dari hipotesis, yaitu untuk k = n . Itu sering terjadi.)$n+1$$k=n$

Prinsip induktif sekarang meyakinkan kita bahwa klaim itu memang berlaku: kita telah langsung menunjukkannya untuk . Langkah ini mengatakan, jika berlaku untuk 0 , itu juga berlaku untuk 1 ; jika berlaku untuk 1 , ia juga berlaku untuk 2 ; dan seterusnya.$0$$0$$1$$1$$2$

Mari kita lihat contoh lain, kali ini di . Klaim yang ingin kami buktikan adalah: untuk setiap subset hingga A dari N , ukuran set daya 2 A dari A adalah 2 | A | ³. Kami melakukan induksi kami atas ( N , ≤ ) , sekali lagi, yaitu atas ukuran himpunan bagian A .$(2^\mathbb{N}, \subseteq)$$A$$\mathbb{N}$$2^A$$A$$2^{|A|}$$(\mathbb{N}, \leq)$$A$

• Anchor: Pertimbangkan set (hanya) ukuran , set kosong. Jelas, 2 ∅ = { ∅ } dan karenanya | 2 ∅ | = 1 = 2 0 seperti yang diklaim.$0$$2^\emptyset = \{\emptyset\}$$|2^\emptyset| = 1 = 2^0$
• Hipotesis: Asumsikan bahwa untuk semua set dengan | A | ≤ n dengan beberapa sewenang-wenang, tetapi tetap n ∈ N , kita memiliki | 2 A | = 2 | A | .$A \subseteq \mathbb{N}$$|A| \leq n$$n \in \mathbb{N}$$|2^A| = 2^{|A|}$

• Langkah: Misalkan arbitrary⁴ ukuran n + 1 , dan biarkan b ∈ B sewenang-wenang (seperti b ada sebagai n + 1 > 0 ). Sekarang hipotesis berlaku untuk B ∖ { b } dan dengan demikian | 2 B ∖ { b } | = 2 n . Sejak$B \subseteq \mathbb{N}$$n+1$$b \in B$$b$$n+1 > 0$$B \setminus \{b\}$$|2^{B \setminus \{b\}}| = 2^n$

  $\qquad \displaystyle 2^B = 2^{B \setminus \{b\}} \cup \{ A \cup \{b\}\mid A \in 2^{B \setminus \{b\}} \}$

  $|2^{B}| = 2 \cdot |2^{B \setminus \{b\}}| = 2 \cdot 2^n = 2^{n+1}$

Sekali lagi, dengan induksi klaim terbukti.

$n$

$B$

• $\varepsilon$$A$
• $n$
• $w \in \{0,1\}^{n+1}$
  1. $w$
     1. $w_n = 0$$w' = w_1 \dots w_{n-1}$$A$$w'$$w_n = 0$$A$
     2. $w_n = 1$$w' = w_1 \dots w_{n-1}$$B$$w'$$w_n = 1$$A$
  2. $w$

Prinsip induksi menyiratkan bahwa klaim memang berlaku.

1. Anda melakukan induksi sepanjang beberapa perintah parsial; jangkar harus mencakup semua elemen minimal, dan kadang-kadang lebih (tergantung pada pernyataan).
2. $n$
3. $2^A$$A$${0,1}$
4. $B$$A$