КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Построение и преобразование грамматикЗадание на курсовое проектирование Введение ГЕОТЕХНИКА 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
Таблица 2
На основе использования табл.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; Просмотров: 641; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |