Как мне написать доказательство, используя индукцию по длине входной строки?

В моем курсе теории вычислений многие наши проблемы связаны с использованием индукции по длине входной строки для доказательства утверждений о конечных автоматах. Я понимаю математическую индукцию, однако, когда вступают в игру струны, меня сильно сбивают с толку. Я был бы очень признателен, если бы кто-то пошёл через процесс создания такого доказательства шаг за шагом.

Вот пример проблемы (упражнение 2.2.10 от Хопкрофта и Уллмана, 3-е издание):

Рассмотрим DFA со следующей таблицей переходов:

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

Неофициально опишите язык, принятый этим DFA, и наведите индуктивно по длине входной строки, что ваше описание верно.

Эта проблема решена в книге, поэтому я не ищу кого-то, кто сделает мою домашнюю работу. Мне просто нужен кто-то, чтобы объяснить это мне прямо.

Ответ книги: (взято отсюда )

Автомат сообщает, является ли число увиденных единиц четным (состояние A) или нечетным (состояние B), принимая в последнем случае. Это простая индукция на | w | показать, что dh (A, w) = A тогда и только тогда, когда w имеет четное число единиц. Основа: | ш | = 0. Тогда w, пустая строка, безусловно, имеет четное число 1, а именно нули 1, и δ-hat (A, w) = A.

Индукция: предположим, что для строк короче w. Тогда w = za, где a равно 0 или 1.

• Случай 1: a = 0. Если w имеет четное число единиц, то и z. По индуктивному предположению δ-hat (A, z) = A. Переходы DFA говорят нам, что δ-hat (A, w) = A. Если w имеет нечетное число 1, то и z. По индуктивной гипотезе δ-hat (A, z) = B, а переходы DFA говорят нам о δ-hat (A, w) = B. Таким образом, в этом случае δ-hat (A, w) = А тогда и только тогда, когда w имеет четное число единиц.

• Случай 2: a = 1. Если w имеет четное число 1, то z имеет нечетное число 1. По индуктивной гипотезе δ-hat (A, z) = B. Переходы DFA говорят нам, что δ-hat (A, w) = A. Если w имеет нечетное число 1, то z имеет четное число 1 - х. По индуктивной гипотезе δ-hat (A, z) = A, а переходы DFA говорят нам о δ-hat (A, w) = B. Таким образом, и в этом случае δ-hat (A, w ) = A тогда и только тогда, когда w имеет четное число единиц.

Я понимаю, как доказать такие вещи, как с использованием индукции. Я просто смущен тем, как это работает со строками. Я смущен полужирными частями. Я не понимаю, как они пришли / как это на самом деле доказывает, что принято / как это индуктивно.$\sum_{i=0}^{n}i = \frac{n(n+1)}{2}$

Кстати, δ-hat - это расширенная функция перехода.

^{Поскольку неясно, в чем ваша проблема, я начну с самого начала.}

Математическая индукция работает как игра китайского шепота (в идеальном случае, т. Е. Все общение происходит без потерь) или (идеально настроенных) домино : вы начинаете где-то и показываете, что каждый ваш следующий шаг ничего не нарушает, предполагая, что ничего не сломано до тогда.

Более формально, каждое доказательство индукции состоит из трех основных элементов:

• Индукционный якорь , также базовый случай : для небольших случаев вы показываете, что иск имеет место.
• Гипотеза об индукции : вы предполагаете, что утверждение верно для некоторого подмножества набора, о котором вы хотите что-то доказать.
• Индуктивный шаг : используя гипотезу, вы показываете, что утверждение верно для большего числа элементов.

Конечно, шаг должен быть настроен так, чтобы он охватывал весь базовый набор (в пределе).

Важное примечание: люди, которые уверены в своих навыках освоения, часто замазывают якорь и оставляют гипотезу неявной. Хотя это хорошо, когда вы представляете свою работу экспертной аудитории (например, на бумаге), это не рекомендуется, когда вы делаете доказательства самостоятельно, особенно для начинающих. Запишите все.

$(\mathbb{N},\leq)$$\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$$n \in \mathbb{N}$

• $n=0$$\sum_{i=0}^{n} i = 0 = \frac{n(n+1)}{2}$
• $\sum_{i=0}^{k} i = \frac{k(k+1)}{2}$$n \in \mathbb{N}$

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

  $n+1$$k=n$

$0$$0$$1$$1$$2$

$(2^\mathbb{N}, \subseteq)$$A$$\mathbb{N}$$2^A$$A$$2^{|A|}$$(\mathbb{N}, \leq)$$A$

• $0$$2^\emptyset = \{\emptyset\}$$|2^\emptyset| = 1 = 2^0$
• $A \subseteq \mathbb{N}$$|A| \leq n$$n \in \mathbb{N}$$|2^A| = 2^{|A|}$

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

Опять же, по индукции претензия доказана.

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

Принцип индукции подразумевает, что требование действительно выполняется.

1. Вы выполняете индукцию по некоторому частичному порядку; Якорь должен охватывать все минимальные элементы, а иногда и больше (в зависимости от утверждения).
2. $n$
3. $2^A$$A$${0,1}$
4. $B$$A$