ПРИМЕРЫ КОНЕЧНЫХ АВТОМАТОВ

Пример 1.

. Детерминированный автомат Мили задан таблицей 11.

Таблица 11.

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова для различных начальных состояний,если на входе автомата задано слово  = (x₁x₂x₃x₄x₄x₃x₂x₁).

Для формирования таблицы соединения состояний автомата находим по таблице 11 число строк и столбцов. Это число равно 4. Имена строк и столбцов заданы именами элементов множества qQ. В позициях таблицы будут значения (x/y), соответствующие переходу из состояния q[] в состояние q[1]. Следует обратить внимание, что переход из состояния q₃ в q₂ обусловлен двумя входными символами (x₁ и x₄), а для каждой пары (q₃;x₁) и (q₃;x₄) автомат генерирует в выходном канале особый символ (y₁ и y₃). Поэтому на дуге (q₃;q₂) следует указать (x₁/y₁x₄/y₃). Переход из состояния q₄ в q₁ обусловлен также двумя входными символами (x₂ и x₄), но автомат генерирует только один символ на выходе y₁. Поэтому на дуге (q₄;q₁) следует указать (x₂x₄)/y₁. Остальные переходы автомата обусловлены появлением только одного входного символа. Таблица 12 представляет таблицу соединений состояний автомата Мили, а рис. 8 – его граф.

Таблица 1.12.

Рис.8 Граф детерминированного автомата Мили.

Для поиска слов  при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова :

пусть q₁=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₁[1] q₂[2] q₄[3] q₂[4] q₂[5] q₂[6] q₁[7] q₃[8] q₂[9]

b[t]: y₁[1] y₁[2] y₂[3] y₂[4] y₂[5] y₂[6] y₁[7] y₁[8],

то есть b=(y₁y₁y₂y₂y₂y₂y₁y₁);

пусть q₂=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₂[1] q₃[2] q₃[3] q₁[4] q₁[5] q₁[6] q₄[7] q₁[8] q₂[9]

b[t]: y₃[1] y₂[2] y₁[3] y₃[4] y₃[5] y₁[6] y₁[7] y₁[8],

то есть b=(y₃y₂y₁y₃y₃y₁y₁y₁);

пусть q₃=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₃[1] q₂[2] q₄[3] q₂[4] q₂[5] q₂[6] q₁[7] q₃[8] q₂[9]

b[t]: y₁[1] y₁[2] y₂[3] y₂[4] y₂[5] y₂[6] y₁[7] y₁[8],

то есть b=(y₁y₁y₂y₂y₂y₂y₁y₁);

пусть q₄=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₄[1] q₄[2] q₁[3] q₄[4] q₁[5] q₁[6] q₄[7] q₁[8] q₂[9]

b[t]: y₂[1] y₁[2] y₁[3] y₁[4] y₃[5] y₁[6] y₁[7] y₁[8],

то есть b=(y₂y₁y₁y₁y₃y₁y₁y₁).

Анализ показывает, что при различных начальных состояниях реакция автомата на одинаковые слова различна. Это подтверждает необходимость указания начального состояния q_i=q₀. Только в этом случае каждому слову на входе автомата найдется единственный образ на выходе.

Пример 1.2.

Детерминированный автомат Мура задан таблицей поведения (см.таблицу 13).

Таблица 13.

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова для различных начальных состояний,если на входе автомата задано слово  = (x₁x₂x₃x₄x₄x₃x₂x₁).

Для формирования таблицы соединения состояний автомата находим по таблице 13 число строк и столбцов. Это число равно 4. Имена строк и столбцов заданы именами элементов множества qQ. Элементами таблицы соединения состояний автомата будут значения x, соответствующие переходу из состояния q[] в состояние q[1]. Переход из состояния q₃ в q₂ обусловлен двумя входными символами (x₁ и x₄). Поэтому на дуге (q₃;q₂) cледует указать (x₁x₄). Переход из состояния q₄ в q₁ обусловлен также двумя входными символами (x₂ и x₄). Поэтому на дуге (q₄;q₁) cледует указать (x₂x₄). Таблица 14 представляет таблицу соединений состояний автомата Мура, а рис.9 - его граф.

