Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции»
| скачать Министерство образования и науки российской федерации Федеральное агентство по образованию РФ Государственное образовательное учреждение высшего профессионального образования "Ижевский государственный технический университет" МЕТОДИЧЕСКИЕ УКАЗАНИЯ к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» Ижевск Издательство ИжГТУ 2008 УДК 62-50 (076.5) Составитель: д-р техн. наук проф. М. А. Сенилов Рецензент: д-р техн. наук, проф. А. И. Мурынов Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» / Сост. М. А. Сенилов. – Ижевск: Изд-во ИжГТУ, 2008. – 28 с. Методические указания освещают основные вопросы выполнения курсовой работы по дисциплине «Теория языков программирования и методы трансляции», включающей тематику теории автоматов, теории формальных грамматик и языков. В них дается индивидуальное задание, а также приводятся рекомендации и сведения, необходимые для выполнения курсовой работы. Методические указания предназначены для студентов направления 230100 – «Информатика и вычислительная техника» и специальности 230105 – «Программное обеспечение вычислительной техники и автоматизированных систем». © Сенилов М. А. составление, 2008 © Издательство Ижевского государственного технического университета ОГЛАВЛЕНИЕ 1. ТЕМА, ЦЕЛЬ И СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ 4 2. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ 4 3. ПЕРЕХОД ОТ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ К АВТОМАТНОЙ 7 4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА 7 5. СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ 11 6. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА 16 7. ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ ПРИ ПЕРЕХОДЕ ОТ ГРАММАТИКИ К МИНИМАЛЬНОМУ АВТОМАТУ 20 8. ПОРЯДОК ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ 25 9. РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ 26 СПИСОК ЛИТЕРАТУРЫ 28 ^ Тема курсовой работы: Синтез распознающего автомата. Цель курсовой работы состоит в изучении способов задания языков грамматиками, распознающими автоматами и сетями Петри, построении модели конечного автомата, распознающего заданный язык, и его программной реализации. Содержание и основные этапы работы:
^ Исходными данными для курсовой работы являются две таблицы – табл. 1 и табл. 2 – и правила вывода R, приведенные ниже. В табл. 1 первоначально записана лишь первая строка, содержащая перечисление 18 символов сi. Во вторую строку si записываются первые 18 символов фамилии, имени и отчества студента с обязательными пробелами между фамилией и именем, именем и отчеством. Затем в третью строку студент заносит для каждого из 18 символов строки символ из алфавита {x0, x1, x2, x3, x4, x5, x6 ,x7} в соответствии с табл. 2. Таблица 1
Таблица 2 построена на основе подсчета появлений каждой буквы русского алфавита в фамилиях, именах и отчествах контингента студентов. Затем буквы были сформированы в восемь групп с таким расчетом, чтобы появление каждого из символов x0 – x7 было равновероятным. Таблица 2
Наконец, задана формальная грамматика: G= Sc1 c2 c3 A; Sc1 c4 c5 B; Sc6 C; Sc7 F; Ac8 D; Ac9; Bc8 E; Bc9; Cc8E; Cc9; Dc10 S; Dc11; Ec10 S; Ec11; Fc12 c13 c14 c15; Fc16 c13 c14 c15; Fc17 c18 c15. Эта грамматика, являющаяся праволинейной, приводится к виду G'= R' – множество правил вывода, получаемых из заданных заменой символов из алфавита Vt символами из алфавита V't в соответствии с таблицей 1. В данном примере они имеют вид: Sx5 x6 x0 A | x5 x6 x4 B | x7 C | x6 F; Ax2 D | x5; Bx2 E | x5; Cx2 E | x5; Dx2 S | x3; Ex2 S | x3; Fx7 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.
|
отлично
1 