Табличный метод структурного синтеза конечных автоматов
Содержание
Введение
1. Синтез конечных автоматов
1.1 Основные понятия и определения
1.2 Задания конечного автомата
2. Элементарные автоматы
3. Табличный метод структурного синтеза конечных автоматов
3.1 Структурный синтез
3.2 Построение синтеза функций возбуждения элементарных автоматов
3.3 Комбинационный синтез конечных автоматов
4. Тестирование программы
Выводы
Список использованных источников
Приложения
Введение
Потребность в вычислениях возникла у людей на самых ранних
стадиях развития человеческого общества. Причем с самого начала для облегчения
счета люди использовали различные приспособления. Многие из них были весьма
интересными и остроумными по принципу действия, но все они обязательно
требовали, чтобы в процессе вычислений активно участвовал человек-оператор.
Качественно новый этап развития вычислительной техники наступил с изобретением
и созданием электронных вычислительных машин, которые работают автоматически,
без участия человека, в соответствии с заранее заданной программой.
В настоящее время электронные вычислительные машины в
основном используются для решения сложных математических и инженерных задач, в
качестве управляющих машин в промышленности и военной технике, а так же в сфере
обработки информации.
Теория автоматов - раздел дискретной математики, изучающий
абстрактные автоматы - вычислительные машины, представленные в виде
математических моделей - и задачи, которые они могут решать. Теория автоматов
наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную
информацию по шагам в дискретные моменты времени и формирует результат по шагам
заданного алгоритма.
Для формального описания узлов ЭВМ при их анализе и синтезе
используется аппарат алгебры логики. Основные положения алгебры логики
разработал в XIX в. английский математик Джордж Буль. Алгебру логики называют
также булевой алгеброй.
Логические элементы - устройства, предназначенные для
обработки информации в цифровой форме (последовательности сигналов высокого -
"1" и низкого - "0" уровней в двоичной логике, последовательность
"0", "1" и "2" в троичной логике,
последовательности "0", "1", "2", "3",
"4", "5", "6", "7", "8"и
"9" в десятичной логике).
Триггер - это устройство последовательного типа с двумя
устойчивыми состояниями равновесия, предназначенное для записи и хранения
информации. Под действием входных сигналов триггер может переключаться из
одного устойчивого состояния в другое. При этом напряжение на его выходе
скачкообразно изменяется.
Как правило, триггер имеет два выхода: прямой и инверсный.
Число входов зависит от структуры и функций, выполняемых триггером. По способу
записи информации триггеры делят на асинхронные и синхронизируемые
(тактируемые). В асинхронных триггерах информация может записываться непрерывно
и определяется информационными сигналами, действующими на входах в данный
момент времени. Если информация заносится в триггер только в момент действия
так называемого синхронизирующего сигнала, то такой триггер называют
синхронизируемым или тактируемым. Помимо информационных входов тактируемые
триггеры имеют тактовый вход синхронизации. В цифровой технике приняты
следующие обозначения входов триггеров:- раздельный вход установки в единичное
состояние (напряжение высокого уровня на прямом выходе Q);- раздельный вход
установки в нулевое состояние (напряжение низкого уровня на прямом выходе Q);-
информационный вход (на него подается информация, предназначенная для занесения
в триггер);- вход синхронизации;
Т - счетный вход.
Наибольшее распространение в цифровых устройствах получили
RS-триггер с двумя установочными входами, тактируемый D-триггер и счетный
Т-триггер.
Регистр - последовательное логическое устройство,
используемое для хранения n-разрядных двоичных слов (чисел) и выполнения
преобразований над ними.
Регистр представляет собой упорядоченную последовательность
триггеров, число которых соответствует числу разрядов в слове. С каждым
регистром обычно связано комбинационное цифровое устройство, с помощью которого
обеспечивается выполнение некоторых операций над словами.
Фактически любое цифровое устройство можно представить в виде
совокупности регистров, соединённых друг с другом при помощи комбинационных
цифровых устройств.
Основой построения регистров являются D-триггеры,
RS-триггеры.
конечный автомат комбинационный синтез
1. Синтез
конечных автоматов
1.1 Основные
понятия и определения
Автоматом называется дискретный преобразователь информации,
способный принимать различные состояния, переходить под воздействием входных
сигналов из одного состояния в другое и выдавать выходные сигналы. Если
множество состояний автомата, а так же множества входных и выходных сигналов
конечны, то автомат называется конечным автоматом.
Понятие состояния введено в связи с тем, что часто возникает
необходимость в описании поведения систем, выходные сигналы которых зависят не
только от состояния входов в данный момент времени, но и от некоторых
предысторий, т.е. от сигналов, которые поступали на входы системы ранее.
Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя
устранить время как явную переменную и выразить выходные сигналы как функцию
состояний и входов в данный момент времени.
Информацию, поступающую на вход автомата, а так же выходную
информацию принято кодировать конечной совокупностью символов. Эту совокупность
называют алфавитом, отдельные символы, образующие алфавит - буквами, а любые
упорядоченные последовательности букв данного алфавита - словами в этом
алфавите.
Например. В алфавите X = (x1, x2), состоящем из двух букв,
словами будут: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1, и т.д.
Наряду со словами, состоящими не менее чем из одной буквы,
введем слово, не содержащее ни одной буквы, которую будем обозначать символом е
и называть пустым словом или пустой буквой.
Математической моделью реального конечного автомата является
абстрактный автомат, который имеет один входной канал и один выходной канал
. →A (a0,a1,an) →y (y1,y2,…,yk)
Рисунок 1.1 - абстрактная модель автомата
Автомат функционирует в дискретные моменты времени, интервал
между которыми Т называется тактом. При этом в каждый дискретный момент времени
на вход автомата поступает одна буква входного алфавита, автомат переходит из
одного состояния в другое и выдается одна буква выходного алфавита. В
зависимости от того, как задается длительность такта Т, различают автоматы
синхронного действия (T = const) и асинхронного действия (T № const). Мы будем
рассматривать, в основном, синхронные автоматы, функционирующие в дискретные
моменты времени, которые можно обозначить целыми не отрицательными натуральными
числами, t=0,1,2,3,…., имеющими смысл номера такта.
1.2 Задания
конечного автомата
Для задания конечного автомата S необходимо задавать
совокупность из пяти объектов: S (A, X, Y, d, d), где= {a0,a1,a2,.,an} -
множество внутренних состояний автомата,= {x1, x2,…, xm} - множество входных
сигналов (входной алфавит), Xi буква входного алфавита, Y = {y1, y2,…, yk} -
множество выходных сигналов (выходной алфавит), d - функция переходов,
определяющая состояние автомата a (t+1), в котором автомат будет находиться в
момент времени (t+1), в зависимости от состояния автомата a (t) и входного
сигнала x (t) в момент времени t, т.е. a (t+1) = d [a (t),x (t)], l - функция
выходов, определяющая значение выходного сигнала y (t) в зависимости от
состояния автомата a (t) и входного сигнала x (t) в момент времени t, т.е. y
(t) = l [a (t), x (t)]. Автомат работает следующим образом: в каждый момент
времени t он находится в определенном состоянии a (t) из множества А возможных
состояний, причем в начальный момент времени t = 0, он всегда находится в
состоянии a (t = 0) = a0. В момент времени t автомат воспринимает входной
сигнал x (t), выдает выходной сигнал y (t) = l [a (t), x (t)] и переходит в
следующее состояние a (t+1) = d [a (t), x (t)]. Другими словами, абстрактный
автомат каждой паре символов a (t) и x (t) ставит в однозначное соответствие
пару символов a (t+1) и y (t). Такие автоматы называют детерминированными.
Преобразование информации в детерминированных автоматах подчиняется следующим
условиям:
. Любое входное слово длинною l букв, преобразуется в
выходное слово той же длины.
. Если каждый раз перед подачей входных сигналов автомат
находится в одном и том же состоянии, то при совпадении в двух входных словах
первых l1 букв, в выходных словах первые l1 букв тоже совпадут.
Кроме детерминированных автоматов существуют вероятностные
или стохастические автоматы, в которых переход из одного состояния в другое под
воздействием случайных или детерминированных входных сигналов происходит
случайно. Работа таких автоматов описывается уже матрицей переходов d,
элементами которой являются вероятности переходов из одного состояния в другое.
Мы будем изучать детерминированные автоматы.
Применяемые на практике автоматы принято разделять на два
класса: - это автоматы Мили и автоматы Мура, названные так по имени
американских ученых, которые впервые начали их изучать.
Закон функционирования автоматов Мили описывается следующей
системой уравнений:
a (t + 1) = d [a (t),x (t)](t) = l [a (t),x (t)]
t = 0,1,2,3…
Работа автоматов Мура задается следующими уравнениями:
a (t + 1) = d [a (t),x (t)](t) = l [a (t)]
Отличительной особенностью автоматов Мили является то, что их
выходные сигналы зависят как от состояния автомата, так и от значения входного
сигнала. В автоматах Мура выходные сигналы y (t) в каждый дискретный момент
времени t однозначно определяются состоянием автомата в тот же момент времени и
не зависят от значения входного сигнала.
2.
Элементарные автоматы
В настоящее время в вычислительной технике, как правило,
используются элементарные автоматы, имеющие следующие особенности:
. Элементарные автоматы являются автоматами Мура с двумя
внутренними состояниями.
. Автомат выдает два различных выходных сигнала,
соответствующих двум его внутренним состояниям. В дальнейшем состояния автомата
и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и
1.
. Элементарные автоматы могут иметь в общем случае несколько
физических входов, на каждый из которых могут подаваться сигналы,
закодированные цифрами 0 и 1.
Рисунок 2.1 − триггер
В качестве элементарных автоматов в вычислительной технике
используются, в основном, триггеры различных типов. Рассмотрим некоторые из
них:
1. Т-триггер <#"725078.files/image002.gif">
Рисунок 3.1 - Начальное окно приложения
При вводе данных надо нажать на кнопку "Построить
таблицу КА". При нажатии на кнопку появится поля для ввода данных (рис
3.2).
Рисунок 3.2 - Построить таблицу КА
При нажатии кнопки "Минимизировать КА"
минимизированный автомат будет выведен в поле для вывода (рис. 3.3).
Рисунок 3.3 - Вывод
Выводы
В курсовой работе был рассмотрен основные понятия теории
Конечных автоматов. Был запрограммирован алгоритм минимизации КА,
протестирована программа, обработан список литературы. По полученным
результатам, обработки материала, можно сделать вывод, что минимизировать
конечные автоматы возможно.
Сделав такой вывод, мы выполнили цель данной работы.
Список
использованных источников
1.
Абрамов, Л.А. Математическое программирование [Текст] / Л.А. Абрамов, В.Ф.
Капустин ‒ Л.: Изд-во ЛГУ, 1981. ‒ 328 с.
.
Белоусова, Г.С. Линейное программирование. Учебное пособие [Текст] / Г.С.
Белоусова ‒ Красноярск: Наука, 1975. ‒ 107 с.
.
Кузнецов, Ю.Н. Математическое программирование: Учебное пособие [Текст] / Ю.Н.
Кузнецов - 2-е изд., перераб. и доп. - М.: Высшая школа, 1980. ‒ 300 с.
.
Габасов, Р.И. Методы линейного программирования [Текст] / Р.И. Габасов, Ф.М.
Кириллова - Минск: Наука. 1977. - 174 с.
6. Голованова, В.Н. Экономическая оценка инженерных решений
[Текст] / В.Н. Голованова. - ХАИ, 1999. - 135 с.
Приложения
Приложение
А
Листинг прогаммы
#pragma once
struct C
{*Nomber;*Znach;
};Курсова {namespace System;namespace System::
ComponentModel;namespace System:: Collections;namespace System:: Windows::
Forms;namespace System:: Data;namespace System:: Drawing;ref class Form1:
public System:: Windows:: Forms:: Form
{:(void)
{();
}:
~Form1 ()
{(components)
{components;
}
}: System:: Windows:: Forms:: TextBox^
textBox1;:: System:: Windows:: Forms:: TextBox^ textBox2;: System:: Windows::
Forms:: LinkLabel^ linkLabel1;: System:: Windows:: Forms:: LinkLabel^
linkLabel2;: System:: Windows:: Forms:: Button^ button1;: System:: Windows::
Forms:: Label^ label1;: System:: Windows:: Forms:: Button^ button2;: System::
Windows:: Forms:: TextBox^ textBox3;::: ComponentModel:: Container ^components;
#pragma region Windows Form Designer generated
codeInitializeComponent (void)
{>textBox1 = (gcnew System:: Windows:: Forms::
TextBox ());>textBox2 = (gcnew System:: Windows:: Forms:: TextBox
());>linkLabel1 = (gcnew System:: Windows:: Forms:: LinkLabel
());>linkLabel2 = (gcnew System:: Windows:: Forms:: LinkLabel ());>button1
= (gcnew System:: Windows:: Forms:: Button ());>label1 = (gcnew System::
Windows:: Forms:: Label ());>button2 = (gcnew System:: Windows:: Forms::
Button ());>textBox3 = (gcnew System:: Windows:: Forms:: TextBox
());>SuspendLayout ();
//
// textBox1
// >textBox1->Location = System:: Drawing::
Point (-3, - 1);>textBox1->Name =
L"textBox1";>textBox1->Size = System:: Drawing:: Size (78,
20);>textBox1->TabIndex = 0;
//
// textBox2
// >textBox2->Location = System:: Drawing::
Point (-3, 24);>textBox2->Name =
L"textBox2";>textBox2->Size = System:: Drawing:: Size (78,
20);>textBox2->TabIndex = 1;
//
// linkLabel1
// >linkLabel1->AutoSize =
true;>linkLabel1->Location = System:: Drawing:: Point
(86,2);>linkLabel1->Name =
L"linkLabel1";>linkLabel1->Size = System:: Drawing:: Size (160,
13);>linkLabel1->TabIndex = 2;>linkLabel1->TabStop = true;
this->linkLabel1->Text = L"Ведите количество
состояний";
//
// linkLabel2
// >linkLabel2->AutoSize =
true;>linkLabel2->Location = System:: Drawing:: Point (86, 27);>linkLabel2->Name
= L"linkLabel2";>linkLabel2->Size = System:: Drawing:: Size
(163, 13);>linkLabel2->TabIndex = 3;>linkLabel2->TabStop = true;
this->linkLabel2->Text = L"Введите количество эл.
вх. ал. ";
//
// button1
// >button1->Location = System:: Drawing::
Point (350,8);>button1->Name = L"button1";>button1->Size
= System:: Drawing:: Size (143, 36);>button1->TabIndex =
4;>button1->Text = L"Построить таблицу КА";>button1->UseVisualStyleBackColor
= true;>button1->Click += gcnew System:: EventHandler (this, &Form1::
button1_Click);
//
// label1
// >label1->AutoSize =
true;>label1->Location = System:: Drawing:: Point (3,
57);>label1->Name = L"label1";>label1->Size = System::
Drawing:: Size (26, 13);>label1->TabIndex = 5;>label1->Text =
L"G (x)";
//
// button2
// >button2->Location = System:: Drawing::
Point (350, 52);>button2->Name =
L"button2";>button2->Size = System:: Drawing:: Size (142,
33);>button2->TabIndex = 7;>button2->Text = L"Минимизировать КА";>button2->UseVisualStyleBackColor
= true;>button2->Click += gcnew System:: EventHandler (this, &Form1::
button2_Click);
//
// textBox3
// >textBox3->Location = System:: Drawing::
Point (336, 165);>textBox3->Multiline = true;>textBox3->Name =
L"textBox3";>textBox3->Size = System:: Drawing:: Size (155,
20);>textBox3->TabIndex = 8;
//
// Form1
// >AutoScaleDimensions = System:: Drawing::
SizeF (6, 13);>AutoScaleMode = System:: Windows:: Forms:: AutoScaleMode::
Font;>ClientSize = System:: Drawing:: Size (491, 346);>Controls->Add
(this->textBox3);>Controls->Add
(this->button2);>Controls->Add (this->label1);>Controls->Add
(this->button1);>Controls->Add
(this->linkLabel2);>Controls->Add
(this->linkLabel1);>Controls->Add (this->textBox2);>Controls->Add
(this->textBox1);>Name = L"Form1";>Text = L"Form1";>Load
+= gcnew System:: EventHandler (this, &Form1:: Form1_Load);>ResumeLayout
(false);>PerformLayout ();
}
#pragma endregion<TextBox^>^
msv;<TextBox^>^ msv1;**massA;**massA1;**massB;S;F;Per;: System:: Void
Form1_Load (System:: Object^ sender, System:: EventArgs^ e) {>Text = "Курсова ";
}: System:: Void button1_Click (System:: Object^
sender, System:: EventArgs^ e) {X,Y;= 0;Число_ли1 = Single:: TryParse (textBox1->Text,::
Globalization:: NumberStyles:: Number,:: Globalization:: NumberFormatInfo::
CurrentInfo, X);Число_ли2 = Single:: TryParse (textBox2->Text,:: Globalization::
NumberStyles:: Number,:: Globalization:: NumberFormatInfo:: CurrentInfo, Y);
if ( (Число_ли1 == false) || (Число_ли2 == false))
{->Text = "Следует вводить числа";
linkLabel1->ForeColor = Color:: Red;;
}
// // // // // // // // // // // // // // // //
// // // // // // // // // // x,y,tb,tr;= (int) (X);= (int) (Y);= x; F = y;=new
int* [x];=new int* [x];=new int* [x];(int i=0; i<x; i++)
{[i] =new int [y];[i] =new int [y];[i] =new int
[y];
}=0;=0;
// // // // // // // // // // // // // // // //
// // // // // // // /= gcnew array<TextBox^> (x*y);(int i = 0; i <
msv->Length; i++)
{ if (i%x==0) {tb=tb+20; tr = 0; };[i] = gcnew
TextBox ();[i] - >Location = System:: Drawing:: Point (tb,70+20*tr);[i] -
>Name = i. ToString ();[i] - >Size = System:: Drawing:: Size (20, 20);[i]
- >TabIndex = 0;>Add (msv [i]);++; }
// // // // // // // // // // // // // // // //
// // // // // // // // // // // // // /^ label2;= gcnew System:: Windows::
Forms:: Label ();->Name = "label2";->Visible =
true;->AutoSize = true;->Location = System:: Drawing:: Point (tb+50,
57);->Text = L"F (x)";->TabIndex = 0;>Add (label2);
// // // // // // // // // // // // // // // //
// // // // // // // // // // // // // /= tb +40;= gcnew array<TextBox^>
(x*y);(int i = 0; i < msv->Length; i++)
{ if (i%x==0) {tb=tb+20; tr = 0; };[i] = gcnew
TextBox ();[i] - >Location = System:: Drawing:: Point (tb,70+20*tr);[i] -
>Name = i. ToString ();[i] - >Size = System:: Drawing:: Size (20, 20);[i]
- >TabIndex = 0;>Add (msv1 [i]);++; }
}: System:: Void button2_Click (System:: Object^
sender, System:: EventArgs^ e) {->Size = Drawing:: Size (400,
200);z=0;*Z,*Z1;= new Single [S*F];= new Single [S*F];(int i = 0; i < F;
i++) {(int j=0; j<S; j++) {Число_ли2 =Single:: TryParse (msv [z] - >Text,:: Globalization::
NumberStyles:: Number,:: Globalization:: NumberFormatInfo:: CurrentInfo, Z
[z]);[j] [i] = (int) (Z [z]);++;
}}=0;(int i = 0; i < F; i++) {(int j=0;
j<S; j++) {Число_ли2 = Single::
TryParse (msv1 [z] - >Text,:: Globalization:: NumberStyles:: Number,::
Globalization:: NumberFormatInfo:: CurrentInfo, Z1 [z]);[j] [i] = (int) (Z1
[z]);++;
}}(int i = 0; i < S; i++) {(int j=0; j<F;
j++) {[i] [j] = massA [i] [j]; }}
// // // // // // // // // // // // // // // //
// // // // // // // // // // // // /*C1;= new C [S];(int i=0; i<S; i++)[i].
Znach=new int [S];
// // // // // // // // // // // // // // // //
// // // // // // // // // /Per1=-1;(Per! =Per1)
{int r=0;(Per1==-1) {Per1=Per;(int i=0; i<S;
i++) {(int z=i; z<S; z++) {(massB [i] [0] ==massB [z] [0])
{for (int d=0; d<F; d++) {(massB [i] [d]!
=massB [z] [d]) {goto a1; }}}{goto a1; }(int b=0; b<S; b++) {(int x=0;
x<S; x++) {(C1 [b]. Znach [x] ==z) {goto a1; }}}[Per]. Znach [r] =z;++;:;
}(int z=0; z<S; z++) {(C1 [Per]. Znach [z]
>-1) { Per++; break; }}}(int i=0; i<S; i++)
{massA [i] [j] =o; break; }}}}
} // // // // // // // // // // // // // // // //
// // // // // // // // // { Per1=Per;=0;(int i=0; i<S; i++)
{for (int j=0; j<S; j++)
{C1 [i]. Znach [j] = (-1); }}
// // // // // // // // // // // // // // // //
// // // // // // // // // =0;(int i=0; i<S; i++) {(int z=i; z<S; z++)
{(massA [i] [0] ==massA [z] [0])
{for (int d=0; d<F; d++) {(massA [i] [d]!
=massA [z] [d]) {goto a2; }}}{goto a2; }(int b=0; b<S; b++) {(int x=0;
x<S; x++) {(C1 [b]. Znach [x] ==z) {goto a2; }}}[Per]. Znach [r] =z;++;:;
}(int z=0; z<S; z++) {(C1 [Per]. Znach [z]
>-1) { Per++; break; }}}(int i=0; i<S; i++)
{for (int j=0; j<F; j++) {(int o=0; o<Per;
o++) {(int x=0; x<S; x++)(massA1 [i] [j] ==C1 [o]. Znach [x])
{massA [i] [j] =o; break; }}}}
}} // // // // // // // // // // // // // // //
// // // // // // // // // // k=0;(int I=0; I<Per; I++)
{for (int j=0; j<S; j++) {(C1 [I]. Znach [j]
>-1)
{for (int y=0; y<F; y++)
{massA [k] [y] =massA [C1 [I]. Znach [j]] [y];
}++;=S-1; }
}}(int i=0; i<S; i++) {(int j=0; j<S; j++)
{(C1 [i]. Znach [j] >-1)
{(int z=0; z<Per; z++) {(int x=0; x<F; x++)
{(C1 [i]. Znach [j] ==massA [z] [x])
{massA [z] [x] =C1 [i]. Znach [j]; }
}}}}}->AppendText (String:: Format
("Otvet: \r\n G (x) \r\n"));(int i=0; i<Per; i++)
{for (int j=0; j<F; j++) {->AppendText
(String:: Format ("{0} \t",massA [i] [j])); }->AppendText
(String:: Format ("\r\n")); }->AppendText (String:: Format
("F (x) \r\n"));(int i=0; i<Per; i++)
{for (int j=0; j<S; j++)(C1 [i]. Znach [j]
>-1)
{(int c=0; c<F; c++)->AppendText (String::
Format ("{0} \t",massB [i] [c]));->AppendText (String:: Format
("\r\n"));
break;
}
}
// // // // // // // // // // // // // // // // // // // //
// // // // // // // // }
};
}