Главная Учебники - Разные Лекции (разные) - часть 17
|
Министерство образования и науки российской федерации Федеральное агентство по образованию РФ Государственное образовательное учреждение "Ижевский государственный технический университет" МЕТОДИЧЕСКИЕ УКАЗАНИЯ к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» Ижевск Издательство ИжГТУ 2008 УДК 62-50 (076.5) Составитель: д-р техн. наук проф. М. А. Сенилов Рецензент: д-р техн. наук, проф. А. И. Мурынов Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» / Сост. М. А. Сенилов. – Ижевск: Изд-во ИжГТУ, 2008. – 28 с. Методические указания освещают основные вопросы выполнения курсовой работы по дисциплине «Теория языков программирования и методы трансляции», включающей тематику теории автоматов, теории формальных грамматик и языков. В них дается индивидуальное задание, а также приводятся рекомендации и сведения, необходимые для выполнения курсовой работы. Методические указания предназначены для студентов направления 230100 – «Информатика и вычислительная техника» и специальности 230105 – «Программное обеспечение вычислительной техники и автоматизированных систем». © Сенилов М. А. составление, 2008 © Издательство Ижевского государственного технического университета ОГЛАВЛЕНИЕ 1. ТЕМА, ЦЕЛЬ И СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ... 4
3. ПЕРЕХОД ОТ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ К АВТОМАТНОЙ.. 6
4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА.. 6
5. СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ 10
6. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА.. 14
7. ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ ПРИ ПЕРЕХОДЕ ОТ ГРАММАТИКИ К МИНИМАЛЬНОМУ АВТОМАТУ 17
8. ПОРЯДОК ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ... 22
9. РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ... 23
1. ТЕМА, ЦЕЛЬ И СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ
Тема курсовой работы: Синтез распознающего автомата. Цель курсовой работы состоит в изучении способов задания языков грамматиками, распознающими автоматами и сетями Петри, построении модели конечного автомата, распознающего заданный язык, и его программной реализации. Содержание и основные этапы работы: 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} – новый терминальный словарь; 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. 3. ПЕРЕХОД ОТ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ К АВТОМАТНОЙ
Этот этап выполняется путем расширения нетерминального словаря способом, вытекающим из возможности преобразования праволинейной грамматики в модифицированную автоматную 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. 4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА
Построим на основе грамматики G'' конечный автомат. При этом нетерминальным символам грамматики V''n
поставим в соответствие состояния автомата (оставим для них те же обозначения). Начальному нетерминалу S поставим в соответствие начальное состояние автомата S. Правилам вывода поставим в соответствие переходы автомата. В результате получим таблицу 3 – таблицу переходов недетерминированного конечного автомата, соответствующего рассматриваемому примеру. Таблица
3 Таблица переходов недетерминированного частичного автомата x0 x2 x3 x4 x5 x6 x7 S S1,S3 F C 0 S1 S2 0 S2 A 0 S3 S4 0 S4 B 0 A D A1 0 A1 1 B E B1 0 B1 1 C E C1 0 C1 1 D S D1 0 D1 1 E S E1 0 E1 1 F F9 F5 F1 0 F1 F2 0 F2 F3 0 F3 F4 0 F4 1 F5 F6 0 F6 F7 0 F7 F8 0 F8 1 F9 F10 0 F10 F11 0 F11 1 Полученный автомат является неполностью определенным (частичным), поскольку в таблице переходов (табл. 3) есть незаполненные клетки, и, кроме того, недетерминированным, поскольку в той же таблице есть клетки, содержащие пары состояний. Чтобы получить полностью определенный автомат, следует ввести дополнительное состояние Er (ошибка). Для этого нужно дополнить автомат соответствующей строкой с состоянием Er и во все пустые клетки таблицы переходов вписать это состояние Er (см. табл. 4). Таблица
4
Таблица переходов недетерминированного полностью определенного автомата x0 x2 x3 x4 x5 x6 x7 S Er Er Er Er S1,S3 F C 0 S1 Er Er Er Er Er S2 Er 0 S2 A Er Er Er Er Er Er 0 S3 Er Er Er Er Er S4 Er 0 S4 Er Er Er B Er Er Er 0 A Er D Er Er A1 Er Er 0 A1 Er Er Er Er Er Er Er 1 B Er E Er Er B1 Er Er 0 B1 Er Er Er Er Er Er Er 1 C Er E Er Er C1 Er Er 0 C1 Er Er Er Er Er Er Er 1 D Er S D1 Er Er Er Er 0 D1 Er Er Er Er Er Er Er 1 E Er S E1 Er Er Er Er 0 E1 Er Er Er Er Er Er Er 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||