Разработка проектов конечных автоматов 


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



ЗНАЕТЕ ЛИ ВЫ?

Разработка проектов конечных автоматов



КУРСОВОЕ ПРОЕКТИРОВАНИЕ

Разработка проектов конечных автоматов

Методическое пособие для студентов (бакалавров)

Специальности

Б.1.В.ОД.5 «Теория конечных автоматов»

 

Направление подготовки

Автоматизация технологических процессов и производств».

 

Квалификация выпускника

Бакалавр

 

Форма обучения

Очная

 

Москва

Содержание

Элементы теории автоматов

ЗАДАНИЕ № 02-18 НА РАЗРАБОТКУ ПРОЕКТА КА

«СИСТЕМА ТРАНСПОРТИРОВАНИЯ СЫПУЧЕГО МАТЕРИАЛА

Пример конкретного выполнения

ЗАДАНИЕ № 03-18 НА РАЗРАБОТКУ ПРОЕКТА КА

 «СИСТЕМА МЕХАНИЧЕСКОЙ ОБРАБОТКИ ДЕТАЛИ «

Пример конкретного выполнения.

Элементы теории автоматов

Понятие конечного автомата

 

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

По входному каналу в каждый момент времени t =1, 2,... в устройство М поступают входные сигналы (из некоторого конечного множества сигналов). Задается закон изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния устройства в текущий момент времени. Выходной сигнал зависит от состояния и входного сигнала в текущий момент времени (рис. 1).

 

 

 


Конечный автомат является математической моделью реальных дискретных устройств по переработке информации.

Конечным автоматом называется система А=(X, Q, Y, j, y), где X, Q, Y — произвольные непустые конечные множества, а j и y - функции, из которых:

1) множество X={ a 1,..., am } называется входным алфавитом, а его элементы — входными сигналами, их последовательности — в ходными словами;

2) множество Q={ q 1,..., qn } называется множеством состояний автомата, а его элементы — состояниями;

3) множество Y ={ b 1,..., bp } называется выходным алфавитом, его элементы — выходными сигналами, их последовательности — выходными словами;

4) функция j: X´Q® Q называется функцией переходов;

5) функция y:X´Q® Y называется функцией выходов.

Таким образом, j (x, q)ÎQ, y (x, q)Î Y для " x ÎX, " q ÎQ.

С конечным автоматом ассоциируется воображаемое устройство, ко­торое работает следующим образом. Оно может находиться в состоянии из множества Q, воспринимать сигналы из множества X и выдавать сигналы из множества Y.

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

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

2.1.Табличное задание автомата

Из определения автомата следует, что его всегда можно задать табли­цей с двумя входами, содержащей т строк и п столбцов, где на пересечении столбца q и строки а стоят значения функций j (ai, qj), y (ai, qj).

q a q 1 qj qn
a 1 j (a 1, q 1), y (a 1, q 1) j (a 1, qj), y (a 1, qj) j (a 1, qn), y (a 1, qn)
ai j (ai, q 1), y (ai, q 1) j (ai, qj), y (ai, qj) j (ai, qn), y (ai, qn)
am j (am, q 1), y (am, q 1) j (am, qj), y (am, qj) j (am, qn), y (am, qn)

 

Задание автомата диаграммой Мура

Другой способ задания конечного автомата — графический, то есть с помощью графа. Автомат изображается в виде помеченного ориентированного графа Г (Q, D) с множеством вершин Q и множеством дуг D ={(qj, j (ai, qj))| qj ÎQ, ai ÎX}, при этом дуга (qj, j (ai, qj)) помечается парой (ai, y (ai, qj)). Таким образом, при этом способе состояния автомата изображают кружками, в которые вписывают символы состояний qj (j=1, …, n). Из каждого кружка проводится т стрелок (ориентированных ребер) взаимно-однозначно соответствующих символам входного алфавита X={ a 1,..., am }. Стрелке, соответствующей букве ai ÎX и выходящей из кружка qj ÎQ, приписывается пара (ai, y (ai, qj)), причем эта стрелка ведет в кружок, соответствующий j (ai, qj).

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

 

Задание конечного автомата системой булевых функций

Третий способ задания конечного автомата А=(X, Q, Y, j, y), задан­ного таблицей или диаграммой Мура, состоит в определении системы булевых функций.

Изложим алгоритм этого способа задания.

(1)  Находим числа k, r, s, удовлетворяющие условиям 2k-1< m <2k, 2r-1< n ≤2r, 2s-1< m <2s, где m =| Х |, п=| Q |, p=| Y |.

