5.3.1.1. Нумерация МТ
A={a0,..,ai,…} – внешний алфавит МТ (счетное множество).
Q={q0, q1, …, qj,…} – внутренние состояния МТ (счетное множество).
Пусть для всех МТ a0 – пустой символ, q0 – заключительное состояние, q1 – начальное состояние.
Каждому символу из множества {Л, П, С, a0, a1,…, ai,…, q0, q1, …qj… } поставим в соответствие двоичное число:
Символ | Код | Число нулей в коде | |
Д | Л | 10 | 1 |
П | 100 | 2 | |
С | 1000 | 3 | |
А | а0 | 10000 | 4 |
а1 | 1000000 | 6 | |
… | |||
ai | 10………0 | 2i+4 | |
…. | |||
Q | q0 | 100000 | 5 |
q1 | 10000000 | 7 | |
…. | |||
qj | 10………0 | 2j+5 | |
… |
Команде МТ поставим в соответствие двоичное число:
.
Упорядочим команды МТ в соответствии с лексикографическим порядком левых частей команд q1a0, q1a1,…q2a0,…. и т. д. Получим последовательность команд I1,…In(m+1), где n – число символов в алфавите А, m – число состояний в множестве Q.
Тогда МТ можно поставить в соответствие двоичное число вида:
Код(Т)=Код(I1)Код(I2) …..Код(In(m+1)).
Пример.
A={a0,a1}
Q={q0,q1}
I1:q1a0→q0a0C
I2:q1a1→q0a1C
Тогда Код(Т)=
Такое кодирование является алгоритмической процедурой. Зная код МТ можно однозначно восстановить множество ее команд. Код МТ можно рассматривать как двоичную запись натурального числа. Такое число называется номером МТ.