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
Тогда Код(Т)=
Такое кодирование является алгоритмической процедурой. Зная код МТ можно однозначно восстановить множество ее команд. Код МТ можно рассматривать как двоичную запись натурального числа. Такое число называется номером МТ.