Очевидно, что k, r, s соответственно равны числу разрядов в двоичном представлении чисел т, п, р. Например, если m =5, n=17, р=3, то k=3, r =5, s =2.

(2) Кодирование состояний входных и выходных символов исходного автомата.

Каждому qj ÎQ взаимно однозначно ставим в соответствие двоичную последовательность длины r — двоичный код a (q)=z1z2...zr. Аналогично каждому ai ÎX и каждому bk ÎY ставим взаимно однозначно в соответствие двоичные последовательности b (a)=x1x2...xk, g (b)=y1y2...ys.

Отметим, что кодирование состояний, входных и выходных символов можно провести многими способами. При этом некоторые последователь­ности (коды) могут оказаться неиспользованными.

(3) Составляем следующую таблицу:

Код

входного

символа

Код

текущего

состояния

Код

следующего

состояния

Код

выходного

символа

x1 x2 ... xk z1 z2 ... zr j1 j2 ... jr y1 y2 ... ys
0 0 0 0 0 0                
                               
b1 b2 ... bk a1 a2 ... ar   g1 g2 ... gs
                               
1 1 1 1 1 1                

 

Эта таблица содержит k+ r + r +s столбцов и 2 k + r строк. В первых k+ r столбцах выписаны все наборы длины k+ r. Каждый такой набор соответ­ствует паре (b, a), где a — возможный код некоторого состояния, b —код входного символа.

(4)     Заполнение последних столбцов в таблице (предыдущий шаг). Для каждой пары (ai, qj), где ai ÎX, qj ÎQ, находим код b (a) и a (q).

По таблице автомата (или диаграмме Мура) определяем j (a, q)= q ¢ и y (a, q)= b. Затем находим код a (q ¢)=  и код g (b)=g1g2…g s. В строку таблицы, соответствующую набору

b1, b2, …, b k, a1, a2, …, a r,

дописываем набор

, , …, , g1, g2, …, g s.

(5) Определение системы булевых функций.

После выполнения предыдущего шага может оказаться, что не все строки в таблице заполнены. Это произойдет в том случае, если хотя бы одно из чисел т, п не является степенью 2. Таким образом, функции j1, j2, …, jr, y1, y2, …, ys окажутся не полностью определенными — на некоторых наборах их значения не определены. Тогда мы их доопределяем произвольным образом. Как правило, доопределение функций производят так, чтобы получившиеся полностью определенные функции удовлетворяли тем или иным условиям оптимальности, например представлялись минимальными ДНФ.

После выполнения этого шага исходный автомат будет задаваться системой полностью определенных булевых функций

{j1, j2, …, jr, y1, y2, …, ys }.

 

 

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

 

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

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

Приведём несколько примеров конечных автоматов.

Пример 1. Элемент задержки (элемент памяти).

Элементы задержки представляют собой устройство, имеющее один вход и один выход. Причем значение выходного сигнала в момент времени t совпадает со значением сигнала в предыдущий момент. Схематично элемент задержки можно изобразить следующим образом (рис. 2).

 

 


Предположим, что входной и, следовательно, выходной алфавит есть X={0, 1}, Y={0, 1}. Тогда Q ={0, 1}. Под состоянием элемента задержки в момент времени t понимается содержание элемента памяти в данный момент. Таким образом q(t)=X(t-1), a Y(t)=q(t)=X(t-1).

Зададим элемент задержки таблицей, где а1=0, а 2=1, q1=0, q 2=1,

j (a 1, q 1)= j (0, 0)=0, y (a 1, q 1)= y (0, 0)=0;

j (a 1, q 2)= j (0, 1)=0, y (a 1, q 2)= y (0, 1)=1;

j (a 2, q 1)= j (1, 0)=1, y (a 2, q 1)= y (1, 0)=0;

j (a 2, q 2)= j (1, 1)=1, y (a 2, q 2)= y (1, 1)=1;

q a 0 1
0 j =0, y =0 j =0, y =1
1 j =1, y =0 j =1, y =1

Диаграмма Мура изображена на рис. 3

 

 


Для представления этого автомата системой булевых функций ис­пользуем таблицу автомата и вышеизложенный алгоритм. При этом ко­дирование производить не нужно, так как входной и выходной алфавиты и состояния уже закодированы.

Обратим внимание на то, что т=п=р=2. Тогда k= r = s =1, и поэтому элемент задержки задается двумя функциями j и y. Таблица истинности этих функций содержит 2 k + r =22=4 строки и k+ r + r +s=4 столбца:

