Построение и преобразование грамматик

Задание на курсовое проектирование

Введение

ГЕОТЕХНИКА I

Сагыбекова Акмарал Оразбековна

Виталий Анатольевич Хомяков

Сергазы Оспанович Оспанов

Сводный план 2008-2009 уч.года, поз.№

Формат 60х84 1/16. Бумага типографская. Ризограф.

Усл.печ.л. Уч.-изд. Л. Тираж Экз.

Заказ №

Цена договорная.

Издание Казахской головной

архитектурно-строительной академии

Издательский дом «Строительство и архитектура»

050043,г. Алматы, ул. Рыскулбекова, 28.

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

Основой изучения данного раздела теории является

· построение базовых формальных моделей описания логических структур, динамики поведения вычислительных структур;

· выработка навыков проектирования вычислительных систем;

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

1. Построение право-линейной грамматики по полученным данным.

2. Переход от право-линейной грамматики к автоматной. Результат -

Право-линейная и автоматная грамматики.

3. Построение недетерминированного распознающего автомата.

4. Результат - таблица переходов и граф переходов автомата.

5. Переход от недетерминированного автомата к полностью опреде-

ленному детерминированному автомату. Результат - таблица перехо-

дов и граф переходов автомата, проверка эквивалентности автоматов.

6. Минимизация автомата. Построение таблиц переходов на основе

эквивалентных преобразований. Построение разбиения множества

состояний на классы эквивалентности. Результат - таблица переходов

и граф переходов минимального автомата.

7. Выполнение предыдущего этапа с использованием сети Петри. Результат - сеть Петри, соответствующая автоматной грамматике, и минимальная сеть Петри. Сравнение полученной минимальной сети с таблицей переходов минимального автомата.

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

9. Построение комбинационной схемы автомата.

Для синтеза конечного автомата задана формальная грамматика

G = < V, W, S, R >,

где V = {c1, c2,..., c18} - словарь терминальных символов;

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

S - начальный символ грамматики; R - множество правил вывода:

S ® c1 c2 c3 A С ® c8 E

S ® c1 c4 c5 B C ® c9

S ® c6 C D ® c10 S

S ® c7 F D ® c11

A ® c8 D E ® c10 S

A ® c9 E ® c11

B ® c8 E F ® c12 c13 c14 c15

B ® c9 F ® c10 c13 c14 c15

F ® c17 c18 c15

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

Для выполнения индивидуальной работы требуется перейти к новому терминальному словарю, используя табл. 1 и 2.

Таблица 1

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

x1

x5

x2

x4

x6

x6

x4

x3

x3

x0

x7

x0

x3

x7

x4

x5

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Э

Ю

Я

x0

x4

x5

x7

x2

x5

x4

x2

x2

x0

x6

x1

x1

x3

x7

x5

Таблица 2

c1

c2

c3

c4

c5

c6

c7

c8

c9

c10

c11

c12

c13

c14

c15

c16

c17

c18

д

о

с

о

в

я

р

о

с

л

а

в

а

л

е

к

x6

x4

x4

x6

X2

x5

x7

x0

x4

x4

x0

X1

x2

x5

X1

X0

X6

X7

На основе использования табл.1 и 2 составляется грамматика индивидуальная для конкретного студента. Например,

1. S ® x6 x4 x4 A 9. C ® x0 E

2. S ® x6 x6 x2 B 10. C ® x4

3. S ® x5 C 11. D ® x4 S

4. S ® x7 F 12. D ® x0

5. A ® x0 D 13. E ® x4 S

6. A ® x4 14. E ® x0

7. B ® x0 E 15. F ® x1 x2 x5 x1

8. B ® x4 16. F ® x4 x2 x5 x1

17. F ® x6 x7 x1.

Грамматика называется праволинейной, если правая часть каждого правила содержит не более одного нетерминала, причем этот нетерминал является самым правым символом.

Грамматика называется автоматной, если ее правила имеют вид:

A ® x B; A ® x, где x Î V, В Î W.

Для сведения праволинейной грамматики к автоматной используют следующий прием (в качестве примера возьмем одно из правил приведенной выше грамматики, а именно, правило S -> x7 x0 x1 A). Перепишем левую часть правила и первый слева символ правой части, а оставшуюся от правой части цепочку обозначим новым нетерминальным символом, который дополнительно будет вводиться в грамматику, например, S1. В результате получим следующее новое правило:

S ® x7 S1; S1 ® x0 x1 A.

Затем, аналогичным способом преобразуем правило для S1 (получим правила вида S1 ® x0 S2 и S2 ® x1 A). Правило S2 не требует дальнейших преобразований, так как оно удовлетворяет требованиям правил автоматной грамматики.

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

Продолжим пример. Из праволинейной грамматики, записанной выше, получаем автоматную грамматику G’ с правилами вывода вида:

1. S ® x6 S1 16. D ® x0

2. S1® x4 S2 17. E ® x4 S

3. S2® x4 A 18. E ® x0

4. S ® x6 S3 19. F ® x1 S5

5. S3® x6 S4 20. S5®x2 S6

6. S4®x2 B 21. S6® x5 S7

7. S ® x5 C 22. S7® x1

8. S ® x7 F 23. F®x4 S6

9. A ® x0 D 24. F ® x6 S8

10. А ® x4 25. S8 ® x7 S7.

11. B ® x0E

12. B ® x4

13. C ® x0 E

14. C ® x4

15. D ® x4 S

Дата добавления: 2014-12-07