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

20

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

Вот пример проблемы (упражнение 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 имеет четное число единиц.

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

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

tcdowney
источник

Ответы:

17

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

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

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

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

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

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


(N,)i=0ni=n(n+1)2nN

  • n=0i=0ni=0=n(n+1)2
  • i=0ki=k(k+1)2nN
  • n+1

    i=0n+1i=(n+1)+i=0ni=IHn+1+n(n+1)2=(n+2)(n+1)2

    n+1k=n

00112


(2N,)AN2AA2|A|(N,)A

  • 02={}|2|=1=20
  • AN|A|nnN|2A|=2|A|
  • BNn+1bBbn+1>0B{b}|2B{b}|=2n

    2B=2B{b}{A{b}A2B{b}}

    |2B|=2|2B{b}|=22n=2n+1

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


n

B

  • εA
  • n
  • w{0,1}n+1
    1. w
      1. wn=0w=w1wn1Awwn=0A
      2. wn=1w=w1wn1Bwwn=1A
    2. w

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


  1. Вы выполняете индукцию по некоторому частичному порядку; Якорь должен охватывать все минимальные элементы, а иногда и больше (в зависимости от утверждения).
  2. n
  3. 2AA0,1
  4. BA
Рафаэль
источник