Доказательства по индукции - Теория автоматов - Страница 2

@AnD04 · 12.09.2022, 09:06 **[ТС]**

Author24 — интернет-сервис помощи студентам

Другими словами, нужно показать, что $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat\sigma_N(q, w)=\{\hat\sigma_D(q, w)\}.$

непонятно это высказывание. В математике фигурные скобки используют для обозначения множества, по-этому равенство $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat\sigma_N(q, w)=\{\hat\sigma_D(q, w)\}.$ не может быть равно. Объясните, пожалуйста.

Добавлено через 20 минут
Докажем, что если $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat{\sigma}_D(q, w)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q, w)=\{p\}$ для любой строки w, произвольного состояния q и состояния p. Доказательство будет проходить индукцией по длине w.
Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?D=(Q, \Sigma, \delta_D, q_0,F)$ есть некоторый ДКА, N является НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?N=(Q, \Sigma, \delta_N, q_0,F)$ , который эквивалентный дка, где а-последний символ, где $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_N$ определена правилом: если $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_D(q, a) =p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_N(q, a) =\{p\}$ . Предположим n - любое число, индукцию ведём по n.
База: Пусть |w|=0, т.е. w= $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ . Из базисных частей определений для ДКА и НКА имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_D((q_0, \varepsilon)=q_0$ , а $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,\varepsilon)= \{q_0\}$
Шаг Индукции:
Пусть w-цепочка вида ха, т.е. а- последний символ в цепочке, а х-цепочка, состоящая из всех символов цепочки w, за исключением послелнего. Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma(q, w)=\sigma(\hat\sigma(q, x), a) <br />$ .
Эта часть верна?

@3D Homer · 12.09.2022, 13:05

Сообщение от AnD04

В математике фигурные скобки используют для обозначения множества

Именно так.

Сообщение от AnD04

по-этому равенство $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat\sigma_N(q, w)=\{\hat\sigma_D(q, w)\}.$ не может быть равно.

Вот цитата из вашего сообщения № 17.

Сообщение от AnD04

Докажем, что если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma_D(q, w)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma_N(q, w)=\{p\}$ для любой строки w и состояния p.

В математике можно равные подставлять вместо равных. То есть, если доказано, что x = y, то для любое утверждение P(x) эквивалентно P(y). В утверждении выше есть предположение $https://www.cyberforum.ru/cgi-bin/latex.cgi?p=\hat\sigma_D(q, w)$ . Значит, используя факт о подстановке, мы получаем, что требуемое утверждение $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma_N(q, w)=\{p\}$ эквивалентно $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma_N(q, w)=\{\hat\sigma_D(q, w)\}$ .

Вообще при чтении и составлении разных утверждений чрезвычайно важно следить за типом сущности, которую обозначает каждая переменная, выражение и его часть. Так, нужно четко понимать, обозначает ли переменная число, кортеж чисел, множество, матрицу, геометрическую фигуру и т.п. В данном случае нужно задать вопрос: что такое $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ ? Согласно определению ДКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D\colon Q\times\Sigma\to Q$ , поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ есть элемент Q, то есть состояние автомата. Что такое $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ ? Согласно определению НКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N\colon Q\times\Sigma\to 2^Q$ , где 2^Q обозначает булеан Q, поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ есть подмножество элементов Q, то есть множество состояний. Это делает предположение "если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a) = p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a) = \{p\}$ " разумным: первая функция возвращает состояние, вторая — множество из одного этого состояния.

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

Про остальную часть напишу позже.

@AnD04 · 14.09.2022, 08:56 **[ТС]**

Согласно определению ДКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D$ [имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D:Qx\sigma\rightarrow Q$ , поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ есть элемент Q, то есть состояние автомата. Что такое $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ ? Согласно определению НКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N:Qx\sigma\rightarrow {2}^{Q}$ , где 2Q обозначает булеан Q, поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ есть подмножество элементов Q, то есть множество состояний. Это делает предположение "если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)=\{p\}$ " разумным: первая функция возвращает состояние, вторая — множество из одного этого состояния.

Это утверждение относится к доказательству? Если "да", то к какой части?

@3D Homer · 14.09.2022, 14:33

Сообщение от AnD04

Это утверждение относится к доказательству?

Какое утверждение?

@AnD04 · 16.09.2022, 09:55 **[ТС]**

То что я выделил в своём сообщении из вашего текста

@3D Homer · 16.09.2022, 11:13

Сообщение от AnD04

То что я выделил в своём сообщении из вашего текста

Цитата в сообщении 23 содержит четыре предложения и не меньшее число утверждений. Например, среди этих утверждений есть "функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D\colon Q\times\Sigma\to Q$ " и " $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ есть состояние автомата". Ставя вопрос "Это утверждение относится к доказательству?" не уточнив, какое из них вы имеете в виду, вы затрудняете разговор. Кроме того, все утверждения в этой цитате говорят об определениях понятий из утверждения в сообщении 1, поэтому конечно они относятся к доказательству. Более того, фраза "если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a) = p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a) = \{p\}$ " вообще является частью утверждения из сообщения 1, которое требуется доказать.

@AnD04 · 07.11.2022, 17:58 **[ТС]**

Доказательство

Докажем, что если $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat{\sigma}_D(q, w)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q, w)=\{p\}$ для любой строки w, произвольного состояния q и состояния p. Доказательство будет проходить индукцией по длине w.
Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?D=(Q, \Sigma, \delta_D, q_0,F)$ есть некоторый ДКА, N является НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?N=(Q, \Sigma, \delta_N, q_0,F)$ , который эквивалентный дка, где а-последний символ, где $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_N$ определена правилом: если $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_D(q, a) =p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_N(q, a) =\{p\}$ . Предположим n - любое число, индукцию ведём по n.Согласно определению ДКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D:Qx\sigma\rightarrow Q$ , поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ есть элемент Q, то есть состояние автомата. Что такое $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ ? Согласно определению НКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N:Qx\sigma\rightarrow {2}^{Q}$ , где 2Q обозначает булеан Q, поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ есть подмножество элементов Q, то есть множество состояний. Это делает предположение "если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)=\{p\}$ " разумным: первая функция возвращает состояние, вторая — множество из одного этого состояния.
База: Пусть |w|=0, т.е. w= $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ . Из базисных частей определений для ДКА и НКА имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_D((q_0, \varepsilon)=q_0$ , а $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,\varepsilon)= \{q_0\}$
Шаг Индукции:
Пусть w-цепочка вида ха, т.е. а- последний символ в цепочке, а х-цепочка, состоящая из всех символов цепочки w, за исключением послелнего. Пусть оба множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,a)\}=\hat{\sigma}_N(q_0,a)$ состояний N представляют собой $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{p_1,p_2,...,p_k\}$ .
По индуктивной части определения для НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,w)=\bigcup_i=1^k\sigma_N(p_i, a)$ (1).
С другой стороны, конструкция подмножеств даёт
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(\{p_1,p_2,...,p_k\},a)\}=\bigcup_i=1^k\sigma_N(p_i,a).$ (2).
Теперь, подставляя (2) в индуктивную часть определения для ДКА и используя тот факт, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q_0,x)={p_1,p_2,...,p_k}\}$ получаем :
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,x)=\{\sigma_D(\hat{\sigma}_D(q_0,x),a))\}=\{\sigma_D(\{p_1,p_2,...,p_k\},a)\}=\bigcup_.$

По индуктивной части определения для НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,w)=\bigcup_{i=1}^{k} \sigma_N(p_i, a)$ (1).
С другой стороны, конструкция подмножеств даёт
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(\{p_1,p_2,...,p_k\},a)\}=\bigcup_{i=1}^{k} \sigma_N(p_i,a).$ (2).
Теперь, подставляя (2) в индуктивную часть определения для ДКА и используя тот факт, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,x)\} =\{p_1,p_2,...,p_k\}$ получаем :
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,x)\} =\{\sigma_D(\{p_1,p_2,...,p_k\},a)\}=\bigcup_{i=1}^{k}\sigma_N(p_i, a).$ (3).
Таким образом из уравнений (1) и (3) видно, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,w)\} =\hat{\sigma}_N(q,w).$

Исправления доказательства

Сообщение от AnD04

Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?D=(Q, \Sigma, \delta_D, q_0,F)$ есть некоторый ДКА, N является НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?N=(Q, \Sigma, \delta_N, q_0,F)$ , который эквивалентный дка]

это не верно, так как множество не может быть равно подмножеству, я правильно понял?

Добавлено через 30 минут

Сообщение от AnD04

База: Пусть |w|=0, т.е. w= $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ . Из базисных частей определений для ДКА и НКА имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_D((q_0, \varepsilon)=q_0$ , а $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,\varepsilon)= \{q_0\}$

тоже не верно. Будет правильно так: База :Пусть w= $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ . Значит $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_D((q_0, \varepsilon)=p$ , а $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0\varepsilon)= \{p\}$ , тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D((q_0, \varepsilon)\} = \hat{\sigma}_N(q_0,\varepsilon)$

Добавить утверждение в шаг индукции: Пусть w имеет длину n+1, и предположим, что утверждение справедливо для цепочки длины n.

@AnD04 1 / 1 / 0 Регистрация: 21.01.2013 Сообщений: 99
	12.09.2022, 09:06 [ТС]	21
	Другими словами, нужно показать, что $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat\sigma_N(q, w)=\{\hat\sigma_D(q, w)\}.$ непонятно это высказывание. В математике фигурные скобки используют для обозначения множества, по-этому равенство $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat\sigma_N(q, w)=\{\hat\sigma_D(q, w)\}.$ не может быть равно. Объясните, пожалуйста. Добавлено через 20 минут Докажем, что если $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat{\sigma}_D(q, w)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q, w)=\{p\}$ для любой строки w, произвольного состояния q и состояния p. Доказательство будет проходить индукцией по длине w. Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?D=(Q, \Sigma, \delta_D, q_0,F)$ есть некоторый ДКА, N является НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?N=(Q, \Sigma, \delta_N, q_0,F)$ , который эквивалентный дка, где а-последний символ, где $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_N$ определена правилом: если $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_D(q, a) =p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_N(q, a) =\{p\}$ . Предположим n - любое число, индукцию ведём по n. База: Пусть \|w\|=0, т.е. w= $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ . Из базисных частей определений для ДКА и НКА имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_D((q_0, \varepsilon)=q_0$ , а $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,\varepsilon)= \{q_0\}$ Шаг Индукции: Пусть w-цепочка вида ха, т.е. а- последний символ в цепочке, а х-цепочка, состоящая из всех символов цепочки w, за исключением послелнего. Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma(q, w)=\sigma(\hat\sigma(q, x), a) <br />$ . Эта часть верна? 0

@AnD04 1 / 1 / 0 Регистрация: 21.01.2013 Сообщений: 99
	16.09.2022, 09:55 [ТС]	25
	То что я выделил в своём сообщении из вашего текста 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,660
	16.09.2022, 11:13	26
	Сообщение от AnD04 То что я выделил в своём сообщении из вашего текста Цитата в сообщении 23 содержит четыре предложения и не меньшее число утверждений. Например, среди этих утверждений есть "функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D\colon Q\times\Sigma\to Q$ " и " $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ есть состояние автомата". Ставя вопрос "Это утверждение относится к доказательству?" не уточнив, какое из них вы имеете в виду, вы затрудняете разговор. Кроме того, все утверждения в этой цитате говорят об определениях понятий из утверждения в сообщении 1, поэтому конечно они относятся к доказательству. Более того, фраза "если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a) = p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a) = \{p\}$ " вообще является частью утверждения из сообщения 1, которое требуется доказать. 0