x z j y
0 0 0 0
0 1 0 1
1 0 1 0
1 1 1 1

 

Пример 2. Двоичный сумматор последовательного действия.

Данный сумматор последовательного действия представляет собой устройство, осуществляющее сложение двух чисел в двоичной системе исчисления. На входы сумматора подаются числа х1 и x2, начиная с младших разрядов. На выходе формируется последовательность, соответствующая записи числа х1+x2 в двоичной системе исчисления (рис. 4).

 

 

 


Входной и выходной алфавиты определены однозначно: X={00; 01; 10; 11}, Y ={0,1}. Множество состояний определяется значением пере­носа при сложении соответствующих разрядов чисел х1 и x2. Если при сложении некоторых разрядов образовался перенос, то будем считать, что сумматор перешел в состояние q 1. При отсутствии переноса будем считать, что сумматор находится в состоянии q 0.

Сумматор задается таблицей.

q a q 0 q 1
00 q 0, 0 q 0, 1
01 q 0, 1 q 1, 0
10 q 0, 1 q 1, 0
11 q 1, 0 q 1, 1

 

Диаграмма Мура сумматора последовательного действия изображена на рис. 5.

Заметим, что входные и выходные символы уже закодированы. Состояния закодируем следующим образом: a (q 0)=0, a (q 1)=1. Поэтому сумматор последовательного действия задается двумя булевыми функциями, таблица истинности которых следующая:

x 1 x 2 z j y
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

 

Пример 3. Схема сравнения на равенство.

Схема сравнения на равенств представляет собой устройство, срав­нивающее два числа х1 и x2, заданное в двоичной системе исчисления. Это устройство работает следующим образом. На вход устройства после­довательно, начиная со старших, подаются разряды чисел х1 и x2. Эти разряды сравниваются. При совпадении разрядов на выходе схемы формируется выходной сигнал 0, в противном случае на выходе появляется сигнал 1. Ясно, что появление 1 в выходной последовательности означает, что сравниваемые числа х1 и x2 различны. Если же выходная последовательность является нулевой и ее длина совпадает с числом разрядов сравниваемых чисел, то х1 и x2.

Для этого автомата X={00, 01, 10, 11}; Y={0,1}.

Функционирование схемы определяется двумя состояниями. Состояние q0 соответствует равенству сравниваемых в данный момент разрядов. При этом автомат остается в этом же состоянии. Если в следующий момент сравниваемые разряды будут различны, то автомат перейдет в новое состояние q1 и в нем остается, так как это означает, что числа различны. Таким образом, схему сравнения можно задать таблицей:

q x q 0 q 1
00 q 0, 0 q 1, 1
01 q 1, 1 q 1, 1
10 q 1, 1 q 1, 1
11 q 0, 0 q 1, 1

Диаграмма Мура схемы сравнения на равенство изображена на рис. 6.

 
Рис. 6


Кодирование состояний произведем следующим образом: a (q 0)=0, a (q 1)=1. Автомат будет задаваться двумя функциями.

 

x1 x2 z j y
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 1 0 0 0
1 1 1 1 1

 

Пример 4. Схема сравнения на неравенство.

Схема сравнения на неравенство представляет собой устройство, позволяющее выяснить, равны ли сравниваемые х1 и x2, и если они не равны, выяснить, какое из них больше другого. Это устройство имеет два входа и два выхода. Выходные сигналы y1(t) и y2(t) определяются по следующим правилам:

y1(t)=y2(t)=0, если x1(t)=x2(t);

y1(t)=1, y2(t)=0, если x1(t)>x2(t), то есть x1(t)=1, x2(t)=0;

y1(t)=0, y2(t)=1, если x1(t)<x2(t), то есть x1(t)=0, x2(t)=1.

Таким образом, при подаче на вход схемы сравнения на неравенство чисел x1=x1(l)…x1(t) и x2=x2(l)…x2(t) последовательно сравниваются разряды этих чисел, начиная со старших. Выходные сигналы формулируются согласно вышеуказанным правилам. При этом, если выходная последовательность состоит из нулевых пар, то x1=x2. Если первая, отличная от нулевой, пара имеет вид , () то x1>x2 (x1<x2).

Из описания схемы следует, что

X={00, 01, 10, 11}, Y ={00, 01, 10}.

Состояние схемы определяется следующим образом. Предположим, что в начальный момент времени t=1 автомат находится в состоянии q1. Если сравниваемые разряды чисел х1 и х2 совпадают, то автомат остается в этом состоянии. Заметим, что на выходе при этом появится сигнал 00. Если же разряд числа х1 будет меньше (больше) соответствующего разряда числа х2, то автомат перейдет в состояние q2 (q3). При этом на выходе появится сигнал 01 (10). В дальнейшем при подаче оставшихся разрядов чисел х1 и х2 на входы автомата автомат будет оставаться в состоянии q2 (q3) и вырабатывать выходной символ 10 (01). Из вышеизложенного следует, что схему сравнения на неравенство можно задать таблицей:

q x q 1 q 2 q 3
00 q 1, 00 q 2, 01 q 3, 10
01 q 2, 01 q 2, 01 q 3, 10
10 q 3, 10 q 2, 01 q 3, 10
11 q 1, 00 q 2, 01 q 3, 10

 

Соответствующая диаграмма Мура изображена на рис. 7.

Входной и выходной алфавиты здесь уже закодированы. Состояния q1, q2 и q3 закодируем: a 1(q 1)=00, a (q 2)=01, a (q 3)=10.

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

  x1 x2 z1 z2 j1 j2 y1 y2
  0 0 0 0 0 0 0 0
  0 0 0 1 0 1 0 1
  0 0 1 0 1 0 1 0
* 0 0 1 1 1 1 1 1
  0 1 0 0 0 1 0 1
  0 1 0 1 0 1 0 1
  0 1 1 0 0 1 0 1
* 0 1 1 1 1 1 1 1
  1 0 0 0 1 0 1 0
  1 0 0 1 0 1 0 1
  1 0 1 0 1 0 1 0
* 1 0 1 1 1 1 1 1
  1 1 0 0 0 0 0 0
  1 1 0 1 0 1 0 1
  1 1 1 1 1 0 1 0
* 1 1 1 1 1 1 1 1

В таблице символами * отмечены наборы переменных x1, x2, z1, z2, на которых функции j1, j2, y1, y2 не определены. Положим значения функций j1, j2, y1, y2 на этих наборах равными 1.

 

 

ЗАДАНИЕ № 02-18 НА РАЗРАБОТКУ ПРОЕКТА  КА

СИСТЕМЫ ТРАНСПОРТИРОВАНИЯ

 СЫПУЧЕГО МАТЕРИАЛА

ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

Разработать проект конечного автомата (КА) системы транспортирования сыпучего материала из бункеров «А» в бункера «Б» с помощью транспортеров-конвейеров Тк. Из бункеров А на транспортер выгрузка осуществляется  через шиберные заслонки Ш.

Контролируемые параметры: верхние уровни Ав,  Бв, нижние уровни Ан, Бн, наличие (отсутствие) материала на ленте транспортера в начале транспортера Мн, в конце транспортера Мо, контроль работы транспортеров РКт, контроль положения заслонок (Шо, Шз).

СОСТАВ ПРОЕКТА

Граф автомата

Схема автомата

Кодирование автомата

Приборная реализация

ПРИМЕР ИСПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ

Символ состояния входа

ЗАДАЧА КА

ОПИСАНИЕ ПРОЦЕССА ПО ВХОДУ

(СОСТОЯНИЕ ВХОДОВ)

( j ) - функции переходов входов

 

РЕАЛИЗАЦИЯ ЗАГРУЗКИ

ВХОДЫ (Xi)   ВКЛЮЧЕНИЕ ОТКЛЮЧЕНИЕ  
х1 min Б (вход UБн)

(х1) Ú (х2)

(х1)*(` х2)*

*(х4)* (` х3)

(` х1)*(х2)*

*(х3)*(` х4)

 
х2 max Б (вход UБв)  
х3 min А (вход UАн)

(х3) Ú (х4)

 
х4 max А (вход UАн)  
х5 МТ1н (материал на начале транспортера имеется)

(х5) Ú (х6)

(х6)*(х8)

(х6)*(х8)*

*(` х5)*(` х6)

 
х6 МТ1о (материал на начале транспортера отсутствует)  
х7 МТ2н (материал в конце транспортера имеется)

(х7) Ú (х8)

 
х8 МТ2о (материал в конце транспортера отсутствует)  

ПРОМЕЖУТОЧНЫЕ (ВНУТРЕННИЕ)

 СОСТОЯНИЯ КА ХАРАКТЕРИЗУЮТСЯ

У3- Шо (шибер открыт),

У4- Шз (шибер закрыт)

ВЫХОД КА

Описание функций переходов

Функции переходов могут быть заданы в «Табличной форме», «Булевыми функциями», «Графически».

