Министерство образования и науки российской федерации
Федеральное агентство по образованию РФ
Государственное образовательное учреждение
высшего профессионального образования
"Ижевский государственный технический университет"
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к курсовой работе по дисциплине
«Теория языков программирования и методы трансляции»
Ижевск
Издательство ИжГТУ
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 |