@AnD04 1 / 1 / 0 Регистрация: 21.01.2013 Сообщений: 99
	07.11.2022, 17:58 [ТС]	27
	Доказательство Докажем, что если $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat{\sigma}_D(q, w)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q, w)=\{p\}$ для любой строки w, произвольного состояния q и состояния p. Доказательство будет проходить индукцией по длине w. Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?D=(Q, \Sigma, \delta_D, q_0,F)$ есть некоторый ДКА, N является НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?N=(Q, \Sigma, \delta_N, q_0,F)$ , который эквивалентный дка, где а-последний символ, где $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_N$ определена правилом: если $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_D(q, a) =p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi? \delta_N(q, a) =\{p\}$ . Предположим n - любое число, индукцию ведём по n.Согласно определению ДКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D:Qx\sigma\rightarrow Q$ , поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ есть элемент Q, то есть состояние автомата. Что такое $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ ? Согласно определению НКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N:Qx\sigma\rightarrow {2}^{Q}$ , где 2Q обозначает булеан Q, поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ есть подмножество элементов Q, то есть множество состояний. Это делает предположение "если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)=\{p\}$ " разумным: первая функция возвращает состояние, вторая — множество из одного этого состояния. База: Пусть \|w\|=0, т.е. w= $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ . Из базисных частей определений для ДКА и НКА имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_D((q_0, \varepsilon)=q_0$ , а $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,\varepsilon)= \{q_0\}$ Шаг Индукции: Пусть w-цепочка вида ха, т.е. а- последний символ в цепочке, а х-цепочка, состоящая из всех символов цепочки w, за исключением послелнего. Пусть оба множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,a)\}=\hat{\sigma}_N(q_0,a)$ состояний N представляют собой $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{p_1,p_2,...,p_k\}$ . По индуктивной части определения для НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,w)=\bigcup_i=1^k\sigma_N(p_i, a)$ (1). С другой стороны, конструкция подмножеств даёт $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(\{p_1,p_2,...,p_k\},a)\}=\bigcup_i=1^k\sigma_N(p_i,a).$ (2). Теперь, подставляя (2) в индуктивную часть определения для ДКА и используя тот факт, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q_0,x)={p_1,p_2,...,p_k}\}$ получаем : $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,x)=\{\sigma_D(\hat{\sigma}_D(q_0,x),a))\}=\{\sigma_D(\{p_1,p_2,...,p_k\},a)\}=\bigcup_.$ По индуктивной части определения для НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,w)=\bigcup_{i=1}^{k} \sigma_N(p_i, a)$ (1). С другой стороны, конструкция подмножеств даёт $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(\{p_1,p_2,...,p_k\},a)\}=\bigcup_{i=1}^{k} \sigma_N(p_i,a).$ (2). Теперь, подставляя (2) в индуктивную часть определения для ДКА и используя тот факт, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,x)\} =\{p_1,p_2,...,p_k\}$ получаем : $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,x)\} =\{\sigma_D(\{p_1,p_2,...,p_k\},a)\}=\bigcup_{i=1}^{k}\sigma_N(p_i, a).$ (3). Таким образом из уравнений (1) и (3) видно, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D(q,w)\} =\hat{\sigma}_N(q,w).$ Исправления доказательства Сообщение от AnD04 Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?D=(Q, \Sigma, \delta_D, q_0,F)$ есть некоторый ДКА, N является НКА $https://www.cyberforum.ru/cgi-bin/latex.cgi?N=(Q, \Sigma, \delta_N, q_0,F)$ , который эквивалентный дка] это не верно, так как множество не может быть равно подмножеству, я правильно понял? Добавлено через 30 минут Сообщение от AnD04 База: Пусть \|w\|=0, т.е. w= $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ . Из базисных частей определений для ДКА и НКА имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_D((q_0, \varepsilon)=q_0$ , а $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0,\varepsilon)= \{q_0\}$ тоже не верно. Будет правильно так: База :Пусть w= $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ . Значит $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_D((q_0, \varepsilon)=p$ , а $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat{\sigma}_N(q_0\varepsilon)= \{p\}$ , тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\hat{\sigma}_D((q_0, \varepsilon)\} = \hat{\sigma}_N(q_0,\varepsilon)$ Добавить утверждение в шаг индукции: Пусть w имеет длину n+1, и предположим, что утверждение справедливо для цепочки длины n. 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,660
	12.09.2022, 13:05	22
	Сообщение от AnD04 В математике фигурные скобки используют для обозначения множества Именно так. Сообщение от AnD04 по-этому равенство $https://www.cyberforum.ru/cgi-bin/latex.cgi? \hat\sigma_N(q, w)=\{\hat\sigma_D(q, w)\}.$ не может быть равно. Вот цитата из вашего сообщения № 17. Сообщение от AnD04 Докажем, что если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma_D(q, w)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma_N(q, w)=\{p\}$ для любой строки w и состояния p. В математике можно равные подставлять вместо равных. То есть, если доказано, что x = y, то для любое утверждение P(x) эквивалентно P(y). В утверждении выше есть предположение $https://www.cyberforum.ru/cgi-bin/latex.cgi?p=\hat\sigma_D(q, w)$ . Значит, используя факт о подстановке, мы получаем, что требуемое утверждение $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma_N(q, w)=\{p\}$ эквивалентно $https://www.cyberforum.ru/cgi-bin/latex.cgi?\hat\sigma_N(q, w)=\{\hat\sigma_D(q, w)\}$ . Вообще при чтении и составлении разных утверждений чрезвычайно важно следить за типом сущности, которую обозначает каждая переменная, выражение и его часть. Так, нужно четко понимать, обозначает ли переменная число, кортеж чисел, множество, матрицу, геометрическую фигуру и т.п. В данном случае нужно задать вопрос: что такое $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ ? Согласно определению ДКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D\colon Q\times\Sigma\to Q$ , поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ есть элемент Q, то есть состояние автомата. Что такое $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ ? Согласно определению НКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N\colon Q\times\Sigma\to 2^Q$ , где 2^Q обозначает булеан Q, поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ есть подмножество элементов Q, то есть множество состояний. Это делает предположение "если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a) = p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a) = \{p\}$ " разумным: первая функция возвращает состояние, вторая — множество из одного этого состояния. В этой теме у вас было несколько аналогичных тИповых ошибок (или, по крайней мере, несколько повторений одной ошибки). Это важно, потому что без проверки утверждений на типы сущностей невозможно ни понять доказательство, ни написать его. Утверждение с ошибками типов даже не неверно: оно бессмысленно. Поэтому обращайте на это внимание. Про остальную часть напишу позже. 0

@AnD04 1 / 1 / 0 Регистрация: 21.01.2013 Сообщений: 99
	14.09.2022, 08:56 [ТС]	23
	Согласно определению ДКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D$ [имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D:Qx\sigma\rightarrow Q$ , поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)$ есть элемент Q, то есть состояние автомата. Что такое $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ ? Согласно определению НКА функция $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N$ имеет сигнатуру $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N:Qx\sigma\rightarrow {2}^{Q}$ , где 2Q обозначает булеан Q, поэтому $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)$ есть подмножество элементов Q, то есть множество состояний. Это делает предположение "если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_D(q, a)=p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta_N(q, a)=\{p\}$ " разумным: первая функция возвращает состояние, вторая — множество из одного этого состояния. Это утверждение относится к доказательству? Если "да", то к какой части? 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,660
	14.09.2022, 14:33	24
	Сообщение от AnD04 Это утверждение относится к доказательству? Какое утверждение? 0