Лабораторная работа "Построение графов конечных автоматов" (СПО)

Практическая работа № 13

По дисциплине:  «Дискретная математика» для специальности 09.02.06 Сетевое и системное администрирование

Тема: Определение множества состояний автомата, входного и выходного алфавита автомата. Построение графа автомата

 Цель: Овладение умениями строить по таблице автоматов граф автомата, строить по графу автомата таблицу автомата, по входному слову определять перечень состояний автомата и выходное слово.

Материальное обеспечение: Программы для графического представления графов: grin_rus, Grafoanalizator1.3.3 rus.

Ход работы:

& Основные понятия и определения

Определение  абстрактного авторитета

В контактных и логических схемах значения выходном переменных определяются только комбинацией значений переменных на входах в данный момент времени. Поэтому их называют комбинационными схемами. В более общем случае выходные переменные могут зависеть от значений входных переменных не только в данный момент, но и от их предыдущих значений. Иначе говоря, значения выходных переменных определяются последовательностью значений входных переменных, в связи с чем схемы с такими свойствами называются последовательными. Если входные и выходные переменные принимают значения из конечных алфавитов, то оба типа схем объединяются под названием конечные автоматы. Конечный автомат является математической моделью дискретного управляющего устройства. Он задается множеством из шести элементов:

S={A,Z,W, δ, λ,a₁}

1)      Z={z₁,z₂…  z_f,..z _F} – множество входных сигналов или входной алфавит. Символами входного алфавита служат слова z =(z₁,z₂, …, z_n)  длины n, если автомат имеет n входов.

2)      W= {w₁,w₂… w_g.. w_G } – множество выходных сигналов или выходной алфавит. Символами выходного алфавита служат слова W= {w₁,w₂ … w_m) , длины m, если автомат имеет m выходов.

3)      A = {a₁,a₂… a_m..a_M } – множество состояний или алфавит состояний.

4)      δ - функция переходов реализующая отображение множества

  в А (a_s = δ (a_m,z_f ), a_s  A)

5)      λ - функция выходов реализующая отображение множества

  на W (w_g =λ (a_m,z_f ))

6)      а₁  A – начальное состояние автомата

Автомат называется конечным, если конечны множества A,Z,W. Автомат называется полностью определенным если D_δ=D_λ=AZ, т.е. область определения функций λ и δ совпадает со множеством все возможных пар вида (a_m,z_f ). У частичного автомата функции λ и δ определены не для всех пар (a_m,z_f )

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

В каждый момент t = 0,1,2… дискретного времени автомат находится в определенном состоянии a(t)A, при t=0 он всегда находится в начальном состоянии а(0) = а₁ . В момент t, будучи в состоянии а(t), автомат способен воспринимать на входном канале сигнал Z(t)Z и выдать на выходном канале сигнал W(t)= λ (a(t); z(t)), переходя в состояние a(t+1)=&(a(t), z(t)), a(t)A, w(t)W.

На практике наибольшая распространение получили автоматы Мили и Мура.

Закон функционирования автомата Мили задается уравнениями:

а(t+1)= δ (a(t);z(t)); w(t)=(a(t), z(t)),t=0,1,2…

Закон функционирования автомата Мура задается уравнениями

а(t+1)= δ (a(t);z(t)); w(t)=(a(t)) ,t=0,1,2…

Методы задания автоматов

Что бы задать конечный автомат S, необходимо описать все элементы множества S={A,Z,W, δ, λ,a₁}.

1.    Табличный способ задания

- Общий вход таблицы переходов автомата Мили:

	a1	…	am
z1	δ (a1;z1)	…	δ(am;z1)
…	…	…	…
zf	δ (a1;zf)	…	δ (am;zf)

На пересечении столбца a_m и строки z_f ставится состояние a_s= &(a_m; z_f) в которое автомат переходит из состояния a_m под действием сигнала z_f

-   Общий вид таблицы выходов автомата Мили

	a1	…	am
z1	λ (a1;z1)	…	λ(am;z1)
…	…	…	…
zf	λ (a1;zf)	…	λ (am;zf)

На пересечении столбца a_m строки z_f становится выходной сигнал w_g = λ (a_m; z_f),  соответствующий переходу автомата в состояние a_s

-   Т.к. в алфавите Мура выходной сигнал зависит только от состояния , то автомат Мура задается одной отмеченной таблицей переходов, в которой каждому столбцу приписан кроме состояний a_m ещё и выходной сигнал w_g  = (a_m), соответствующий этому состоянию.

	λ (a1)	…	λ (am)
	a1	…	am
z1	&(a1;z1)	…	&(am;z1)
…	…	…	…
zf	&(a1;zf)	…	&(am;zf)

Графический способ задания

Граф алфавита – это ориентированный связный граф, вершины которого соответствует состояниям, а дуги – переходом между ними.

Две вершины графа автомата a_m и a_s (исходное состояние и состояние перехода) соединяются дугой направленной от a_m к a_s, если в автомате имеется переход от a_m к a_s, т.е. если a_s= δ (a_m; z_f) при некотором входном сигнала z_fZ

Дуге (a_m; a_s) графа автомата приписывается входной сигнал w_g = λ (a_m; z_f) если он определен и ставится прочерк в противном случае.

При описании автомата Мура в виде, графа выходной сигнал w_g = λ (a_m) записывается внутри вершины a_m или рядом с ней.

Примеры:

Полностью определенный

1)    Автомат Мили S₁ c тремя состояниями, двумя входными и двумя выходными сигналами:

	a1	a2	a3			a1	a2	a3
z1	a3	a1	a1		z1	w1	w1	w2
z2	a1	a3	a2		z2	w1	w2	w1

Пусть на автомат подается входное слово ξ= z₁z₁z₂z₁z₂z₂

Входное слово:	Z1	Z1	Z2	Z1	Z2	Z2
Последовательность состояний:	a1	a3	a1	a1	a3	a2	a2
Выходное слово:	W1	W2	W1	W1	W1	W2

2)                      Автомат Мура с 5 состояниями, двумя входными и 3 выходными сигналами.

Отмеченная таблица переходов

	w1	w1	w3	w2	w3
	a1	a2	a3	a4	a5
z1	a2	a5	a5	a3	a3
z2	a4	a2	a2	a1	a1

Входное слово:	Z1	Z1	Z2	Z1	Z2	Z2
Последовательность состояний:	a1	a2	a5	a1	a2	a2	a2
Выходное слово:	W1	W1	W3	W1	W1	W1

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

Пример : По графу автомата Мура построить отмеченную таблицу переходов.

	w1	w3	w2
	a1	a2	a3
z1	a2	a2	a2
z2	a3	a2	a3
z3	a1	a1	a3

Входное слово:	Z1	Z2	Z2	Z3	Z1	Z3
Последовательность состояний:	a1	a2	a2	a2	a1	a2	a1
Выходное слово:		W3	W3	W3	W1	W3	W1

Пример : По графу автомата Мили построить таблицу переходов и таблицу выходов.

	a1	a2	a3	a4	a5
z1	a4	a4	a1	a2	a2
z2	a1	a1	a5	a3	a2

	a1	a2	a3	a4	a5
z1	w1	w1	w1	w2	w1
z2	w1	w1	w2	w1	w2

Входное слово:	Z1	Z2	Z1	Z2	Z1	Z2
Последовательность состояний:	a1	a4	a3	a1	a1	a4	a3
Выходное слово:	W1	W1	W1	W1	W1	W1

Ход работы:

Задание № 1 Даны таблицы переходов и выходов автомата Мили.

	a1	a2	a3			a1	a2	a3
z1	a3	a1	a1		z1	w1	w1	w2
z2	a1	a3	a2		z2	w1	w2	w1

- записать множество состояний автомата, входной и выходной алфавит;

Автомат Мили S₁ c тремя состояниями, двумя входными и двумя выходными сигналами.

- построить граф автомата;

1) создание вершин сети:для изменения вида и размера вершины необходимо выполнить команды: Вид → Прорисовать основным цветом →двойным щелчком по вершине вызвать подменю и изменить вес на 2 имя вершины согласно его порядковому номеру в таблице, увеличить радиус до 20 и поставить галочки в окнах: Использовать собст. атрибуты и Рисунок

2) для создания петель в графе необходимо ввести вершины с именем 0, если не одна вершина имеет петлю к имени добавить порядковый номер;

3) создание дуг сети: необходимо выполнить команды: Вид → Панель новых элементов → в открывшемся диалогов окне Параметры выбрать Тип ребра → стиль (сплошная) →ширина 2 →Имя ребра записать входной сигнал Z_i; через пробел 2-3 раза выходной сигнал W_j

3) создание сети: вид сети согласно данных задания.

- для входного слова z₁z₂z₁z₂z₁z₂ определить перечень состояний автомата и выходное слово.

Входное слово:	Z1	Z1	Z2	Z1	Z2	Z2
Последовательность состояний:	a1	a3	a1	a1	a3	a2	a2
Выходное слово:	W1	W2	W1	W1	W1	W2

Заполнить таблицу в отчёте на формате А4 самостоятельно.

Практическая работа № 13

По дисциплине:  «Дискретная математика» для специальности 09.02.06 Сетевое и системное администрирование

Тема: Определение множества состояний автомата, входного и выходного алфавита автомата. Построение графа автомата

          Цель: Овладение умениями строить по таблице автоматов граф автомата, строить по графу автомата таблицу автомата, по входному слову определять перечень состояний автомата и выходное слово.

Материальное обеспечение: Программы для графического представления графов: grin_rus, Grafoanalizator1.3.3 rus.

Вариант 20

Задание № 1 Даны таблицы переходов и выходов автомата Мили.

	a1	a2	a3	а4			a1	a2	a3	а4
z1	a2	a1	a1	a2		z1	w1	w1	w2	w2
z2	a3	а4	a2	a3		z2	w2	w2	w1	w1

- записать множество состояний автомата, входной и выходной алфавит;

- построить граф автомата;

- для входного слова z₁z₂z₁z₂z₁z₂z₁z₂z₂ определить перечень состояний автомата и выходное слово.

Задание № 2 Даны отмеченная таблицы переходов автомата Мура.

	w1	w1	w3	w2	w3
	a1	a2	a3	a4	a5
z1	a2	a3	a1	a3	a1
z2	a5	a4	a2	a2	a2
z3	a2	a5	a3	a1	a3

- записать множество состояний автомата, входной и выходной алфавит;

- построить граф автомата;

- для входного слова z₁ z₃ z₁ z₂ z₁ z₃ z₁ z₃ z₂ z₁ определить перечень состояний автомата и выходное слово.

Задание № 3 Дан граф автомата Мили.

- записать множество состояний автомата, входной и выходной алфавит;

- построить таблицу переходов и выходов автомата;

- для входного слова z₁ z₂ z₁ z₂ z₁ z₁ z₂ z₂ z₁ z₁ определить перечень состояний автомата и выходное слово.

Задание № 4 Дан граф автомата Мура.

- записать множество состояний автомата, входной и выходной алфавит;

- построить отмеченную таблицу переходов автомата;

- для входного слова z₁ z₂ z₃ z₁ z₃ z₂ z₁ z₂ z₃ z₁ определить перечень состояний автомата и выходное слово.

Задание № 5 Представить в табличной и графической формах полностью определенный автомат Мили, имеющий 3-4 состояния, 2-3 входных и 2-3 выходных сигнала. Подать на вход автомата входное слово из 5 символов, для этого слова получить последовательность состояний автомата и выходное  слово.

