Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции» icon

Методические указания к курсовой работе по дисциплине «Теория языков программирования и методы трансляции»


Смотрите также:
Методические указания по выполнению лабораторных работ по дисциплине "Теория языков...
Методические указания к курсовой работе по дисциплине «численные методы»...
Методические указания к курсовой работе по дисциплине «численные методы»...
«Теория языков программирования и методы трансляции»...
Учебно-методический комплекс по языки программирования и методы трансляции наименование...
Методические указания к курсовому проекту по дисциплине «Технологии программирования»...
Методические указания по курсовой работе для студентов специальности 22...
Методические указания к курсовой работе по дисциплине «Радиотехнические сигналы и цепи»...
Методические указания и задания для выполнения курсовой работы по дисциплине : "основы...
Методические указания и варианты заданий для курсовой работы по курсу «Экономическая Теория»...
Методические указания по написанию курсовой работы по дисциплине «Теория менеджмента»...
Методические указания и задания к курсовой работе по дисциплине «Бухгалтерский (финансовый)...



Загрузка...
страницы:   1   2   3   4
скачать


Министерство образования и науки российской федерации

Федеральное агентство по образованию РФ


Государственное образовательное учреждение
высшего профессионального образования

"Ижевский государственный технический университет"


МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к курсовой работе по дисциплине

«Теория языков программирования и методы трансляции»


Ижевск

Издательство ИжГТУ

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. ТЕМА, ЦЕЛЬ И СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ



Тема курсовой работы: Синтез распознающего автомата.

Цель курсовой работы состоит в изучении способов задания языков грамматиками, распознающими автоматами и сетями Петри, построении модели конечного автомата, распознающего заданный язык, и его программной реализации.

Содержание и основные этапы работы:

  1. построение праволинейной грамматики;

  2. построение автоматной грамматики по праволинейной;

  3. построение недетерминированного конечного автомата;

  4. сведение недетерминированного конечного автомата к детерминированному;

  5. построение минимального автомата;

  6. выполнение этапов 2-5 с использованием аппарата сетей Петри;

  7. программная реализация автомата.



^

2. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ



Исходными данными для курсовой работы являются две таблицы – табл. 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={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={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.





оставить комментарий
страница1/4
М. А. Сенилов
Дата02.10.2011
Размер0,65 Mb.
ТипМетодические указания, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4
отлично
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх