Geum.ru

Синтез распознающего автомата

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

Министерство образования и науки РФ

ГОУ ВПО Ижевский государственный технический университет

Кафедра Программное обеспечение

 

 

 

 

 

 

 

 

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по дисциплине:

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

на тему:

Синтез распознающего автомата

 

 

 

 

Выполнил:

ст.гр. 4-78-11

Таишев Е.Э.

 

 

Ижевск 2012

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

1.Постановка задачи

2.Индивидуальное задание. Построение праволинейной

грамматики

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

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

5.Сведение недетерминированного конечного автомата к детерминированному

6.Построение минимального автомата

.Построение сети Петри, моделирующей работу распознающего автомата

.Описание программы, реализующей распознающий автомаТ

8.1 Вводная часть

8.2 Функциональное назначение

.3 Описание информации

.4 Описание логики

9Описание контрольного примера

9.1 Назначение

9.2 Исходные данные

.3Результаты расчета

.4 Результаты испытания программы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

ВВЕДЕНИЕ

 

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

В наше время, конечные автоматы имеют широкое распространение в компиляторах языков, поэтому программная реализация конечного автомата приобретает высокое значение. Также они применяются для создания лингвистических процессоров, для описания и обработки формальных языков.

Каждый автомат имеет конечное число входов, воспринимающих информацию, изображаемую конечным числом символов из некоторого алфавита, и конечное число выходов для выдачи информации.

Выходная информация автомата зависит не только от входной информации, но и от внутреннего состояния автомата. Конечный автомат имеет конечное число состояний.

Автоматы часто представляют сетями. Для автомата характерен последовательный способ функционирования: автомат последовательно переходит из состояния в состояние с заданной функцией перехода и осуществляет очередной шаг.

1.ПОСТАНОВКА ЗАДАЧИ

 

Необходимо построить праволинейную грамматику на основе индивидуального задания и приведенного ниже определения формальной грамматики. Затем по праволинейной грамматике построить автоматную грамматику. Построить недетерминированный конечный автомат по полученной автоматной грамматике. Преобразовать недетерминированный конечный автомат в детерминированный. Минимизировать полученный автомат, построить таблицу и граф переходов минимального автомата.

Построить по праволинейной грамматике сеть Петри. Минимизировать ее - построить недетерминированную сеть. Построить детерменированную сеть Петри на основе недетерминированной. По полученной детерминированной сети Петри построить граф переходов минимального автомата. Сравнить с графом минимального автомата, полученным ранее.

Входными данными для автомата является цепочка (строки, вводимые с клавиатуры) из терминальных символов. На выходе автомата выдается состояние - отвергающее или допускающее входную цепочку.

Задана формальная грамматика G = , где

Vt = {C1, C2,…, C18} - терминальный словарь,

Vn = {S, A, B, C, D, E, F}- нетерминальный словарь,

S - начальный символ грамматики, S Vn,

P - множество правил вывода

Правила вывода имеют следующий вид:

S C1 C2 C3 A; C1 C4 C5 B; C6 C; C7 F; C8 D; C9; C8 E; C9; C8 E; C9; C10 S; C11; C10 S; C11; C12 C13 C14 C15; C16 C13 C14 C15; C17 C18 C15.

2.ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ. ПОСТРОЕНИЕ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ

 

Индивидуальным задание для курсовой работы являются две таблицы (см. табл., 1,2) и правила вывода R. необходимо поставить в соответствие терминальным символам Ci грамматики G терминальные символы Xi грамматики G. Для этого во вторую строку таблицы 1 записываются первые 18 символов фамилии, имени и отчества с обязательными пробелами между ними. В третью строку необходимо занести для каждого из 18 символов строки символы из алфавита {X0, X1, X2, X3, X4, X5, X6, X7} в соответствии с таблицей 2.

 

Таблица 1. Индивидуальная таблица

CiC1C2C3C4C5C6C7C8C9C10C11C12C13C14C15C16C17C18S1ТАИШЕВ ЕВГЕНИЙ ЭДУXiX5X1X3X2X6X2X5X6X2X4X6X7X3X0X5X1X6 X7

Таблица 2. Таблица соответствия между буквами алфавита и терминальными символами грамматики G

АБВГДЕЖЗИЙКЛМНОПX1X5X2X4X6X6X4X3X3X0X7X0X3X7X4X5РСТУФХЦЧШЩЬЫЭЮЯX0X4X5X7X2X5X1X2X2X0X6X1X1X3X7X5

Правила вывода для G получаются из правил вывода грамматики G заменой символов Ci на соответствующие символы Xi. При этом праволинейная грамматика приводится к следующему виду:

G = , где

Vt= { X0, X2, X3, X4, X5, X6, X7} - терминальный словарь,

Vn= {S, A, B, C, D, E, F}- нетерминальный словарь,

S - начальный символ грамматики, S Vn,- множество правил вывода, получаемых из правил вывода R заменой символов Ci на Xi в соответствии с таблицей 1.

Получим следующие правила вывода праволинейной грамматики G:

  1. S x5 x1 x3 A
  2. S x5 x2 x6 B
  3. S x2 C
  4. S x5 F
  5. A x6 D
  6. A x2
  7. B x6 E
  8. B x2
  9. C x6 E
  10. C x2
  11. D x4 S
  12. D x6
  13. E x4 S
  14. E x6
  15. F x7 x3 x0 x5
  16. F x1 x3 x0 x5
  17. F x6 x7 x5

 

Граф полученн?/p>