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.

— tcdowney
źródło

^{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 $(\mathbb{N},\leq)$ odnosi się do wszystkich. $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ $n \in \mathbb{N}$

Kotwica : dla , $n=0$ wyraźnie trzyma. $\sum_{i=0}^{n} i = 0 = \frac{n(n+1)}{2}$
Hipoteza : Załóż, że posiada przy dowolnym, ale fixed². $\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 . 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ść , to również ma wartość ; jeśli ma wartość , ma także wartość ; 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 z wielkość zestawu mocy z wynosi ³. Wykonujemy naszą indukcji na , ponownie, a mianowicie na wielkości podzbiorów . $(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 i dlatego jak zastrzeżono. $0$ $2^\emptyset = \{\emptyset\}$ $|2^\emptyset| = 1 = 2^0$
Hipoteza: Załóż, że dla wszystkich zbiorów z z pewnymi dowolnymi, ale ustalonymi , mamy . $A \subseteq \mathbb{N}$ $|A| \leq n$ $n \in \mathbb{N}$ $|2^A| = 2^{|A|}$
Krok: Niech dowolna⁴ o rozmiarze i niech dowolna (takie istnieje jako ). Teraz hipoteza dotyczy a zatem . 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$
1. 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.

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).
$n$
$2^A$ $A$ ${0,1}$
$B$ $A$

— Raphael
źródło