14. Способы задания конечных автоматов.

Работа конечного автомата может быть задана (описана) тремя способами.

1. С помощью таблиц переходов и выходов.

Задаются таблицы переходов и выходов. В таблице выходов ставятся соответствия, выходного слова, входного и состоянию, соответственно таблице переходов.

Пример:

Конечный автомат задан на множества.

X = {x₁, x₂}

Y = {y₁, y₂ y₃}

S = [s₀, s₁, s₂, s₃]

Задана следующая таблица выходов:

xi / Si	s0	s1	s2	s3
x1	y1	y2	y3	y3
x2	y3	y2	y3	y1

Задана следующая таблица переходов:

xi / Si	s0	s1	s2	s3
x1	s1	s0	s0	s3
x2	s2	s0	s2	s3

Иногда, эти таблицы объединяют.

xi / Si	s0	s1	s2	s3
x1	y1 / s1	y2 / s0	y3 / s0	y3 / s3
x2	y3 / s2	y2 / s0	y3 / s2	y1 / s3

2. Методами теории графов.

Конечный автомат представляется О-графом (?), в котором вершина поставлена в соответствие состоянию конечного автомата, а направленные дуги указывают направление перехода из состояния в состояние.

Фото.

Коммент: Под действием слова x₁ перейдёт в состояние s₂ и выработает слово y₁.

Состояние автомата, соответствующая вершина которого не имеет исходящих дуг, а имеет хотя бы одну входящую, называется преходящая.

Тупиковым называется состояние автомата, соответствующая вершина которого не имеет исходящих дуг, а имеет только входящие (заходящие).

Под изолированным состоянием понимается такое состояние, соответствующая вершина которого не имеет ни исходящих, ни входящих дуг и может иметь только петли.

3. С помощью матриц.

15. Элементарные конечные автоматы.

Автомат называется элементарным, если он обладает следующими свойствами:

• Имеет два внутренних состояния.

• Входной и выходной алфавиты – двоичны.

• Работа такого автомата описывается моделью Мура.

  • Y(t+1) = F_λ[S(t)]

  • S(t+1) = F_δ[X(t), S(t)]

• Обладает полной системой переходов и выходов.

Для элементарного автомата с двумя внутренними состояниями, полная система переходов выглядит следующим образом:

Q(t) → Q(t+1)

0 → 0

1 → 0

0 → 1

1 → 1

Конечные автоматы обладают полной систему выходов (Y(t) -> Y(t+1)) и переходов (S(t) -> S(t+1)) если найдётся хотя бы один входной сигнал, который переводит конечный автомат из одного состояния в другое для каждой пары его состояний (Q и ¯Q). Если в каждом состоянии конечный автомат имеет выходной сигнал, отличный от выходных сигналов в других состояниях, то говорят что конечный автомат имеет полную систему выходов.

Примеры элементарных конечных автоматов:

T-триггер (триггер со счётным входом).

R-S-триггер (триггер с разделёнными входами).

D-триггер (триггер задержки).

J-K-триггер (универсальный триггер).