- •Самарский государственный архитектурно-строительный университет
- •Оглавление
- •Введение
- •Задание на курсовое проектирование
- •Построение и преобразование грамматик
- •3. Построение детерминированного конечного автомата
- •4. Минимизация автомата
- •5. Работа с сетями Петри
- •6. Кодирование состояний автомата
- •7. Структурный синтез автомата
- •Библиографический справочник
Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
Самарский государственный архитектурно-строительный университет
Факультет информационных систем и технологий
Кафедра прикладной математики и вычислительной техники
О.В. Прохорова
Методические указания к выполнению курсовой работы
«Синтез конечных автоматов» для студентов специальности 230400
по дисциплине «Информационные технологии»
Самара 2013
УДК 62-50 (076.5 )
Синтез конечных автоматов: Методические указания к выполнению курсовой работы для студентов специальности 230400 / cост. О.В. Прохорова. – Самара, СГАСУ, 2013. - 41c.
Изложены основные требования к выполнению курсовой работы по синтезу конечных автоматов. Приведено индивидуальное задание, описан пример построения автомата по заданной грамматике и его схемотехническая реализация, даны сведения, необходимые для выполнения работы.
.
Оглавление
Введение 4
1.Задание на курсовое проектирование 5
2. Построение и преобразование грамматик 8
3. Построение детерминированного конечного автомата 10
4. Минимизация автомата 13
5. Работа с сетями Петри 16
6. Кодирование состояний автомата 19
7. Структурный синтез автомата 24
Библиографический справочник 40
Введение
Синтез конечных автоматов является важным разделом в изучении вопросов организации вычислительных процессов и структур. Необходимость в построении теории автоматов возникла с развитием вычислительной техники, с появлением теории формальных языков и грамматик - теории, позволяющей описывать и анализировать синтаксические свойства языков программирования и других формальных языков. Потребовалось решение вопросов преобразования грамматик в автоматы, которые бы распознавали и транслировали множества, задаваемые грамматиками.
Основой изучения данного раздела теории является
построение базовых формальных моделей описания логических структур, динамики поведения вычислительных структур;
выработка навыков проектирования вычислительных систем;
формирование представления о методах, используемых при решении задач анализа, синтеза организации функционирования вычислительных структур и системного программного обеспечения.
Задание на курсовое проектирование
Построение право-линейной грамматики по полученным данным.
Переход от право-линейной грамматики к автоматной. Результат -
Право-линейная и автоматная грамматики.
Построение недетерминированного распознающего автомата.
Результат - таблица переходов и граф переходов автомата.
Переход от недетерминированного автомата к полностью опреде-
ленному детерминированному автомату. Результат - таблица перехо-
дов и граф переходов автомата, проверка эквивалентности автоматов.
Минимизация автомата. Построение таблиц переходов на основе
эквивалентных преобразований. Построение разбиения множества
состояний на классы эквивалентности. Результат - таблица переходов
и граф переходов минимального автомата.
Выполнение предыдущего этапа с использованием сети Петри. Результат - сеть Петри, соответствующая автоматной грамматике, и минимальная сеть Петри. Сравнение полученной минимальной сети с таблицей переходов минимального автомата.
Кодирование состояний автомата. Результат - логические функции переключения элементов памяти; логические функции состояния ошибки и состояния, подтверждающего принадлежность анализируемой формальной цепочки входных символов формальному языку заданной грамматики.
Построение комбинационной схемы автомата.
Для синтеза конечного автомата задана формальная грамматика
G = < V , W , S , R >,
где V = {c1, c2,..., c18} - словарь терминальных символов;
W = {S, A, B, C, D, E, F} - словарь нетерминальных символов;
S - начальный символ грамматики; R - множество правил вывода:
S c1 c2 c3 A С c8 E
S c1 c4 c5 B C c9
S c6 C D c10 S
S c7 F D c11
A c8 D E c10 S
A c9 E c11
B c8 E F c12 c13 c14 c15
B c9 F c10 c13 c14 c15
F c17 c18 c15
Задача курсовой работы - синтезировать конечный автомат, распознающий цепочки входного языка на принадлежность заданной грамматике.
Для выполнения индивидуальной работы требуется перейти к новому терминальному словарю, используя табл. 1 и 2.
Таблица 1
А |
Б |
В |
Г |
Д |
Е |
Ж |
З |
И |
Й |
К |
Л |
М |
Н |
О |
П |
x1 |
x5 |
x2 |
x4 |
x6 |
x6 |
x4 |
x3 |
x3 |
x0 |
x7 |
x0 |
x3 |
x7 |
x4 |
x5 |
Р |
С |
Т |
У |
Ф |
Х |
Ц |
Ч |
Ш |
Щ |
Ъ |
Ы |
Э |
Ю |
Я |
|
x0 |
x4 |
x5 |
x7 |
x2 |
x5 |
x4 |
x2 |
x2 |
x0 |
x6 |
x1 |
x1 |
x3 |
x7 |
x5 |
Таблица 2
c1 |
c2 |
c3 |
c4 |
c5 |
c6 |
c7 |
c8 |
c9 |
c10 |
c11 |
c12 |
c13 |
c14 |
c15 |
c16 |
c17 |
c18 |
д |
о |
с |
о |
в |
|
я |
р |
о |
с |
л |
а |
в |
|
а |
л |
е |
к |
x6 |
x4 |
x4 |
x6 |
X2 |
x5 |
x7 |
x0 |
x4 |
x4 |
x0 |
X1 |
x2 |
x5 |
X1 |
X0 |
X6 |
X7 |