Спасибо!
Информация о работе
Подробнее о работе
Построение автомата с магазинной памятью по контекстно-свободной грамматике Вариант 3 (на С#)
- 40 страниц
- 2018 год
- 86 просмотров
- 1 покупка
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Тема: «Построение автомата с магазинной памятью по контекстно-свободной грамматике»
Цель:
- закрепить понятия «автомат с магазинной памятью (МП-автомат)», «расширенный МП-автомат», «конфигурация МП-автомата»; «строка и язык, допускаемые МП-автоматом»;
- сформировать умения и навыки построения МП-автомата и расширенного МП-автомата по КС-грамматике, разбора входной строки с помощью МП-автомата.
Начальной конфигурацией МП-автомата является конфигурация
(q0, ω, N0).
Шаг работы МП-автомата будем представлять в виде отношения непосредственного следования конфигураций (обозначается «|=») и отношения достижимости конфигураций (обозначается «|=*»). Если одним из значений магазинной функции F(q ∈ Q,t ∈ (T ∪ {ε}),S ∈ N) является
(qʹ ∈ Q, γ ∈ N^*), то записывается (q,t ω,Sα) |=(qʹ, ω,γα). При этом возможны следующие варианты.
!!! В прикрепленном файле расширение doc поменять на zip !!!
на С#
Разработать программное средство, реализующее следующие функции:
а) ввод произвольной формальной грамматики и проверка ее на принадлежность к классу КС-грамматик;
б) построение МП-автомата по КС-грамматике;
в) построение расширенного МП-автомата по КС-грамматике;
Продемонстрировать разбор некоторой входной строки с помощью построенных автоматов для случая:
а) входная строка принадлежит языку исходной КС-грамматики и допускается МП-автоматом;
б) входная строка не принадлежит языку исходной КС-грамматики и не принимается МП-автоматом.
Вариант 3: КС-грамматика G=({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P:
1) S→R | T
2) R→pX | paR | paT | ε
3) T→Tg | g
4) X→aXb
5) Y→aYa | y
1 Ишакова Е.Н. Теория формальных языков, грамматик и автоматов: Методические указания к лабораторному практикуму. - Оренбург: ГОУ ОГУ, 2005. – 54 с.
2 Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты.: Пер. с англ. – М.: Изд. дом «Вильямс», 2001. – 768с.
3 Серебряков В.И. Лекции по конструированию компиляторов. – М.: МГУ, 1997. – 171с.
4 Братчиков И.Л. Синтаксис языков программирования / Под ред. С.С. Лаврова. – М.: Наука, 1975. - 262с.
5 Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под ред. А. Матросова. – СПб: Питер, 2002. – 688с.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
