<<
>>

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

Тогда Код(Т)=

Такое кодирование является алгоритмической процедурой. Зная код МТ можно однозначно восстановить множество ее команд. Код МТ можно рассматривать как двоичную запись натурального числа. Такое число называется номером МТ.

<< | >>
Источник: Викентьева О. Л.. Математическая логика и теория алгоритмов. Конспект лекций для студентов специальностей АСУ, ЭВТ, КЗИ. Пермь, 2007г.. 2007

Еще по теме 5.3.1.1. Нумерация МТ: