Пусть машины Т1 и Т2 имеют соответственно программы П 1 и П 2. Предположим, что внутренние алфавиты этих машин не пересекаются и что - некоторое заключительное состояние машины Т1, а - какое-либо начальное состояние машины Т2. Заменим всюду в программе П 1 состояние на состояние и полученная программа П определяет машину Т, называемую композицией машин Т1 и Т2 (по паре состояний (, )) и обозначаемую через Т1◦Т2 или Т1Т2 (более подробно: Т=Т(Т1,Т2, (, )). Внешний алфавит композиции Т1Т2 является объединением внешних алфавитов машин Т1 и Т2.
5.9. Построить композицию машины Т1Т2 по паре состояний (q10,q21) и найти результат применения композиции к слову Р (q20 – заключительное состояние машины T2)
1)
q11 | q12 | q21 | q22 | ||||
T1 | 0 | q12 0 R | q10 1 L | T2 | 0 | q22 1 R | q22 1 R |
1 | q12 1 R | q11 0 R | 1 | q21 0 L | q20 1 S |
a) P=130212 б) Р=1401
2)
q11 | q12 | q13 | q21 | q22 | ||||
T1 | 0 | q10 0 L | q13 0 R | q11 0 R | T2 | 0 | q22 1 L | q20 0 R |
1 | q12 1 R | q13 1 R | q11 0 R | 1 | q22 1 L | q21 0 L |
а) Р=110213012, б) Р=1201013
3)
q11 | q12 | q13 | q21 | q22 | q23 | ||||
T1 | 0 | q12 0 R | q13 0 R | q10 1 L | T2 | 0 | q22 0 L | q23 0 L | q20 0 R |
1 | q11 1 R | q11 1 R | - | 1 | q21 1 L | q22 1 L | q23 1 L |
|
|
a) P=12013012, б) Р=120120212
Пусть - некоторое заключительное состояние машины Т, а - какое-либо состояние машины Т, не являющееся заключительным. Заменим всюду в программе П машины Т символ на . Получим программу , определяющую машину (, ). Машина называется итерацией машины Т (по паре состояний (, )).
5.10. Найти результат применения итерации машины Т к слову Р по паре состояний (q0,qi) (заключительными состояниями являются q0 и q0’ )
1) i=1,
a) P=13k, b) P=13k+1, c) P=13k+2, k>=1
q1 | q2 | q3 | q4 | q5 | |
0 | q0 0 S | q4 0 S | q5 0 S | q4 1 R | q0’ 0 R |
1 | q2 0 R | q3 0 R | q1 0 R | - | - |
2) i=1,
a) P=12k, b) P=12k+1, k>=1
q1 | q2 | q3 | q4 | q5 | q6 | |
0 | q0’ 0 R | q0’ 0 R | q4 0 R | q5 1 L | q6 0 L | q0 0 R |
1 | q2 0 R | q3 0 R | q3 1 R | q4 1 R | q5 1 L | q6 1 L |
3) i=3,
a) P=1x01y, x,y>=1
q1 | q2 | q3 | q4 | q5 | q6 | |
0 | q0 0 L | - | q4 0 R | q5 1 L | q6 0 L | q0’ 0 R |
1 | q1 2 R | q2 1 R | - | q4 1 R | q5 1 L | q6 1 L |
2 | - | q3 1 R | - | - | - | q0 1 R |
Пусть машины Т1, Т2, Т3 имеют соответственно программы П 1, П2, П3. Предположим, что внутренние алфавиты этих машин не пересекаются. Пусть и - некоторые различные заключительные состояния машины Т1. Заменим всюду в программе П1 состояние некоторым начальным состоянием машины Т2, а состояние - некоторым начальным состоянием машины Т3. Затем новую программу объединим с программами П2 и П3. Полученная программа П определяет машину Т= Т(Т1(, ),Т2(, ),Т3), называемую разветвлением машин Т2 и Т3, управляемым машиной Т1.
5.11. Найти результат применения разветвления машины Т= Т(Т1(, ),Т2(, ),Т3), к слову Р (q20 – заключительное состояние машины T2, а q30 – заключительное состояние машины T3).
|
|
1) a) P=1013, b) P=1301
q11 | q12 | q21 | q31 | q32 | ||||||
T1 | 0 | q12 0 R | q’10 0 R | T2 | 0 | q20 1 S | T3 | 0 | q32 1 L | q30 1 L |
1 | q12 1 R | q’’10 1 L | 1 | q21 0 R | 1 | q31 1 L | - |
2) a) P=1x021, x>=1, b) P=1x0101y01z, x,y,z>=1
q11 | q12 | q13 | q21 | q22 | q31 | q32 | ||||||
T1 | 0 | q12 0 R | q’10 0 L | q’’10 0 R | T2 | 0 | q22 0 L | q20 0 R | T3 | 0 | q32 0 R | q30 1 S |
1 | q11 1 R | q13 1 R | q13 1 R | 1 | q21 1 L | q22 1 L | 1 | q31 1 R | q31 1 R |
5.12По программе МТ написать аналитическое выражение для функций f(x) и f(x,y), вычисляемых МТ.
1) 2)
q1 | q2 | q1 | q2 | q3 | q4 | q5 | |||||
0 | q21L | q00R | 0 | q30R | q10L | q40L | q40L | q00R | |||
1 | q11R | q 21L | 1 | q11R | q30R | q30R | q51L | q51L |
3)
q1 | q2 | q3 | q4 | q5 | q6 | q7 | q8 | q9 | |
0 | q20R | q30R | q01S | q50R | q30L | q70L | - | q90L | q10R |
1 | q20R | q41R | q81L | q41R | q61R | q61R | q80L | q81L | q91R |
4) f(x)-? В начальной конфигурации обозревается крайняя правая единица ленты
5) f(x,y)-? В начальной конфигурации обозревается крайняя правая единица ленты
4) 5)
q1 | q2 | q3 | q1 | q2 | q3 | q4 | q5 | q6 | ||||||
0 | q21L | q31R | q00 | 0 | q20R | q10L | q40R | q40L | q60R | q00 | ||||
1 | q11R | q21L | q01 | 1 | q11R | q30R | q30R | q51L | q51L | q01 |