Jak napisać dowód przy użyciu indukcji na długości ciągu wejściowego?

W moim kursie teorii obliczeń wiele naszych problemów wiąże się z wykorzystaniem indukcji na długości łańcucha wejściowego do udowodnienia twierdzeń o automatach skończonych. Rozumiem indukcję matematyczną, ale kiedy pojawiają się struny, naprawdę się potykam. Byłbym bardzo wdzięczny, gdyby ktoś krok po kroku robił taki dowód.

Oto przykładowy problem (ćwiczenie 2.2.10 z Hopcroft i Ullman 3rd Edition):

Rozważ DFA z następującą tabelą przejścia:

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

Nieformalnie opisz język akceptowany przez ten DFA i udowodnij, wprowadzając długość ciągu wejściowego, że Twój opis jest poprawny.

Jest to problem, na który odpowiedziano w książce, więc nie szukam nikogo do odrabiania lekcji. Potrzebuję tylko kogoś, kto mi to wytłumaczy.

Odpowiedź książki: (wzięte stąd )

Automat informuje, czy liczba 1 jest parzysta (stan A) czy nieparzysty (stan B), akceptując w tym drugim przypadku. Jest to łatwa indukcja na | w | aby pokazać, że dh (A, w) = A wtedy i tylko wtedy, gdy w ma parzystą liczbę 1. Podstawa: | w | = 0. Zatem w, pusty łańcuch z pewnością ma parzystą liczbę 1, a mianowicie zero 1 i hat-hat (A, w) = A.

Indukcja: Załóżmy, że ciągi znaków są krótsze niż w. Następnie w = za, gdzie a wynosi 0 lub 1.

• Przypadek 1: a = 0. Jeśli w ma parzystą liczbę 1, to samo dotyczy z. Zgodnie z hipotezą indukcyjną δ-hat (A, z) = A. Przejścia z DFA mówią nam δ-hat (A, w) = A. Jeśli w ma nieparzystą liczbę 1, to też robi z. Poprzez hipotezę indukcyjną δ-hat (A, z) = B, a przejścia DFA mówią nam δ-hat (A, w) = B. Zatem w tym przypadku δ-hat (A, w) = A wtedy i tylko wtedy, gdy w ma parzystą liczbę 1.

• Przypadek 2: a = 1. Jeśli w ma parzystą liczbę 1, to z ma nieparzystą liczbę 1. Zgodnie z hipotezą indukcyjną δ-hat (A, z) = B. Przejścia DFA mówią nam δ-hat (A, w) = A. Jeśli w ma nieparzystą liczbę 1, to z ma parzystą liczbę 1. Poprzez hipotezę indukcyjną δ-hat (A, z) = A, a przejścia DFA mówią nam δ-hat (A, w) = B. Zatem w tym przypadku również δ-hat (A, w ) = A wtedy i tylko wtedy, gdy w ma parzystą liczbę 1.

Rozumiem, jak udowodnić rzeczy takie jak za pomocą indukcji. Jestem tylko zdezorientowany, jak to działa z budowaniem ciągów. Jestem zdziwiony pogrubionymi częściami. Nie rozumiem, jak oni wymyślili / jak to faktycznie dowodzi, co jest akceptowane / jak to jest indukcyjne.$\sum_{i=0}^{n}i = \frac{n(n+1)}{2}$

Nawiasem mówiąc, hat-hat jest rozszerzoną funkcją przejścia.

^{Ponieważ nie jest jasne, gdzie leży twój problem, zacznę od samego początku.}

Indukcja matematyczna działa jak gra w chińskie szepty (w idealnym przypadku, tj. Cała komunikacja jest bezstratna) lub (idealnie skonfigurowane) domino : zaczynasz gdzieś i pokazujesz, że każdy kolejny krok niczego nie psuje, zakładając, że nic nie zostało zerwane do następnie.

Bardziej formalnie, każdy dowód indukcyjny składa się z trzech podstawowych elementów:

• Kotwica indukcyjna , również skrzynka podstawowa : w przypadku małych skrzynek1 pokazujesz, że roszczenie się utrzymuje.
• Hipoteza indukcyjna : zakładasz, że roszczenie dotyczy określonego podzbioru zbioru, o którym chcesz coś udowodnić.
• Krok indukcyjny : wykorzystując hipotezę, pokazujesz, że roszczenie dotyczy większej liczby elementów.

Oczywiście krok musi być dostrojony tak, aby obejmował cały zestaw podstawowy (w limicie).

Ważna uwaga: ludzie, którzy są pewni swoich umiejętności indukcyjnych, często połyskują kotwicę i pozostawiają hipotezę ukrytą. Chociaż jest to w porządku, gdy prezentujesz swoje prace ekspertom (np. Artykułowi), nie jest to zalecane, gdy wykonujesz dowody samodzielnie, szczególnie jako początkujący. Zapisz wszystko.

Rozważ prosty przykład nad ; chcemy pokazać, że ∑ n i = 0 i = n ( n + 1 $(\mathbb{N},\leq)$ odnosi się do wszystkichn∈N.$\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$$n \in \mathbb{N}$

• Kotwica : dla , ∑ n i = 0 i = 0 = n ( n + 1 $n=0$ wyraźnie trzyma.$\sum_{i=0}^{n} i = 0 = \frac{n(n+1)}{2}$
• Hipoteza : Załóż, że posiada przy dowolnym, ale fixed²n∈N.$\sum_{i=0}^{k} i = \frac{k(k+1)}{2}$$n \in \mathbb{N}$

• Krok : Dla oblicz sumę:$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}$

  Tak więc tożsamość obowiązuje dla . (Zauważamy, że potrzebowaliśmy tylko niewielkiej części hipotezy, mianowicie dla k = n . Często się to zdarza.)$n+1$$k=n$

Zasada indukcyjna zapewnia nas teraz, że twierdzenie rzeczywiście się utrzymuje: bezpośrednio pokazaliśmy to dla . Krok mówi, że jeśli ma wartość 0 , to również ma wartość 1 ; jeśli ma wartość 1 , ma także wartość 2 ; i tak dalej.$0$$0$$1$$1$$2$

Spójrzmy na inny przykład, tym razem na . Twierdzenie, które chcemy udowodnić, brzmi: dla każdego skończonego podzbioru A z N wielkość zestawu mocy 2 A z A wynosi 2 | A | ³. Wykonujemy naszą indukcji na ( N , ≤ ) , ponownie, a mianowicie na wielkości podzbiorów A .$(2^\mathbb{N}, \subseteq)$$A$$\mathbb{N}$$2^A$$A$$2^{|A|}$$(\mathbb{N}, \leq)$$A$

• Kotwica: Rozważ (tylko) zestaw rozmiaru , pusty zestaw. Oczywiście 2 ∅ = { ∅ } i dlatego | 2 ∅ | = 1 = 2 0 jak zastrzeżono.$0$$2^\emptyset = \{\emptyset\}$$|2^\emptyset| = 1 = 2^0$
• Hipoteza: Załóż, że dla wszystkich zbiorów z | A | ≤ n z pewnymi dowolnymi, ale ustalonymi n ∈ N , mamy | 2 A | = 2 | A | .$A \subseteq \mathbb{N}$$|A| \leq n$$n \in \mathbb{N}$$|2^A| = 2^{|A|}$

• Krok: Niech dowolna⁴ o rozmiarze n + 1 i niech b ∈ B dowolna (takie b istnieje jako n + 1 > 0 ). Teraz hipoteza dotyczy B ∖ { b }, a zatem | 2 B ∖ { b } | = 2 n . Od$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\}} \}$

  mamy w istocie, że jak zastrzeżono.$|2^{B}| = 2 \cdot |2^{B \setminus \{b\}}| = 2 \cdot 2^n = 2^{n+1}$

Ponownie przez indukcję roszczenie zostało udowodnione.

$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$

Zasada indukcji oznacza, że ​​roszczenie rzeczywiście się utrzymuje.

1. Indukcję wykonuje się według jakiegoś częściowego porządku; kotwica musi obejmować wszystkie minimalne elementy, a czasem więcej (w zależności od instrukcji).
2. $n$
3. $2^A$$A$${0,1}$
4. $B$$A$