Композиция, иттерация, разветвление

Пусть машины Т₁ и Т₂ имеют соответственно программы П₁ и П_2.Предположим, что внутренние алфавиты этих машин не пересекаются и что - некоторое заключительное состояние машины Т₁, а - какое-либо начальное состояние машины Т₂. Заменим всюду в программе П₁ состояние на состояние и полученная программа П определяет машину Т, называемую композицией машин Т1 и Т2 (по паре состояний (, )) и обозначаемую через Т₁◦Т₂или Т₁Т₂ (более подробно: Т=Т(Т₁,Т₂, (, )). Внешний алфавит композиции Т₁Т₂ является объединением внешних алфавитов машин Т₁ и Т_2.

5.9. Построить композицию машины Т₁Т₂ по паре состояний (q₁₀,q₂₁) и найти результат применения композиции к слову Р (q₂₀ – заключительное состояние машины T₂)

		q₁₁	q₁₂			q₂₁	q₂₂
T₁	0	q₁₂ 0 R	q₁₀ 1 L	T₂	0	q₂₂ 1 R	q₂₂1 R
	1	q₁₂ 1 R	q₁₁ 0 R		1	q₂₁ 0 L	q₂₀ 1 S

a) P=1³0²1²б) Р=1⁴01

		q₁₁	q₁₂	q₁₃			q₂₁	q₂₂
T₁	0	q₁₀ 0 L	q₁₃ 0 R	q₁₁ 0 R	T₂	0	q₂₂ 1 L	q₂₀0 R
	1	q₁₂ 1 R	q₁₃ 1 R	q₁₁ 0 R		1	q₂₂ 1 L	q₂₁ 0 L

а) Р=1¹0²1³01², б) Р=1²0101³

		q₁₁	q₁₂	q₁₃			q₂₁	q₂₂	q₂₃
T₁	0	q₁₂ 0 R	q₁₃ 0 R	q₁₀ 1 L	T₂	0	q₂₂ 0 L	q₂₃0 L	q₂₀0 R
	1	q₁₁ 1 R	q₁₁ 1 R	-		1	q₂₁ 1 L	q₂₂ 1 L	q₂₃ 1 L

a) P=1²01³01², б) Р=1²01²0²1²

Пусть - некоторое заключительное состояние машины Т, а - какое-либо состояние машины Т_,не являющееся заключительным. Заменим всюду в программе П машины Т символ на . Получим программу , определяющую машину (, ). Машина называется итерацией машины Т (по паре состояний (, )).

5.10. Найти результат применения итерации машины Т к слову Р по паре состояний (q₀,q_i) (заключительными состояниями являются q₀и q₀’)

1) i=1,

a) P=1^3k, b) P=1^3k+1, c) P=1^3k+2, k>=1

	q₁	q₂	q₃	q₄	q₅
0	q₀0 S	q₄0 S	q₅0 S	q₄1 R	q₀’ 0 R
1	q₂0 R	q₃0 R	q₁0 R	-	-

2) i=1,

a) P=1^2k, b) P=1^2k+1, k>=1

	q₁	q₂	q₃	q₄	q₅	q₆
0	q₀’ 0 R	q₀’ 0 R	q₄0 R	q₅1 L	q₆0 L	q₀0 R
1	q₂0 R	q₃0 R	q₃1 R	q₄1 R	q₅1 L	q₆1 L

3) i=3,

a) P=1^x01^y, x,y>=1

	q₁	q₂	q₃	q₄	q₅	q₆
0	q₀ 0 L	-	q₄0 R	q₅1 L	q₆0 L	q₀’ 0 R
1	q₁2 R	q₂1 R	-	q₄1 R	q₅1 L	q₆1 L
2	-	q₃1 R	-	-	-	q₀1 R

Пусть машины Т₁, Т₂, Т₃имеют соответственно программы П₁, П₂, П_3.Предположим, что внутренние алфавиты этих машин не пересекаются. Пусть и - некоторые различные заключительные состояния машины Т₁. Заменим всюду в программе П₁ состояние некоторым начальным состоянием машины Т₂, а состояние - некоторым начальным состоянием машины Т₃. Затем новую программу объединим с программами П₂ и П_3. Полученная программа П определяет машину Т= Т(Т1(, ),Т2(, ),Т3), называемую разветвлением машин Т₂ и Т₃, управляемым машиной Т1.

5.11. Найти результат применения разветвления машины Т= Т(Т1(, ),Т2(, ),Т3), к слову Р (q₂₀ – заключительное состояние машины T₂, а q₃₀ – заключительное состояние машины T₃).

1) a) P=101³, b) P=1³01

		q₁₁	q₁₂			q₂₁			q₃₁	q₃₂
T₁	0	q₁₂ 0 R	q’₁₀ 0 R	T₂	0	q₂₀ 1 S	T₃	0	q₃₂1 L	q₃₀1 L
	1	q₁₂ 1 R	q’’₁₀ 1 L		1	q₂₁ 0 R		1	q₃₁1 L	-