64821-матлогика-3

n=5: 3125A + 625B + 125C + 25D + 5E + F = 1235

n=6: 7776A + 1296B + 216C + 36D + 6E + F = 2531

Решая систему, получим:

A=1/5; B=1/2; C=1/3; D=0; E=-1/30; F=0.

В итоге получим:

.

Докажем полученное равенство методом математической индукции:

1. база индукции. При n=1 получим:

.

2. Предположим, что формула верна для n (***).

Проверим ее справедливость для n+1.

(1)

(2)

Докажем, что (1)=(2).

Выражение верно, что и требовалось доказать.

Ответ: .

Задание к контрольной работе № 3

1. Составить программу, таблицу соответствия и граф алгоритма для машины Тьюринга по заданной начальной и конечной конфигурации, используя алфавит A={|,#}.

2. Проверить решение на некоторых значениях аргументов.

По варианту 3:

Решение

- усеченное вычитание

Алгоритм:

1. Удаляем «лишнее» слово y и выполняем операцию сложения (x+z);

2. Выполняем операцию усеченного вычитания ().

Реализация:

1. Сначала нужно «дойти» до начала слова y и стереть символ «#» перед ним.

Состояние	Символы внешнего алфавита
	|		#
q0	q1|R		q2#R
q1	q1|R		q2R
Дошли до начала слова y, стерли символ «#»
q2	q2R		q3R
Удалили все символы «|» в слове y и символ «#» между y и z
q3		q3|R		q4#R

В итоге получаем следующее:

2. Выполняем операцию усеченного вычитания ();

Будем последовательно заменять первые символы слова s и последние символы слова t на знак «*». Действия продолжаются до тех пор, пока одно из слов s или t не будет состоять из одних только символов «*».

Т.е. в итоге получим либо вид

(переход в состояние q₁₂)

либо вид

. (переход в состояние q₁₂)

Состояние	Символы внешнего алфавита
	|	#	*
q4	q5*R
q5	q5 | R	q8#R
В слове (x) заменили «|» на «*», дошли до начала слова z
q6	q7|R	q8#L	q12*L
		Если s=0	Если в слове s больше нет знаков «|»
q7	q7|R	q12#L	q8*L
q8	q9*L
q9	q9 | L	q10#L
q10	q11 |L		q12*R
q11	q12 |L		q5*R

В итоге указатель будет находиться в состоянии q₁₂ между словами (s) и (t).

После этого нужно:

• Переместить указатель в начало слова (s);

• двигаясь вправо, стереть все «*» в слове (s) и «лишний» разделитель «#»;

• двигаясь вправо, стереть все слово (t).

Состояние	Символы внешнего алфавита
	|	#	*
q12	q12|L	q13#R	q15*L
q13	q13 | R	q14 R	q13 R
q14	q14 R	q15 # R	q14R

В итоге указатель находится в конце слова .

Проверка:

а) пусть x=|||; y=||||; z=||; s=|||; t=|, тогда

.

б) пусть x=|; y=||; z=|||; s=|; t=|||, тогда

16