МЕТОДИЧЕСКИЕ УКАЗАНИЯ
Для практических занятий и самостоятельной работы студентов
по дисциплине “Теория автоматов и формальных языков”
Ижевск
Издательство ИжГТУ
УДК 62-50 (076.5)
Составитель: д-р техн. наук, проф. М. А. Сенилов
Методические указания для практических занятий и самостоятельной работы студентов по дисциплине «Теория автоматов и формальных языков» / Сост. М. А.Сенилов.– Ижевск: Изд-во ИжГТУ, 2018. – 26 с.
Методические указания содержат задания с образцами их выполнения для практических занятий и самостоятельной работы студентов по дисциплине «Теория автоматов и формальных языков». В качестве задания предлагается на основе заданной формальной грамматики выполнить синтез распознающего автомата. Для выполнения задания необходимо знание основ теории автоматов, теории формальных грамматик и языков. Методические указания предназначены для студентов-бакалавров очной и заочной формы обучения направления подготовки 09.03.04 – «Программная инженерия».
© Сенилов М. А. составление, 2018
© Издательство Ижевского государственного
технического университета
ОГЛАВЛЕНИЕ
1. ТЕМА, ЦЕЛЬ И СОДЕРЖАНИЕ задания.. 4
2. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ. 4
3. ПЕРЕХОД ОТ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ К АВТОМАТНОЙ.. 6
4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА.. 6
5. СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ 10
6. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА.. 14
7. ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ ПРИ ПЕРЕХОДЕ ОТ ГРАММАТИКИ К МИНИМАЛЬНОМУ АВТОМАТУ 17
8. ПОРЯДОК ВЫПОЛНЕНИЯ задания.. 22
9. РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ задания.. 23
СПИСОК ЛИТЕРАТУРЫ... 25
ТЕМА, ЦЕЛЬ И СОДЕРЖАНИЕ ЗАДАНИЯ
Тема задания для практических занятий и самостоятельной работы: Синтез распознающего автомата.
Цель задания состоит в изучении способов задания формальных языков грамматиками, распознающими автоматами и сетями Петри, построении модели конечного автомата, распознающего заданный язык, и его программной реализации.
Содержание и основные этапы работы:
1) построение уникальной (для каждого студента) праволинейной грамматики;
2) построение автоматной грамматики по праволинейной;
3) построение недетерминированного конечного автомата;
4) сведение недетерминированного конечного автомата к детерминированному;
5) построение минимального автомата;
6) выполнение этапов 2-5 с использованием аппарата сетей Петри;
7) программная реализация автомата.
ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ
Исходными данными для выполнения задания являются две таблицы (табл. 1 и табл. 2) и правила вывода R, приведенные ниже.
В таблице 1 первоначально записана лишь первая строка, содержащая перечисление 18 символов сi. Во вторую строку si записываются первые 18 символов фамилии, имени и отчества студента с обязательными пробелами между фамилией и именем, именем и отчеством. Затем в третью строку студент заносит для каждого из 18 символов строки символ из алфавита {x0, x1, x2, x3, x4, x5, x6, x7} в соответствии с табл. 2.
Таблица 1
| ci | c1 | c2 | c3 | c4 | c5 | c6 | c7 | c8 | c9 | c10 | c11 | c12 | c13 | c14 | c15 | c16 | c17 | c18 |
| si | Б | Е | Р | Е | С | Н | Е | В | _ | В | И | К | Т | О | Р | _ | В | Я |
| xi | x5 | x6 | x0 | x6 | x4 | x7 | x6 | x2 | x5 | x2 | x3 | x7 | x5 | x4 | x0 | x5 | x2 | x7 |
Таблица 2 построена на основе подсчета появлений каждой буквы русского алфавита в фамилиях, именах и отчествах контингента студентов.
Затем буквы были сформированы в восемь групп с таким расчетом, чтобы появление каждого из символов x0 – x7 было равновероятным.
Таблица 2
| А | Б | В | Г | Д | Е | Ж | З | И | Й | К | Л | М | Н | О | П |
| x1 | x5 | x2 | x4 | x6 | x6 | x4 | x3 | x3 | x0 | x7 | x0 | x3 | x7 | x4 | x5 |
| P | С | Т | У | Ф | Х | Ц | Ч | Ш | Щ | Ь | Ы | Э | Ю | Я | _ |
| x0 | x4 | x5 | x7 | x2 | x5 | x1 | x2 | x2 | x0 | x6 | x1 | x1 | x3 | x7 | x5 |
Наконец, задана формальная грамматика: G=<Vt, Vn, S, R>, где Vt={c1, c2, c3, …, c18} – терминальный словарь; Vn={S, A, B, C, D, E, F} – нетерминальный словарь; SÎVn – начальный символ грамматики; R – множество правил вывода, которые имеют следующий вид:
S®c1 c2 c3 A; S®c1 c4 c5 B; S®c6 C; S®c7 F;
A®c8 D; A®c9; B®c8 E; B®c9; C®c8E; C®c9;
D®c10 S; D®c11; E®c10 S; E®c11;
F®c12 c13 c14 c15; F®c16 c13 c14 c15; F®c17 c18 c15.
Эта грамматика, являющаяся праволинейной, приводится к виду
G'=<V't, V'n, S, R'>, где V't={x0, …, x7} – новый терминальный словарь; V'n=Vn; R' – множество правил вывода, получаемых из заданных заменой символов из алфавита Vt символами из алфавита V't в соответствии с таблицей 1. В данном примере они имеют вид:
S®x5 x6 x0 A | x5 x6 x4 B | x7 C | x6 F;
A®x2 D | x5;
B®x2 E | x5;
C®x2 E | x5;
D®x2 S | x3;
E®x2 S | x3;
F®x7 x5 x4 x0 | x5 x5 x4 x0 | x2 x7 x0.
Здесь “|” – металингвистический символ (связка), читаемый как "ИЛИ".
Примеры цепочек, принадлежащих языку L(G'), порождаемому грамматикой G': x5 x6 x0 x5, x7 x2 x3, x6 x7 x5 x4 x0. Напротив, цепочки x2 x7 x0 x2 x7, x6 x5 x2 x5 x6 не принадлежат L(G'), так как они не выводимы в грамматике G'.
Грамматика G', порождаемая из заданной грамматики G, является индивидуальным заданием студента.
Примечание. Мощность |V't| словаря V't (число символов в нем) в рассмотренном случае равна 7: словарь не содержит символа x1.
ПЕРЕХОД ОТ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ К АВТОМАТНОЙ
Этот этап выполняется путем расширения нетерминального словаря способом, вытекающим из возможности преобразования праволинейной грамматики в модифицированную автоматную G''=< V't, V''n, S, R''>. Для рассматриваемого примера, который будет сквозным в данных указаниях, получим множество R'' правил вывода:
S®x5 S1; S1®x6 S2; S2®x0 A;
S®x5 S3; S3®x6 S4; S4®x4 B;
S®x7 C;
S®x6 F;
A®x2 D; A®x5 A1; A1®e;
B®x2 E; B®x5 B1; B1®e;
C®x2 E; C®x5 C1; C1®e;
D®x2 S; D®x3D1; D1®e;
E®x2 S; E®x3 E1; E1®e;
F®x7 F1; F1®x5 F2; F2®x4 F3; F3®x0 F4; F4®e;
F®x5 F5; F5®x5 F6; F5®x4 F7; F7®x0 F8; F8®e;
F®x2 F9; F9®x7 F10; F10®x0 F11; F11®e.
Таким образом, нетерминальный словарь теперь имеет вид V''n = {S, S1, S2, S3, S4, A, A1, B, B1, C, C1, D, D1, E, E1, F, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11} и его мощность |V''n| равна 27.