Абстрактний автомат. Робота автомата. Способи завдання

Задачі

Лічильник, на вхід якого подаються двоїчні цифри 0 і 1, підраховує за модулем 3 загальне число одиниць, що надійшли на його вхід, необхідно:

визначити вхідний, вихідний алфавіти і безліч станів;

записати таблицю переходів-виходів відповідного автомата;

побудувати граф автомата і його матрицю з'єднань (суміжності);

визначити тип автомата.

Побудувати таблиці переходів-виходів і матриці з'єднань (суміжності) для автоматів А₁, А₂ (рис. 5.1.).

Рис. 5.1. Графи автоматів А₁ і А₂

Текст в алфавіті з 32 букв і пропусків між словами сканується для підрахунку слів, що починаються з букви «а» і закінчуються на букви «ія». Букви, крім «а», «і», «я» позначаються через «a», пропуск - через «b». Вхідний і вихідний алфавіти, безліч станів рівні: X = {а, і, я, a, b}, Y = {вважати, не вважати}, S = {нове слово, поява «а...,» поява «а...і», поява «а...ія», чекання нового слова}. Необхідно:

записати таблицю переходів-виходів відповідного автомата;

побудувати граф автомата і його матрицю з'єднань (суміжності);

визначити тип автомата.

Автомат А₃ заданий матрицею з'єднань (табл. 5.1.), необхідно:

визначити безліч станів, вхідний і вихідний алфавіти;

записати таблицю переходів-виходів відповідного автомата;

побудувати граф автомата і визначити тип автомата;

знайти наскрізний, ізольований і тупиковий подавтоматы для А₄.

Таблиця 5.1

	0/1Ú1/0
		0/0		1/1
			0/1Ú1/1
			0/1		1/0
			0/1					1/1
						0/1Ú1/0
					1/0			0/1
						0/0Ú1/1

Визначити, які з автоматів А₄, А₅, А₆ (рис. 5.2.), є еквівалентними.

Рис. 5.2. Автомати А₄, А₅, А₆

На входи однорозрядного послідовного суматора подаються розряди двох доданків у коді 0 чи 1, а виходом є розряд суми за модулем 2. Суматор має два стани, обумовлені значеннями переносу (0 чи 1). Показати, що суматор можна представити автоматами А₇, А₈ (рис. 5.3.).

Рис. 5.3. Автомати Мура А₇ і Мілі А₈