Табличный метод структурного синтеза конечных автоматов
Понятие автомата как дискретного преобразователя информации, особенности его состояний. Синтез конечных автоматов, их задания и структурных анализ. Построение синтеза функций возбуждения элементарных автоматов. Комбинационный синтез конечных автоматов.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 01.06.2014 |
| Размер файла | 336,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
- Введение
- 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" в десятичной логике).
Триггер - это устройство последовательного типа с двумя устойчивыми состояниями равновесия, предназначенное для записи и хранения информации. Под действием входных сигналов триггер может переключаться из одного устойчивого состояния в другое. При этом напряжение на его выходе скачкообразно изменяется.
Как правило, триггер имеет два выхода: прямой и инверсный. Число входов зависит от структуры и функций, выполняемых триггером. По способу записи информации триггеры делят на асинхронные и синхронизируемые (тактируемые). В асинхронных триггерах информация может записываться непрерывно и определяется информационными сигналами, действующими на входах в данный момент времени. Если информация заносится в триггер только в момент действия так называемого синхронизирующего сигнала, то такой триггер называют синхронизируемым или тактируемым. Помимо информационных входов тактируемые триггеры имеют тактовый вход синхронизации. В цифровой технике приняты следующие обозначения входов триггеров:
S - раздельный вход установки в единичное состояние (напряжение высокого уровня на прямом выходе Q);
R - раздельный вход установки в нулевое состояние (напряжение низкого уровня на прямом выходе Q);
D - информационный вход (на него подается информация, предназначенная для занесения в триггер);
C - вход синхронизации;
Т - счетный вход.
Наибольшее распространение в цифровых устройствах получили RS-триггер с двумя установочными входами, тактируемый D-триггер и счетный Т-триггер.
Регистр - последовательное логическое устройство, используемое для хранения n-разрядных двоичных слов (чисел) и выполнения преобразований над ними.
Регистр представляет собой упорядоченную последовательность триггеров, число которых соответствует числу разрядов в слове. С каждым регистром обычно связано комбинационное цифровое устройство, с помощью которого обеспечивается выполнение некоторых операций над словами.
Фактически любое цифровое устройство можно представить в виде совокупности регистров, соединённых друг с другом при помощи комбинационных цифровых устройств.
Основой построения регистров являются D-триггеры, RS-триггеры.
конечный автомат комбинационный синтез
1. Синтез конечных автоматов
1.1 Основные понятия и определения
Автоматом называется дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы. Если множество состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом.
Понятие состояния введено в связи с тем, что часто возникает необходимость в описании поведения систем, выходные сигналы которых зависят не только от состояния входов в данный момент времени, но и от некоторых предысторий, т.е. от сигналов, которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входов в данный момент времени.
Информацию, поступающую на вход автомата, а так же выходную информацию принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит - буквами, а любые упорядоченные последовательности букв данного алфавита - словами в этом алфавите.
Например. В алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1, и т.д.
Наряду со словами, состоящими не менее чем из одной буквы, введем слово, не содержащее ни одной буквы, которую будем обозначать символом е и называть пустым словом или пустой буквой.
Математической моделью реального конечного автомата является абстрактный автомат, который имеет один входной канал и один выходной канал
. >A (a0,a1,an) >
X y (y1,y2,…,yk)
Рисунок 1.1 - абстрактная модель автомата
Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (T № const). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми не отрицательными натуральными числами, t=0,1,2,3,…., имеющими смысл номера такта.
1.2 Задания конечного автомата
Для задания конечного автомата S необходимо задавать совокупность из пяти объектов: S (A, X, Y, d, d), где
A = {a0,a1,a2,.,an} - множество внутренних состояний автомата,
X = {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). Такие автоматы называют детерминированными. Преобразование информации в детерминированных автоматах подчиняется следующим условиям:
1. Любое входное слово длинною l букв, преобразуется в выходное слово той же длины.
2. Если каждый раз перед подачей входных сигналов автомат находится в одном и том же состоянии, то при совпадении в двух входных словах первых l1 букв, в выходных словах первые l1 букв тоже совпадут.
Кроме детерминированных автоматов существуют вероятностные или стохастические автоматы, в которых переход из одного состояния в другое под воздействием случайных или детерминированных входных сигналов происходит случайно. Работа таких автоматов описывается уже матрицей переходов d, элементами которой являются вероятности переходов из одного состояния в другое.
Мы будем изучать детерминированные автоматы.
Применяемые на практике автоматы принято разделять на два класса: - это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать.
Закон функционирования автоматов Мили описывается следующей системой уравнений:
a (t + 1) = d [a (t),x (t)]
y (t) = l [a (t),x (t)]
t = 0,1,2,3…
Работа автоматов Мура задается следующими уравнениями:
a (t + 1) = d [a (t),x (t)]
y (t) = l [a (t)]
Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y (t) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.
2. Элементарные автоматы
В настоящее время в вычислительной технике, как правило, используются элементарные автоматы, имеющие следующие особенности:
1. Элементарные автоматы являются автоматами Мура с двумя внутренними состояниями.
2. Автомат выдает два различных выходных сигнала, соответствующих двум его внутренним состояниям. В дальнейшем состояния автомата и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и 1.
3. Элементарные автоматы могут иметь в общем случае несколько физических входов, на каждый из которых могут подаваться сигналы, закодированные цифрами 0 и 1.
Рисунок 2.1 ? триггер
В качестве элементарных автоматов в вычислительной технике используются, в основном, триггеры различных типов. Рассмотрим некоторые из них:
1. Т-триггер.
2. R-s - триггер с разделенными входами.
3. J-k триггер (универсальный триггер) .
3. Табличный метод структурного синтеза конечных автоматов
3.1 Структурный синтез
Структурный синтез конечных автоматов заключается в выборе типов элементарных автоматов, в составлении возбуждения каждого элементарно автомата и функций кодированных выходов заданного автомата.
На этапе структурного синтеза выбираем также способ кодирования состояний и выходных сигналов заданного автомата через состояния и выходные сигналы элементарных автоматов, в результате чего составляют кодированные таблицы переходов и выходов.
Функции возбуждения элементарных автоматов и функции выходов получаются на основе кодированной таблицы переходов и выходов.
Рассмотрим примеры синтеза, которые позволяют сформулировать общий алгоритм структурного синтеза конечных автоматов.
Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов.
Таблица 3.1 - Автомат Мура
|
xj\ai |
a0 |
a1 |
a2 |
|
|
x1 |
a1/y1 |
a1/y2 |
a1/y2 |
|
|
x2 |
a2y3 |
a2/y3 |
a0/y1 |
В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов - элементы И, ИЛИ, НЕ. Итак, имеем A={a0, a1, a2}; X={x1, x2}; Y={y1, y2, y3}. Здесь n=2, n+1=3; m=2, k=3.
Перейдем от абстрактного автомата к структурному, для чего определим количество элементов памяти R и число входных L и выходных N каналов.
R =] log (n+1) [=] log 3 [= 2
L =] log m [=] log 2 [= 1
R =] log k [=] log 3 [= 2.
Таким образом, необходимо иметь два элементарных автомата Q1 и Q2 (т.к. R=2), один входной канал b1 и два выходных канала Z1 и Z2.
Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов.
Таблица 3.2 - Таблица кодирования состояний автомата.
|
Сост. элем. авт. Сост. задан. Абстрактн. авт. |
Q1 |
Q2 |
|
|
a0 |
0 |
0 |
|
|
a1 |
0 |
1 |
|
|
a2 |
1 |
0 |
Таблица 3.3 - Таблица кодирования входных сигналов.
|
Вх. сигн. структ. Авт. Вх. сигн. задан. авт |
d1 |
|
|
X1 |
0 |
|
|
X2 |
1 |
Таблица 3.4 - Таблица кодирования выходных сигналов
|
Вх. сигн. структ. авт Вх. сигн. задан. авт |
Z1 |
Z2 |
|
|
Y1 |
0 |
0 |
|
|
Y2 |
0 |
1 |
|
|
Y3 |
1 |
0 |
Поэтому автомат имеет три состояния, то комбинация состояний элементарных автоматов 11 не используется и является запрещенной (автомат в это состояние никогда не попадет). Здесь и в дальнейшем будем использовать естественное кодирование, когда наборы значений двоичных переменных расписываются в порядке возрастания их номеров. С учетом кодирования перерисуем совмещенную таблицу переходов и выходов абстрактного автомата.
Таблица 3.5 - Выходов конечного автомата Мура
|
Xj\ai |
00 |
01 |
10 |
|
|
0 |
01/00 |
01/01 |
01/01 |
|
|
1 |
10/10 |
10/10 |
00/00 |
В таблицах кодирования выходные каналы Z1 и Z2 называются физическими выходами автомата.
Пользуясь таблицами кодирования можно на основе заданных переходов и выходов построить кодированные таблицы переходов и выходов.
Кодированная таблица переходов определяет зависимость состояний Qi (t+1) элементарных автоматов в момент времени (t+1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t. Т.е.
Qi (t+1) = fi [ (Q1 (t), Q2 (t), …, Qr (t),
В кодированной таблице выходов - выходные сигналы Zl (t) определяются в зависимости от значения входных сигналов и внутренних состояний в момент времени t
Таблица 3.6 - Формирование классов эквивалентности
|
t1 (t) |
Q1 (t) |
Q2 (t) |
Q1 (t+1) |
Q2 (t+1) |
Z1 (t) |
Z2 (t) |
|
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
0 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
- |
- |
- |
- |
|
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
- |
- |
- |
- |
Эти функции являются переключательными, поскольку значения функции и ее аргументов определены в один и тот же момент времени t.
3.2 Построение синтеза функций возбуждения элементарных автоматов
Основная задача, решаемая в процессе структурного синтеза - построение синтеза функций возбуждения элементарных автоматов, которая определяет значения сигналов на входах элементарных автоматов, необходимые для обеспечения переходов автомата из одного состояния в другое. При построение этой таблицы используется матрица переходов выбранных элементарных автоматов, в нашем случае JK-триггеров. С помощью матрицы переходов заполняются столбцы таблицы функций возбуждения. В строках этой таблицы записываются значения Ji и Ki, обеспечивающие нужный переход.
Таблица 3.7 - Формирование классов эквивалентности
|
J |
K |
Q (t) |
Q (t+1) |
|
|
0 |
b1 |
0 |
0 |
|
|
1 |
b2 |
0 |
1 |
|
|
b3 |
1 |
1 |
0 |
|
|
b4 |
0 |
1 |
1 |
Таблица 3.8 - Формирование классов эквивалентности
|
t1 (t) |
Q1 (t) |
Q2 (t) |
Q1 (t+1) |
Q2 (t+1) |
J1 (t) |
K1 (t) |
J2 (t) |
K2 (t) |
|
|
0 |
0 |
0 |
0 |
1 |
0 |
b |
1 |
b |
|
|
0 |
0 |
1 |
0 |
1 |
0 |
b |
b |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
B |
1 |
1 |
b |
|
|
0 |
1 |
1 |
- |
- |
- |
- |
- |
- |
|
|
1 |
0 |
0 |
1 |
0 |
1 |
b |
0 |
b |
|
|
1 |
0 |
1 |
1 |
0 |
1 |
b |
b |
1 |
|
|
1 |
1 |
0 |
0 |
0 |
B |
1 |
0 |
b |
|
|
1 |
1 |
1 |
- |
- |
- |
- |
- |
- |
Например, переход Q1 (t) из 0 в 0 обеспечивается подачей на вход J сигнала 0, а значение сигнала на входе K - безразлично.
Таким образом, получим значения входных сигналов J и K элементарных автоматов, которые зависят как от значения входного сигнала так и от состояния автомата в тот же момент времени, что и Qi и B (т.е. в t).
Поскольку функции возбуждения J (t) и K (е) определенны в тот же момент времени, что и их аргументы Q1 (t), Q2 (t) и B1 (t), то эти функции являются переключательными.
В результате мы получим систему переключательных функций Z1 (t), Z2 (t), J1 (t), K1 (t), J2 (t) и K2 (t) заданных в виде таблиц их истинности.
3.3 Комбинационный синтез конечных автоматов
Следующий этап - комбинационный синтез конечных автоматов. На этом этапе по полученным переключательным функциям синтезируются комбинационные схемы. Очевидно, задача комбинационного синтеза конечных автоматов полностью совпадает с задачей синтеза логических схем, которую мы уже рассматривали. Обычно полученные переключательные функции минимизируют и представляют в булевом базисе, для каждой из которых построим диаграмму Вейча.
Таблица 3.9, 3.10 - комбинационный синтез конечных автоматов
|
J1 |
0 |
0 |
b |
B |
J2 |
1 |
B |
B |
1 |
|
|
1 |
1 |
b |
b |
0 |
b |
b |
0 |
|||
|
K1 |
B |
B |
B |
1 |
K2 |
B |
0 |
B |
B |
|
|
B |
B |
b |
1 |
B |
1 |
b |
B |
Таблица 3.9, 3.10 - комбинационный синтез конечных автоматов
|
Z1 |
0 |
0 |
B |
0 |
|
|
1 |
1 |
b |
0 |
||
|
Z2 |
0 |
1 |
B |
1 |
|
|
0 |
0 |
b |
0 |
Обычно полученную систему ПФ минимизируют совместно. Однако совместная минимизация всех ПФ представляет собой достаточно трудоемкую и длительную операцию, применимую, в общем случае, при использовании машины. В результате минимизации мы получим следующую схему конечного автомата.
Функциональные схемы, получаемые в результате структурного синтеза, в дальнейшем на этапе инженерной доработки подвергаются изменениям. Эти изменения связаны с тем, что добавляются специальные цепи, необходимые для работы разработанной схемы в составе других схем ЦВМ. Например, в схеме регистра сдвига информации добавляется цепь "установка в 0". Другие изменения связаны с особенностью физического представления информации в ЦВМ, с особенностями логических элементов и с техническими особенностями логических элементов и с техническими особенностями конечных автоматов.
4. Тестирование программы
На основании описанного алгоритма на языке C++ в среде Microsoft Visual Studio.net 2012 был разработан программный продукт Курсова. Использование данного продукта позволяет минимизировать автомат Мили. В качестве примера был использован конечный автомат. Исходными данными для работы программы является количество состояний и знаков входного алфавита.
Для начала работы программисту стоит запустить файл Курсова. exe. После запуска появляется окно пользовательского интерфейса (рис.3.1). Интерфейс программы построен в стиле однооконного приложения.
Рассмотрим назначения каждого оконного элемента.
Два поля для ввода
Две кнопки для манипуляции
Одно поле для вывода
Рисунок 3.1 - Начальное окно приложения
При вводе данных надо нажать на кнопку "Построить таблицу КА". При нажатии на кнопку появится поля для ввода данных (рис 3.2).
Рисунок 3.2 - Построить таблицу КА
При нажатии кнопки "Минимизировать КА" минимизированный автомат будет выведен в поле для вывода (рис. 3.3).
Рисунок 3.3 - Вывод
Выводы
В курсовой работе был рассмотрен основные понятия теории Конечных автоматов. Был запрограммирован алгоритм минимизации КА, протестирована программа, обработан список литературы. По полученным результатам, обработки материала, можно сделать вывод, что минимизировать конечные автоматы возможно.
Сделав такой вывод, мы выполнили цель данной работы.
Список использованных источников
1. Абрамов, Л.А. Математическое программирование [Текст] / Л.А. Абрамов, В.Ф. Капустин ? Л.: Изд-во ЛГУ, 1981. ? 328 с.
2. Белоусова, Г.С. Линейное программирование. Учебное пособие [Текст] / Г.С. Белоусова ? Красноярск: Наука, 1975. ? 107 с.
3. Кузнецов, Ю.Н. Математическое программирование: Учебное пособие [Текст] / Ю.Н. Кузнецов - 2-е изд., перераб. и доп. - М.: Высшая школа, 1980. ? 300 с.
4. Ашманов, С.А. Линейное программирование [Текст] / С.А. Ашманов - М.: Наука. 1969. - 240 с.
5. Габасов, Р.И. Методы линейного программирования [Текст] / Р.И. Габасов, Ф.М. Кириллова - Минск: Наука. 1977. - 174 с.
6. Голованова, В.Н. Экономическая оценка инженерных решений [Текст] / В.Н. Голованова. - ХАИ, 1999. - 135 с.
Приложения
Приложение А
Листинг прогаммы
#pragma once
struct C
{
int *Nomber;
int *Znach;
};
namespace Курсова {
using namespace System;
using namespace System:: ComponentModel;
using namespace System:: Collections;
using namespace System:: Windows:: Forms;
using namespace System:: Data;
using namespace System:: Drawing;
public ref class Form1: public System:: Windows:: Forms:: Form
{
public:
Form1 (void)
{
InitializeComponent ();
}
protected:
~Form1 ()
{
if (components)
{
delete components;
}
}
private: System:: Windows:: Forms:: TextBox^ textBox1;
protected:
private: System:: Windows:: Forms:: TextBox^ textBox2;
private: System:: Windows:: Forms:: LinkLabel^ linkLabel1;
private: System:: Windows:: Forms:: LinkLabel^ linkLabel2;
private: System:: Windows:: Forms:: Button^ button1;
private: System:: Windows:: Forms:: Label^ label1;
private: System:: Windows:: Forms:: Button^ button2;
private: System:: Windows:: Forms:: TextBox^ textBox3;
private:
System:: ComponentModel:: Container ^components;
#pragma region Windows Form Designer generated code
void InitializeComponent (void)
{
this->textBox1 = (gcnew System:: Windows:: Forms:: TextBox ());
this->textBox2 = (gcnew System:: Windows:: Forms:: TextBox ());
this->linkLabel1 = (gcnew System:: Windows:: Forms:: LinkLabel ());
this->linkLabel2 = (gcnew System:: Windows:: Forms:: LinkLabel ());
this->button1 = (gcnew System:: Windows:: Forms:: Button ());
this->label1 = (gcnew System:: Windows:: Forms:: Label ());
this->button2 = (gcnew System:: Windows:: Forms:: Button ());
this->textBox3 = (gcnew System:: Windows:: Forms:: TextBox ());
this->SuspendLayout ();
//
// textBox1
//
this->textBox1->Location = System:: Drawing:: Point (-3, - 1);
this->textBox1->Name = L"textBox1";
this->textBox1->Size = System:: Drawing:: Size (78, 20);
this->textBox1->TabIndex = 0;
//
// textBox2
//
this->textBox2->Location = System:: Drawing:: Point (-3, 24);
this->textBox2->Name = L"textBox2";
this->textBox2->Size = System:: Drawing:: Size (78, 20);
this->textBox2->TabIndex = 1;
//
// linkLabel1
//
this->linkLabel1->AutoSize = true;
this->linkLabel1->Location = System:: Drawing:: Point (86,2);
this->linkLabel1->Name = L"linkLabel1";
this->linkLabel1->Size = System:: Drawing:: Size (160, 13);
this->linkLabel1->TabIndex = 2;
this->linkLabel1->TabStop = true;
this->linkLabel1->Text = L"Ведите количество состояний";
//
// linkLabel2
//
this->linkLabel2->AutoSize = true;
this->linkLabel2->Location = System:: Drawing:: Point (86, 27);
this->linkLabel2->Name = L"linkLabel2";
this->linkLabel2->Size = System:: Drawing:: Size (163, 13);
this->linkLabel2->TabIndex = 3;
this->linkLabel2->TabStop = true;
this->linkLabel2->Text = L"Введите количество эл. вх. ал. ";
//
// button1
//
this->button1->Location = System:: Drawing:: Point (350,8);
this->button1->Name = L"button1";
this->button1->Size = System:: Drawing:: Size (143, 36);
this->button1->TabIndex = 4;
this->button1->Text = L"Построить таблицу КА";
this->button1->UseVisualStyleBackColor = true;
this->button1->Click += gcnew System:: EventHandler (this, &Form1:: button1_Click);
//
// label1
//
this->label1->AutoSize = true;
this->label1->Location = System:: Drawing:: Point (3, 57);
this->label1->Name = L"label1";
this->label1->Size = System:: Drawing:: Size (26, 13);
this->label1->TabIndex = 5;
this->label1->Text = L"G (x)";
//
// button2
//
this->button2->Location = System:: Drawing:: Point (350, 52);
this->button2->Name = L"button2";
this->button2->Size = System:: Drawing:: Size (142, 33);
this->button2->TabIndex = 7;
this->button2->Text = L"Минимизировать КА";
this->button2->UseVisualStyleBackColor = true;
this->button2->Click += gcnew System:: EventHandler (this, &Form1:: button2_Click);
//
// textBox3
//
this->textBox3->Location = System:: Drawing:: Point (336, 165);
this->textBox3->Multiline = true;
this->textBox3->Name = L"textBox3";
this->textBox3->Size = System:: Drawing:: Size (155, 20);
this->textBox3->TabIndex = 8;
//
// Form1
//
this->AutoScaleDimensions = System:: Drawing:: SizeF (6, 13);
this->AutoScaleMode = System:: Windows:: Forms:: AutoScaleMode:: Font;
this->ClientSize = System:: Drawing:: Size (491, 346);
this->Controls->Add (this->textBox3);
this->Controls->Add (this->button2);
this->Controls->Add (this->label1);
this->Controls->Add (this->button1);
this->Controls->Add (this->linkLabel2);
this->Controls->Add (this->linkLabel1);
this->Controls->Add (this->textBox2);
this->Controls->Add (this->textBox1);
this->Name = L"Form1";
this->Text = L"Form1";
this->Load += gcnew System:: EventHandler (this, &Form1:: Form1_Load);
this->ResumeLayout (false);
this->PerformLayout ();
}
#pragma endregion
array<TextBox^>^ msv;
array<TextBox^>^ msv1;
int **massA;
int **massA1;
int **massB;
int S;
int F;
int Per;
private: System:: Void Form1_Load (System:: Object^ sender, System:: EventArgs^ e) {
this->Text = "Курсова ";
}
private: System:: Void button1_Click (System:: Object^ sender, System:: EventArgs^ e) {
Single X,Y;
Per = 0;
bool Число_ли1 = Single:: TryParse (textBox1->Text,
System:: Globalization:: NumberStyles:: Number,
System:: Globalization:: NumberFormatInfo:: CurrentInfo, X);
bool Число_ли2 = Single:: TryParse (textBox2->Text,
System:: Globalization:: NumberStyles:: Number,
System:: Globalization:: NumberFormatInfo:: CurrentInfo, Y);
if ( (Число_ли1 == false) || (Число_ли2 == false))
{
linkLabel1->Text = "Следует вводить числа";
linkLabel1->ForeColor = Color:: Red;
return;
}
// // // // // // // // // // // // // // // // // // // // // // // // // //
int x,y,tb,tr;
x= (int) (X);
y= (int) (Y);
S = x; F = y;
massA=new int* [x];
massA1=new int* [x];
massB=new int* [x];
for (int i=0; i<x; i++)
{
massA [i] =new int [y];
massA1 [i] =new int [y];
massB [i] =new int [y];
}
tb=0;
tr=0;
// // // // // // // // // // // // // // // // // // // // // // // /
msv = gcnew array<TextBox^> (x*y);
for (int i = 0; i < msv->Length; i++)
{ if (i%x==0) {tb=tb+20; tr = 0; };
msv [i] = gcnew TextBox ();
msv [i] - >Location = System:: Drawing:: Point (tb,70+20*tr);
msv [i] - >Name = i. ToString ();
msv [i] - >Size = System:: Drawing:: Size (20, 20);
msv [i] - >TabIndex = 0;
Controls->Add (msv [i]);
tr++; }
// // // // // // // // // // // // // // // // // // // // // // // // // // // // // /
Label^ label2;
label2 = gcnew System:: Windows:: Forms:: Label ();
label2->Name = "label2";
label2->Visible = true;
label2->AutoSize = true;
label2->Location = System:: Drawing:: Point (tb+50, 57);
label2->Text = L"F (x)";
label2->TabIndex = 0;
Controls->Add (label2);
// // // // // // // // // // // // // // // // // // // // // // // // // // // // // /
tb = tb +40;
msv1 = gcnew array<TextBox^> (x*y);
for (int i = 0; i < msv->Length; i++)
{ if (i%x==0) {tb=tb+20; tr = 0; };
msv1 [i] = gcnew TextBox ();
msv1 [i] - >Location = System:: Drawing:: Point (tb,70+20*tr);
msv1 [i] - >Name = i. ToString ();
msv1 [i] - >Size = System:: Drawing:: Size (20, 20);
msv1 [i] - >TabIndex = 0;
Controls->Add (msv1 [i]);
tr++; }
}
private: System:: Void button2_Click (System:: Object^ sender, System:: EventArgs^ e) {
textBox3->Size = Drawing:: Size (400, 200);
int z=0;
Single *Z,*Z1;
Z = new Single [S*F];
Z1 = new Single [S*F];
for (int i = 0; i < F; i++) {
for (int j=0; j<S; j++) {
bool Число_ли2 =Single:: TryParse (msv [z] - >Text,
System:: Globalization:: NumberStyles:: Number,
System:: Globalization:: NumberFormatInfo:: CurrentInfo, Z [z]);
massA [j] [i] = (int) (Z [z]);
z++;
}}
z=0;
for (int i = 0; i < F; i++) {
for (int j=0; j<S; j++) {
bool Число_ли2 = Single:: TryParse (msv1 [z] - >Text,
System:: Globalization:: NumberStyles:: Number,
System:: Globalization:: NumberFormatInfo:: CurrentInfo, Z1 [z]);
massB [j] [i] = (int) (Z1 [z]);
z++;
}}
for (int i = 0; i < S; i++) {
for (int j=0; j<F; j++) {
massA1 [i] [j] = massA [i] [j]; }}
// // // // // // // // // // // // // // // // // // // // // // // // // // // // /
C *C1;
C1 = new C [S];
for (int i=0; i<S; i++)
C1 [i]. Znach=new int [S];
// // // // // // // // // // // // // // // // // // // // // // // // // /
int Per1=-1;
while (Per! =Per1)
{int r=0;
if (Per1==-1) {Per1=Per;
for (int i=0; i<S; i++) {
for (int z=i; z<S; z++) {
if (massB [i] [0] ==massB [z] [0])
{for (int d=0; d<F; d++) {
if (massB [i] [d]! =massB [z] [d]) {goto a1; }}}
else {goto a1; }
for (int b=0; b<S; b++) {
for (int x=0; x<S; x++) {
if (C1 [b]. Znach [x] ==z) {goto a1; }}}
C1 [Per]. Znach [r] =z;
r++;
a1:;
}
for (int z=0; z<S; z++) {
if (C1 [Per]. Znach [z] >-1) { Per++; break; }}}
for (int i=0; i<S; i++)
{for (int j=0; j<F; j++) {
for (int o=0; o<Per; o++) {
for (int x=0; x<S; x++)
if (massA1 [i] [j] ==C1 [o]. Znach [x])
{massA [i] [j] =o; break; }}}}
} // // // // // // // // // // // // // // // // // // // // // // // // //
else { Per1=Per;
Per=0;
for (int i=0; i<S; i++)
{for (int j=0; j<S; j++)
{C1 [i]. Znach [j] = (-1); }}
// // // // // // // // // // // // // // // // // // // // // // // // //
r=0;
for (int i=0; i<S; i++) {
for (int z=i; z<S; z++) {
if (massA [i] [0] ==massA [z] [0])
{for (int d=0; d<F; d++) {
if (massA [i] [d]! =massA [z] [d]) {goto a2; }}}
else {goto a2; }
for (int b=0; b<S; b++) {
for (int x=0; x<S; x++) {
if (C1 [b]. Znach [x] ==z) {goto a2; }}}
C1 [Per]. Znach [r] =z;
r++;
a2:;
}
for (int z=0; z<S; z++) {
if (C1 [Per]. Znach [z] >-1) { Per++; break; }}}
for (int i=0; i<S; i++)
{for (int j=0; j<F; j++) {
for (int o=0; o<Per; o++) {
for (int x=0; x<S; x++)
if (massA1 [i] [j] ==C1 [o]. Znach [x])
{massA [i] [j] =o; break; }}}}
}} // // // // // // // // // // // // // // // // // // // // // // // // //
int k=0;
for (int I=0; I<Per; I++)
{for (int j=0; j<S; j++) {
if (C1 [I]. Znach [j] >-1)
{for (int y=0; y<F; y++)
{massA [k] [y] =massA [C1 [I]. Znach [j]] [y]; }
k++;
j=S-1; }
}}
for (int i=0; i<S; i++) {
for (int j=0; j<S; j++) {
if (C1 [i]. Znach [j] >-1)
{
for (int z=0; z<Per; z++) {
for (int x=0; x<F; x++) {
if (C1 [i]. Znach [j] ==massA [z] [x])
{massA [z] [x] =C1 [i]. Znach [j]; }
}}}}}
textBox3->AppendText (String:: Format ("Otvet: \r\n G (x) \r\n"));
for (int i=0; i<Per; i++)
{for (int j=0; j<F; j++) {
textBox3->AppendText (String:: Format ("{0} \t",massA [i] [j])); }
textBox3->AppendText (String:: Format ("\r\n")); }
textBox3->AppendText (String:: Format ("F (x) \r\n"));
for (int i=0; i<Per; i++)
{for (int j=0; j<S; j++)
if (C1 [i]. Znach [j] >-1)
{
for (int c=0; c<F; c++)
textBox3->AppendText (String:: Format ("{0} \t",massB [i] [c]));
textBox3->AppendText (String:: Format ("\r\n"));
break;
}
}
// // // // // // // // // // // // // // // // // // // // // // // // // // // // }
};
}
Размещено на Allbest.ru
Подобные документы
Теоретические основы эквивалентности конечных автоматов-распознавателей и их минимизация. Определение математических моделей Мили и Мура. Их графическое и табличное представление. Примеры построения конечных автоматов, распознающих некоторые языки.
курсовая работа [567,8 K], добавлен 02.05.2015Синтез и детерминизация, алгоритм минимизации автоматов–распознавателей. Машина Тьюринга как универсальный тип абстрактного преобразователя. Моделирование систем и событий с помощью сетей Петри. Методы синтеза структурных автоматов на базе триггеров.
учебное пособие [2,3 M], добавлен 17.06.2014Теоретические и практические основы грамматик, теория конечных автоматов-распознавателей. Эквивалентные и недостижимые состояния конечных автоматов. Классификация грамматик и порождаемых ими языков. Разработка программного комплекса построения грамматик.
курсовая работа [654,2 K], добавлен 14.11.2010Принципы и понятия автоматного программирования. Виды конечных автоматов, их применение при построении лексических и синтаксических анализаторов. Описание конечных автоматов Миля и Мура, их различий в зависимости от способа формирования функций выхода.
курсовая работа [430,9 K], добавлен 26.05.2015Основные понятия структурных автоматов. Этапы канонического метода синтеза. Кодирование алфавитов автомата и выбор элементов его памяти. Построение уравнений булевых функций возбуждения и выходов. Методы устранения гонок в структурных автоматах.
курсовая работа [496,3 K], добавлен 27.01.2011Составление треугольной таблицы. Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Получение логических функций выходов автомата. Синтез конечного автомата и функциональной схемы. Принципиальная электрическая схема.
контрольная работа [215,8 K], добавлен 22.06.2012В статье рассмотрено применение конечных автоматов для создания системы автоматов, связанных графами. Документооборот представляется в виде автомата, обрабатывающего автоматы, каждый из которых моделирует поведенческую единицу системы документооборота.
статья [80,8 K], добавлен 19.04.2006В статье рассмотрено применение конечных автоматов для создания системы автоматов, связанных графами. Документооборот представляется в виде автомата, обрабатывающего автоматы, каждый из которых моделирует поведенческую единицу системы документооборота.
статья [80,8 K], добавлен 15.07.2006Основное направление исследования клеточных автоматов. Математическое определение автоматов. Классификация по типам поведения. Тоталистичные клеточные автоматы. Создание и визуализация в Excel математической модели распространения лесного пожара.
курсовая работа [234,9 K], добавлен 01.11.2014Синтез контролирующих опросных циклических реляторных автоматов. Организация структуры с приоритетной стратегией "дейзи-цепочка", "дейзи-кольцо". Элементарный логический реляторный процессор. Сущность приоритетной перестраиваемой реляторной структуры.
контрольная работа [479,5 K], добавлен 20.03.2016