Задание автомата таблицей

Вход x Є X

Выход y Є Y

Выход КА

    x1 x2 x3 x4 x5 x6 x7 x8 y1 y2 y3 y4 z1 z2   q0 x1 x2 x3 x4 x5 x6 x7 x8   1   1 1 0   q1 1 0       1   1 1       1 0   q2 1         1   1   1     1 0   q3   1 0     1   1     1   1 0   q4 0 1                   1 1 0   q5                         1 0   q6                         1 0   q7                         1 0   q8                         0 1  

Граф автомата

Схема автомата

         
 
 
 


Z 2 = (` х1)*(х2)*(х3)*(х4) (х6)*(х8)*(` х5)*(` х6)(у4)(у2)

у1 = (х1)(` х2) (х6) (х8) (` у2) =(х1)(` х2)(х6) (х8) ` [ (х6х8(х2)(` х1))]

 у2= х6х8у4 = х6х8(х2)(` х1)

у3=(у1)(` х3)(` х2) = (у1)(` х3) ` ([х6х8(х2)(` х1)])

у4 = (х2)(` х1)

Приборная реализация

Задание по вариантам

 Разработать конечный автомат для транспортной системы

 

Функциональная технологическая задача с коментариями для формирования конечного автомата

Транспортная система Обеспечения наличие М атериалов М(i)    

 в п риемных Б ункерах БМп(j). Каждый бункер БМп(j) имеет контроль состояния по наличию или отсутствию материалов по уровню: Упн (нижний уровень приема) – нет материала, Упв – (верхний уровень приема) (имеется материал). Промежуточное положение (последующее состояние между Упн и Упв) определяется Предыдущим состоянием уровня в бункере (Бу(t +1)    Бу(t)).

Состояние бункеров в приборном исполнении контролируется дискретными уровнемерами наличие нижнего уровня- наличие верхнего уровня

 Обеспечение осуществляется путем перегрузки транспортной системой Т из расходных бункеров БМр i системой последовательно включенных транспортных перегрузочных устройств Тк (ленточных конвейеров, элеваторов, винтовых конвейеров)

Выгрузка из каждого БМр осуществляется через шибер расходный, имеющий два состояния – закрытое (заперт на проход) (Шрз) и открытое (свободен на проход) (Шрс).

Каждый шибер снабжен приводом шибера расходный (Дшр), который включается на открытие (если предыдущее состояние закрытое) и включается на закрытие, если предыдущее состояние открытое.

Загрузка каждого приемного бункера БМп осуществляется через шибер приемный (или через плужковый сбрасывавтель), имеющий два состояния - закрытое (заперт на проход) Шпз и открытое (свободен на проход) (Шпс)

Уровни Упн – нижний приемного бункера, Упв – верхний приемного бункера

Каждый шибер снабжен приводом шибера приемный (Дшп), который включается на открытие (если предыдущее состояние закрытое) и включается на закрытие, если предыдущее состояние открытое.п

Состояние в приборном исполнении (Положение шиберов) контролируется концевым выключателем по двум состояниям закрытое-открытое.

Перегрузочные устройства Тк снабжены приводами ДТк имеющими два состояния закрытое (З акрыто на проход- привод отключен) (Тпз)  

Открыто (открыто на проход. С водбоден на проход – привод включен включено (Тпс)

Состояние в приборном исполнении (включено-отключено) контролируется Реле конроля скорости (РКС)

 

РАЗРАБОТКА КА

Исход – технологическая схема

Разработка– Структуры КА

Минимизация структуры

Приборная реализация структуры.

Приборная реализация системы управления с КА

 

ТЕХНОЛОГИЧЕСКАЯ СХЕМА (ЗАДАНИЕ НА РАЗРАБОТКУ ТЕХНОЛОГИЧЕСКОЙ СХЕМЫ

 

 

 


ИНДЕКС Вариант 1 2 3 4 5 6 7 8 9 10 11 12
БМр   3 3 3 3 2 2 2 2 1 1 1 1
БМп   4 3 2 1 3 4 3 2 4 3 2 2
Тк   1 2 3 4 2 2 3 4 3 4 3 2
Тип Тк                          

КУРСОВОЕ ПРОЕКТИРОВАНИЕ

Разработка проектов конечных автоматов

Методическое пособие для студентов (бакалавров)

Специальности



Поделиться:


Читайте также:




Последнее изменение этой страницы: 2020-11-23; просмотров: 431; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.15.229.113 (0.172 с.)