Задания по вариантам:

№ варианта	Задание 1	Задание 2	Задание 3	Задание 4
1, 11, 21	a1 a2 a3 а4 z1 а4 a1 a1 а3 z2 а3 a3 а4 а2 a1 a2 a3 а4 z1 w1 w2 w1 w1 z2 w2 w2 w2 w1	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a3 a5 a4 a1 a1 z2 a4 a1 a2 a2 a3 z3 a2 a3 a5 a5 a2
2, 12, 22	a1 a2 a3 а4 z1 а2 а4 a1 а3 z2 а3 a3 а4 а4 a1 a2 a3 а4 z1 w1 w2 w1 w2 z2 w2 w1 w1 w1	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a2 a3 a2 a3 a3 z2 a4 a3 a1 a1 a4 z3 a5 a4 a4 a2 a1
3, 13, 23	a1 a2 a3 а4 z1 a3 a1 a1 а3 z2 а4 a3 a1 a1 a1 a2 a3 а4 z1 w1 w2 w1 w2 z2 w2 w1 w1 w1	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a4 a3 a2 a1 a2 z2 a2 a1 a5 a3 a4 z3 a4 a4 a2 a1 a1
4, 14, 24	a1 a2 a3 а4 z1 a3 a1 a2 a1 z2 а4 а4 a1 a3 a1 a2 a3 а4 z1 w1 w2 w1 w1 z2 w2 w1 w2 w2	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a3 a1 a1 a2 a4 z2 a5 a3 a2 a5 a2 z3 a4 a4 a5 a1 a3
5, 15, 25	a1 a2 a3 а4 z1 a2 a1 a2 a2 z2 a3 а4 a1 a3 a1 a2 a3 а4 z1 w2 w2 w2 w1 z2 w1 w1 w2 w1	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a3 a5 a1 a1 a4 z2 a2 a4 a4 a2 a1 z3 a4 a3 a2 a3 a2
6, 16, 26	a1 a2 a3 а4 z1 a3 a1 a2 a2 z2 a2 a3 а4 a1 a1 a2 a3 а4 z1 w1 w2 w1 w1 z2 w2 w1 w2 w1	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a3 a4 a5 a3 a2 z2 a5 a1 a4 a2 a3 z3 a2 a3 a1 a1 a2
7, 17, 27	a1 a2 a3 а4 z1 a2 a3 a1 a2 z2 a2 а4 а4 a1 a1 a2 a3 а4 z1 w2 w1 w1 w1 z2 w2 w2 w2 w1	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a3 a5 a2 a1 a2 z2 a5 a4 a4 a1 a3 z3 a2 a1 a5 a2 a4
8, 18, 28	a1 a2 a3 а4 z1 a2 a1 а4 a2 z2 a3 a3 a2 a1 a1 a2 a3 а4 z1 w1 w2 w2 w2 z2 w2 w1 w2 w1	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a3 a5 a1 a1 a2 z2 a4 a1 a2 a1 a1 z3 a2 a4 a5 a2 a1
9, 19, 29	a1 a2 a3 а4 z1 a3 а4 a1 a2 z2 а4 a3 a2 a3 a1 a2 a3 а4 z1 w2 w2 w1 w1 z2 w1 w1 w2 w1	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a3 a4 a2 a1 a2 z2 a4 a1 a2 a4 a1 z3 a2 a5 a4 a5 a3
10, 20, 30	a1 a2 a3 а4 z1 a2 a1 a1 a2 z2 a3 а4 a2 a3 a1 a2 a3 а4 z1 w1 w1 w2 w2 z2 w2 w2 w1 w1	w1 w1 w3 w2 w3 a1 a2 a3 a4 a5 z1 a2 a3 a1 a3 a1 z2 a5 a4 a2 a2 a2 z3 a2 a5 a3 a1 a3