Задачи

2.1. Постройте таблицу переходов, граф переходов и матрицу переходов для случаев, сформулированных в задачах Для каждого случая рассмотрите число возможных начальных состояний и входных последовательностей и подтвердите, что выходные последовательности, получаемые на основании различных представлений, соответствуют тем, которые предполагались соответствующими словесным описаниям.

2.2. Известно, что конечный автомат имеет входной алфавит выходной алфавит и множество состояний Начертите граф переходов, удовлетворяющий этим условиям.

2.3. Подсчитайте число различных: (а) -автоматов, в которых реакция в настоящий момент зависит только от состояния в настоящий момент и не зависит от входного сигнала в настоящий момент; (б) -автоматов, в которых и из каждого состояния можно перейти в любое другое, подав на автомат один входной символ; (в) -автоматов, в которых нет изолированных состояний; , - автоматов, в которых каждый из q выходных символов появляется в таблице переходов, по крайней мере, один раз (достаточно получить рекуррентную формулу для подсчета этого числа автоматов).

2.4. Постройте автомат, изоморфный автомату, изображенному таблицей 3 2.1, посредством замены обозначений состояний 1, 2, 3,

Таблица 3 2.1

4, 5 и 6 на 2, 3, 4, 5, 6 и 1 соответственно. Без построения всего семейства перестановок автомата покажите, что это семейство имеет мощность, равную

2.5. Покажите, что если b обозначает число дуг в графе переходов , -автомата, то

2.6. (а) Постройте таблицу переходов и матрицу переходов автомата, изображенного на рис. 3 2.1. (б) Определите преходящие, тупиковые и изолированные состояния в автомате, (в) Определите для этого автомата

2.7. Пусть — состояние из множества состояний S автомата М. Пусть — достижимое множество и пусть множество состоит из элементов множества S, не содержащиеся в

Покажите, что: (а) если представляют собой два изолированных подавтомата автомата если представляют тупиковый и преходящий автоматы соответственно; (в) если не содержит изолированных подавтоматов.

Рис. 3 2.1.

2.8. Таблица 3 2.2 представляет автомат А. (а) Найдите G ( 5,6) для автомата А. (б) Используя результаты задачи 2.7, покажите, что G ( 6) представляет изолированный подавтомат, a G ( 2) - тупиковый подавтомат, (в) Найдите максимальное разложение автомата А.

Таблица 3 2.2

2.9. Постройте таблицу переходов для расщепляемого автомата, который состоит из автоматов А, Б и В, изображенных на рис. 3 2.2.

2.10. Пусть — множество всех состояний автомата М, из которых можно попасть в любое состояние множества при подаче входных последовательностей длины k или меньше.

Рис. 3.2.2.

(а) Сформулируйте алгоритм для определения -множества состояний, из которых достижимо при подаче входной последовательности любой длины, (б) Примените алгоритм к автомату А из задачи 2.8 при (в) Покажите, что

2.11. Автомат А огрзделен матрицей переходов (а) Определите преходящие, тупиковые и изолированные состояния автомата А. (б) Определите (5, 7) и ( 2, 3). (в) Путем изменения порядка строк и столбцов в определите, составляют ли множества состояний пару из преходящего и тупикового подавтоматов, пару изолированных подавтоматов или пару автоматов, не принадлежащих ни к одному из указанных типов.

2.12. (а) Покажите, что если -единственный ненулевой влемент в строке матрицы -единственный ненулевой

элемент в i - й строке матрицы любого целого ). (б) Покажите, что если единственный ненулевой элемент в столбце матрицы то единственный ненулевой элемент в столбце любого целого .

2.13. Покажите, что (для всех ).

2.14. Для автомата А из задачи 2.11 постройте: установите, что А не имеет полных контуров.

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

2.16. Подсчитайте число различных скелетных матриц и скелетных модифицированных матриц, которые описывают , - автоматы.

2.17. Требуется определить, существует ли в автомате М путь, который ведет из через и если существует, то определить длину минимального пути, соответствующего такому переходу. Сформулируйте алгоритм для решения этой задачи.

2.18. На автомат состояниями требуется подать такую входную последовательность, чтобы, начиная из состояния автомат перешел в состояние через входных символов (где ) и в состояние через символов. Полагая, что элементом матрицы является элемент найдите число возможных последовательностей, которые отвечают сформулированным требованиям.

2.19. Граф переходов автомата М имеет n состояний, обозначенных и m дуг, обозначенных матрица с элементом , обозначенным через определяется так:

- матрица с элементом обозначенным через определяется так:

Покажите, что , где является транспонированной матрицей

2.20. Используя методику частичного построения матриц, описанную в § 2.13, ответьте на следующие вопросы, относящиеся к автомату, представленному таблицей 3 2.3: (а) Какие кратчайшие входные последовательности переводят автомат из состояния 3 В состояние (б) Какие входные последовательности длины 4 или

меньше переводят автомат из состояния 3 снова в состояние 3? (в) Имеет ли автомат полные контуры? Если имеет, то составьте входную последовательность, которая соответствует полному контуру, начинающемуся в состоянии 3.

Таблица 3.2.3