Математические основы теории систем

41

2.2 Виды автоматов и их свойства

Дадим несколько определений, которые понадобятся для дальнейшего изложения.

·····························································

Состояние qj называется достижимым из состояния qi, если существует входное слово x, такое, что δ(qi ,x) = qj . Автомат

называется сильно связанным, если из любого его состояния достижимо любое другое состояние.

·····························································

2.2.1 Автономные автоматы

·····························································

Автомат называется автономным по входу, если его входной алфавит состоит из одной буквы: X ={x}. Все входные слова

у такого автомата имеют вид xx…x.

·····························································

Из произвольного автомата с входным алфавитом X ={x1,…xm} может быть построено m различных автономных по входу автоматов исключением из графа переходов автомата всех ребер, кроме ребер с выбранной буквой xi (i =1,…,m).

·····························································

Аналогично, автомат называется автономным по выходу, если его выходной алфавит состоит из одной буквы Y ={y}.

·····························································

Автономный по выходу автомат получается из произвольного автомата с выходным алфавитом Y = {y1, y2 ,...yk } исключением из графа переходов ребер со всеми выходными буквами кроме выбранной буквы yi .

Таблица автономного автомата по входной букве, например x2, получится удалением всех столбцов, кроме столбца с буквой x2 (табл. 2.3).

47

Таблица 2.9 – Автомат Мили к примеру 2.5

·······································································

Можно проверить, что автомат Мили В, заданный таблицей 2.9, индуцирует такое же автоматное отображение, что и автомат Мура А, определяемый таблицей 2.8.

Таким образом, при исследовании автоматов достаточно пользоваться только автоматом Мура. Это в некоторых случаях удобнее потому, что автомат Мура можно рассматривать как автомат без выходов, состояния которого различным образом отмечены. Можно считать, что таких отметок вообще две (например, 0 и 1) и они делят состояния на два класса, один из которых можно назвать заключительным. Это позволяет дать еще одно определение абстрактного автомата − автомата без выходов S = (X ,Q,Y ,λ,q1, F ), где F Q − мно-

жество заключительных состояний, а q1 − начальное состояние автомата. Вспоминая понятие автономного автомата, можно сказать, что автомат

Мили может быть представлен как совокупность автономных автоматов по входным и выходным буквам. В случае автоматов Мура имеет смысл говорить об автономных автоматах только по входным буквам.

2.2.4 Автоматы первого и второго рода

Вспомним интерпретацию автомата как некоторого устройства, работающего в дискретном времени. Первопричиной появления выходного сигнала и изменения состояния является входной сигнал. Следовательно, выходной сигнал y(t) всегда появляется после входного сигнала x(t). Однако относительно

времени t перехода автомата из состояния q(t −1) в состояние q(t) выходной сигнал может появиться либо раньше, либо позже этого момента времени.

В первом случае уравнения, описывающие работу автомата, будут следующие:

q(t) = δ(q(t −1), x(t)),

(2.6)

y(t) = λ(q(t −1), x(t)),

а автомат будет именоваться автоматом первого рода.

48

Во втором случае получаем автомат второго рода с уравнениями:

q(t) = δ(q(t −1), x(t)),

(2.7)

y(t) = λ(q(t), x(t)).

В уравнениях (2.6) и (2.7) функция λ называется либо обычной (для автоматов первого рода), либо сдвинутой (для автоматов второго рода) функцией выхода.

Установим взаимосвязь между автоматами первого и второго рода. Пусть дан автомат второго рода S = (X ,Q,Y,δ,λ) . Запишем функцию переходов δ(q,x) и сдвинутую функцию выхода λ(q,x):

y(t) = λ(q(t), x(t)), q(t) = δ(q(t −1), x(t)).

Подставим в первое уравнение q(t), определяемое вторым уравнением. Тогда получим уравнение

y(t) = λ(δ(q(t −1),x(t)),x(t)) = λ′(q(t −1), x(t)),

определяющее обычную функцию выхода λ′(q, x), которая характеризует автомат первого рода. Таким образом, подставляя в сдвинутую функцию выхода λ(q,x) автомата второго рода функцию переходов δ(q,x), получаем автомат первого рода S′ ={X,Q,Y,δ,λ′}, который индуцирует то же самое автоматное отображение, что и автомат S. Такое сведение автомата второго рода к эквивалентному автомату первого рода называется интерпретацией автомата второго рода автоматом первого рода.

49

Предположим, что автомат А является автоматом первого рода. Тогда функция выхода λ(q, x) , полученная из таблицы 2.10 и представленная в таблице 2.11, будет являться обычной функцией выхода.

Таблица 2.11 – Обычная функция выхода автомата к примеру 2.6

Если на вход автомата, находящегося первоначально в состоянии 1, поступит слово x = x1x1x2 x3 x2 x3 , то на выходе будет слово y = y1 y2 y1 y1 y2 y1.

Теперь предположим, что автомат А является автоматом второго рода. Тогда таблица 2.10 определяет сдвинутую функцию выхода. При поступлении на вход автомата второго рода слова x = x1x1x2 x3 x2 x3 , такого же, как и в случае автомата первого рода, на выходе появится слово y = y2 y1 y1 y2 y1 y2 , которое отличается от соответствующего выходного слова автомата первого рода. Поэтому отображение, индуцируемое автоматом первого рода, отличается от отображения, индуцируемого автоматом второго рода.

Построим автомат A′ первого рода, эквивалентный автомату А первого рода. Подставляя в сдвинутую функцию выхода λ(q, x) , заданную в таблице 2.11, функцию перехода δ(q, x) из таблицы 2.12, получим обычную функцию выхода λ′(q, x) (см. табл. 2.13).

50

Таблица 2.13 – Сдвинутая функция выхода автомата к примеру 2.6

·······································································

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

Необходимо еще раз подчеркнуть, что автоматы первого и второго рода мы различаем, когда интерпретируем работу конечного абстрактного автомата некоторым реальным устройством.

В дальнейшем по умолчанию будем считать, что задан автомат первого рода, если не оговорено обратное.