Как проверить работу автомата над словом

Решение

Построим сам граф. Столбцы – вершины графа, строки – его рёбра. Если ребро инцидентно вершине, то клетка будет закрашена. Получим:

Составим остовное дерево для данного графа. Остовное дерево графа – это подграф графа, состоящий из всех вершин графа и минимального числа рёбер так, чтобы из любой вершины можно добраться в любую. Сначал включаем в оствное дерево ребро Ребро добавляет к остовному дереву вершину , его также включаем. Ребро добавляет к остовному дереву вершину , его также включаем. Ребро добавляет к остовному дереву вершину , его также включаем. Ребро добавляет к остовному дереву вершину , его также оставляем. Ребро добавляет к остовному дереву вершину , его также оставляем. Ребро не добавляет к остовному дереву новых вершин, поэтому его в остовное дерево не включаем. Ребро добавляет к остовному дереву вершину , поэтому его также включаем. В остовное дерево включены все вершины графа, поэтому остовное дерево построено.

4. А) Написать таблицу состояний данного автомата.

б) Считая автомат неинициальным, построить эквивалентный автомат Мура. Проверить работу данного и построенного автоматов над одним и тем же словом.

Определение реакции автомата на входное слово

Пусть на вход автомата Мили А_А и эквивалентного ему автомата Мура А_В из примера 4.3 поступает входное слово . Рассмотрим реакцию автоматов на входное слово.

Для автомата Мили имеем: ; , т.е. под действием символа х₁ автомат переходит в состояние с выходом у₁; при следующем символе получим: ; и т. д. В результате получим последовательность состояний и выходное слово:

входное слово x	—	= k *
cостояния S		= k+1
выходное слово h	—	= k

Для автомата Мура А_В имеем: при вхождении символа х₁ автомат находился в состоянии с выходом , ; . Далее поступает следующий символ х₁ в состоянии с выходом и т.д. Последовательность входных и выходных символов, а также символов состояний выглядит аналогично представленным выше для автомата Мили:

входное слово x	—	= k
cостояния S		= k+1
выходное слово h		= k+1

Видно, что реакция автоматов А_А и А_В на входное слово совпадают с точностью до сдвига на один такт; это получилось потому, что реакция автомата Мура на входную букву наступает в следующем такте. Так будет и в общем случае, если автоматы эквивалентны и разных типов. Проверка этого утверждения предоставляется студентам.

Проверить работу машины Тьюринга над некоторыми словами.

Будем обозначать состояния машины Тьюринга числами 0, 1, 2, 3, …, причем 1 – начальное, а 0 – заключительное состояния.

Вначале с помощью команд проходим до конца слова, не изменяя его символов.

Признаком окончания слова будет считывание в первом состоянии.

С помощью команд движемся влево, не изменяя последнего символа.

Если в состоянии 3 считываем a, значит, , нужно стирать все символы слова , кроме последнего. Это можно сделать с помощью команд . Если в состоянии 4 считывается , значит, вся работа проделана, и пора останавливаться с помощью команды .

Если в состоянии 3 считываем символ b, значит, , нужно все символы, кроме x_n, заменять буквами b. Это делаем с помощью команд . Если в состоянии 5 считывается , значит, все символы исходного слова пройдены, можно переходить в состояние 0 с помощью команды .

Запишем программу найденной машины Тьюринга в виде таблицы:

Л2	—	—	Н0	Н0
a	aП1	aЛ3	Л4	Л4	bЛ5
b	bП1	bЛ3	bЛ5	Л4	bЛ5

2. Проверим работу построенной машины Тьюринга над словами abba:

Итак, в слове abba предпоследний символ – b, и все буквы исходного слова, кроме последней, заменены буквой b.

Проверим работу построенной машины Тьюринга над словом bbaaa:

В слове bbaaa предпоследний символ – a, и все буквы исходного слова, кроме последней, заменены пустыми символами .

Итак, проверка сделана, результат работы машины Тьюринга удовлетворяет требованиям, которые ставились в условии задачи.

Задание 2.

3. Построить машину Тьюринга, вычисляющую числовую функцию .