Tаблица 14

Рис.9 Граф детерминированного автомата Мура.

Для поиска слов  при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова :

пусть q₁=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₁[1] q₂[2] q₄[3] q₂[4] q₂[5] q₂[6] q₁[7] q₃[8] q₂[9]

b[t]: y₁[1] y₃[2] y₁[3] y₃[4] y₃[5] y₃[6] y₁[7] y₂[8],

то есть b=(y₁y₃y₁y₃y₃y₃y₁y₂);

пусть q₂=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₂[1] q₃[2] q₃[3] q₁[4] q₁[5] q₁[6] q₄[7] q₁[8] q₂[9]

b[t]: y₃[1] y₂[2] y₂[3] y₁[4] y₁[5] y₁[6] y₁[7] y₁[8],

то есть b=(y₃y₂y₂y₁y₁y₁y₁y₁);

пусть q₃=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₃[1] q₂[2] q₄[3] q₂[4] q₂[5] q₂[6] q₁[7] q₃[8] q₂[9]

b[t]: y₂[1] y₃[2] y₁[3] y₃[4] y₃[5] y₃[6] y₁[7] y₂[8],

то есть b=(y₂y₃y₁y₃y₃y₃y₁y₂);

пусть q₄=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₄[1] q₄[2] q₁[3] q₄[4] q₁[5] q₁[6] q₄[7] q₁[8] q₂[9]

b[t]: y₁[1] y₁[2] y₁[3] y₁[4] y₁[5] y₁[6] y₁[7] y₁[8]

то есть b=(y₁y₁y₁y₁y₁y₁y₁y₁).

Этот пример также подтверждает необходимость указания начального состояния q=q₀.

Пример 1.3.

Недетерминированный автомат Мили задан таблицей поведения (см. таблицу 15).

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова для различных  и различных начальных состояний.

Элементами таблицы соединения состояний автомата будут значения (x/y), соответствующие переходу из состояния q[] в состояние q[1]. Следует обратить внимание, что не определены переходы из состояния q2 для входного символа x1, из состояния q3 для входного символа x2 и из состояния q4 для входного символа x4.

Не определены также значения символов на выходе для состояния q1 и входного символа x2, для состояния q2 и входного символа x4 и для состояния q3 и входного символа x2. Таблица 16 представляет таблицу соединений состояний недетерминированного автомата Мили, а рис.10 - его граф.

Таблица 15.

Таблица 16.

Для поиска слов , генерируемых недетерминированным автоматом Мура также необходимо проследить последовательность изменения состояний автомата для каждого очередного символа слова :

пусть q₁=q₀ и a= (x₁x₂x₃x₃x₃x₂x₄x₄), тогда

a[t]: x₁[1] x₂[2] x₃[3] x₃[4] x₃[5] x₂[6] x₄[7] x₄[8]

q[t+1]: q₁[1] q₂[2] q₄[3] q₂[4] q₁[5] q₄[6] q₁[7] q₁[8] q₁[9]

b[t]: y₁[1] y₁[2] y₂[3] y₂[4] y₁[5] y₁[6] y₃[7] y₃[8],

то есть b=(y₁y₁y₂y₂y₁y₁y₃y₃);

Рис.10 Граф недетерминированного автомата Мили.

пусть q₁=q₀ и a= (x₂x₂x₃x₄x₄x₃x₂x₁), тогда

a[t]:........... x₂[1] x₂[2] x₃[3] …

q[t+1]:....... q₁[1] q₃[2] _* …

b[t]:.......... _*[1] _*[2] …,

