Получили детерминированный и минимизированный конечный автомат.
Задание к работе:
1. Построить конечные автоматы в программе Automata Guide. Проработать основные операторы данной программы.
1. 
2. 
3. 
4. 
5.
Порядок выполнения работы:
1. Изучить пример.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Укажите, где применяются конечные автоматы.
2. Как можно представить (задать) конечный автомат?
3. Можно использовать конечный автомат в словаре?
Практическая работа № 14
Тема: Решение задач по теории конечных автоматов.
Структурная схема конечных автоматов.
Цель: ознакомление со структурной схемой конечного автомата; усвоение навыков решения задач прогнозирования, управления, освоение способов задания автоматов.
Задачи: использования специального программного обеспечения для моделирования; построение адекватной модели.
Материальное обеспечение: практическая работа.
Общие теоретические положения
В структурной теории автомат представляют в виде композиции двух частей: запоминающей части, состоящей из элементов памяти, и комбинационной части, состоящей из логических элементов. Комбинационная схема, строится из логических элементов, образующих функционально полную систему, а память – на элементарных автоматах, обладающих полной системой переходов и выходов.
|
|
|
Каждое состояние абстрактного автомата ai, i=0,n, кодируется в структурных автоматах набором состояний элементов памяти Q2, R=1,R. Поскольку в качестве элементов памяти используются обычные двоичные триггера, то каждое состояние можно закодировать двоичным числом ai=Q1Q2….Qr. Здесь Q – состояние автомата, а ai = {0, 1}/ Как и прежде Q
Общее число необходимых элементов памяти можно определить из следующего неравенства 2R > n + 1. Здесь (n+1) – число состояний. Логарифмируя неравенство получим R > ]log2 (n+1)[. Здесь ]с[ - означает, что необходимо взять ближайшее целое число, большее или равное C.
В отличии от абстрактного автомата, имеющего один входной и один выходной канала, на которые поступают сигналы во входном X={x1, x2,…..,xm} и выходном Y={y1,y2,….,yk} алфавитах, структурный автомат имеет L входных и N выходных каналов. Каждый входной xj и выходной yj сигналы абстрактного автомата могут быть закодированы двоичным набором состояний входных и выходных каналов структурного автомата.
Очевидно число каналов L и N можно определить по формулам
L ³ ]log m[;
N ³ ]log k[,
аналогичным формуле для определения a3 под действием сигнала xj с выдачей сигнала yg соответствует переход структурного автомата из состояния ai в состояние as под действием сигнала xj с выдачей сигнала yg соответствует переход структурного автомата из состояния ( 
) в состояние ( 
), под действием входного сигнала ( 
) с выдачей выходного сигнала ( 
). Для того, чтобы структурный автомата перешел из одного состояния в другое, необходимо изменить состояние элементов памяти Qr.
|
|
|
Изменение же состояния элементов памяти происходит под действием сигналов U=(U1,U2,…,Ur) поступающих на их входы. Эти сигналы формируются комбинационной схемой II и называются функций возбуждения элементов памяти (элементарных автоматов). На вход комбинационной схемы II, кроме входного сигнала xj, по цепи обратной связи поступают сигналы Q=(Q1, Q2, …, QR), называемые функцией обратной связи от памяти автомата к комбинационной схеме. Комбинационная схема I служит для формирования выходного сигнала yg, причем в случае автомата Мили на вход этой схемы поступает входной сигнал xj, а в случае автомата Мура – сигнал xj не поступает, т.к. yg не зависит от xj.
Примеры конечного автомата
Дата добавления: 2019-02-22; просмотров: 583; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!