то есть b= (_{* *} … и автомат "зависает" на третьем символе слова a;

пусть q₁=q₀ и a= (x₂x₂x₃x₄x₄x₃x₂x₁), тогда

a[t]: x₁[1] x₄[2] x₃[3] x₂[4] x₃[5] x₂[6] x₄[7] x₄[8]

q[t+1]: q₁[1] q₂[2] q₂[3] q₁[4] q₃[5] q₁[6] q₃[7] q₂[8] q₂[9]

b[t]: y₁[1] _*[2] y2[3] _* [4] y1[5] _* [6] y₃[7] _* [8],

то есть b=(y_1*y_2*y_*y_*) содержит четыре символа "_*";

пусть q₂=q₀ и a= (x₁x₄x₃x₂x₃x₂x₄x₄), тогда

a[t]: x₁[1] x₄[2] …

q[t+1]: q₂[1] _*.[2] …

b[t]: y₃[1] …

то есть b= (y₃ … и автомат "зависает" на втором символе слова a.

Анализ показывает, что недетерминированный автомат Мили может

1) генерировать на выходе последовательности символов, равные последовательностям символов на входе, но содержащие неопределенные символы "_*", что разрушает образ слова ;

2) "зависать" в состоянии, для которого не определен переход в очередное состояние.

Пример 1.4.

Недетерминированный автомат Мура задан таблицей поведения (см. таблицу 17).

Таблица 17.

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова для различных  и различных начальных состояний.

Элементами таблицы соединения состояний автомата будут значения x, соответствующие переходу из состояния q[] в состояние q[1]. Следует обратить внимание, что не определены переходы из состояния q₂ для входного символа x₁, из состояния q₃ для входного символа x₂ и из состояния q₄ для входного символа x₄. Не определено также значение символа на выходе для состояния q₂. Таблица 18 представляет таблицу соединений состояний недетерминированного автомата Мура, а рис. 11 - его граф.

Таблица 18.

Рис.11. Граф недетерминированного автомата Мура.

Для поиска слов  при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова :

пусть q₁=q₀ и a= (x₂x₃x₂x₃x₃x₁x₂x₄), тогда

a[t]: x₂[1] x₃[2] x₂[3] x₃[4] x₃[5] x₁[6] x₂[7] x₄[8]

q[t+1]: q₁[1] q₃[2] q₁[3] q₃[4] q₁[5] q₄[6] q₄[7] q₁[8] q₁[9]

b[t]: y₁[1] y₂[2] y₁[3] y₂[4] y₁[5] y₁[6] y₁[7] y₁[8],

то есть b= (y₁y₂y₁y₂y₁y₁y₁y₁);

пусть q₂=q₀ и a= (x₂x₃x₁x₄x₄x₃x₂x₁), тогда

a[t]: x₂[1] x3[2] x₁[3] x₄[4] …

q[t+1]: q₂[1] q₄[2] q₂[3] _* [4] …

b[t]: _* [1] y₁[2] _* [3] …,

то есть b= (_*y_1* … и автомат "зависает" на четвертом символе слова a;

пусть q₁=q₀ и a= (x₁x₂x₃x₃x₁x₃x₁x₃), тогда

a[t]: x₁[1] x₂[2] x₃[3] x₃[4] x₁[5] x₃[6] x₁[7] x₃[8]

q[t+1]: q₁[1] q₂[2] q₄[3] q₂[4] q₁[5] q₂[6] q₁[7] q₂[8] q₁[9]

b[t]: y₁[1] _*[2] y₁[3] _* [4] y₁[5] _* [6] y₁[7] _* [8],

то есть b=(y_1*y_1*y_1*y_1*) содержит четыре символа про"_*";

пусть q₂=q₀ и a= (x₁x₄x₃x₂x₃x₂x₄x₄), тогда

a[t]: x₁[1] x₄[2] …

q[t+1]: q₂[1] _* [2] …

b[t]: _* …,

то есть b= (_* … и автомат "зависает" на втором символе слова a.

Анализ показывает, что для недетерминированного автомата Мура характерны такие же недостатки, как для недетерминированного автомата Мили

Заключение

Автоматное программирование, иначе называемое «программирование от состояний» или «программирование с явным выделением состояний» — это метод разработки программного обеспечения, основанный на расширенной модели конечных автоматов и ориентированный на создание широкого класса приложений.

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

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

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

Дата добавления: 2015-07-26; просмотров: 362; Нарушение авторских прав

Мы поможем в написании ваших работ!