В множестве Р правил грамматики G непродуктивным называют нетерминал, из которого нельзя получить цепочку терминалов. Для поиска в множестве правил непродуктивных нетерминалов используется следующее свойство.
Свойство А: Если все символы правой части правила продуктивны, то продуктивен и символ, стоящий в его левой части.
Алгоритм поиска непродуктивных нетерминалов в множестве правил P грамматики G:
– составить список нетерминалов для которых найдется хотя бы одно правило, правая часть которого состоит только из терминалов;
– если найдется такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал стоящий в его левой части;
– если на предыдущем шаге список не пополняется, то получен исчерпывающий список всех продуктивных нетерминалов.
Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются непродуктивными и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.
В множестве правил грамматики недостижимым называют нетерминал, который не участвует в процессе вывода. цепочек. Для поиска недостижимых нетерминалов используется следующее свойство.
Свойство Б: Если нетерминал в левой части правила является достижимым, то достижимы все нетерминалы, стоящие в правой части этого правила.
Алгоритм поиска недостижимых нетерминалов в множестве правил P грамматики G:
– образовать одноэлементный список из начального нетерминала грамматики;
– если в множестве Р найдено правило, левая часть которого уже в списке, то включить в список все нетерминалы из его правой части;
– если на предыдущем шаге список не пополняется, то получен исчерпывающий список всех достижимых нетерминалов.
Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются недостижимыми и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.
Не нарушая эквивалентности, можно также исключить правила такого вида: A - A или A - B, B - C, C - A (циклический блок правил).
1.2.5 Построение грамматик для заданного КА
Любое регулярное множество, которое распознается КА, можно описать с помощью автоматной грамматики. Алгоритм построения грамматики следующий:
– Начальное состояние КА - начальный символ грамматики.
– Алфавит КА (без символа конец цепочки–"┤") - терминальные символы грамматики.
– Множество состояний КА - нетерминальные символы грамматики.
– Если в таблице переходов КА есть переход из состояния А в состояние В при воздействии входного символа х – ввести правило следующего вида: А - xB.
– Если D– допускающее состояние КА, то ввести правило следующего вида: D-*,где *– пустая цепочка(для отвергающих состояний правил нет).
– Закончить составление правил, когда будут обработаны все непустые клетки управляющей таблицы ("0" – пустая клетка).
– Удобный, легкий в обращении интерфейс.
– В программе необходимо предусмотреть неквалифицированные действия пользователя.
– К программе должна прилагаться специально разработанная справочная система.
– Программа должна работать в разных операционных системах.
– Надёжность работы программы.
Представленный мною ПП является наглядным пособием для всех желающих изучить такую тему дискретной математики, как «Построение грамматики для заданного пользователем конечного автомата».
Программа написана в среде программирования Delphi 7.0 под Windows.
Delphi - это комбинация нескольких важнейших технологий:
–Высокопроизводительный компилятор в машинный код
– Объектно-ориентированная модель компонент
– Визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов
– Масштабируемые средства для построения баз данных
Компилятор в машинный код. Компилятор, встроенный в Delphi, обеспечивает высокую производительность, необходимую для построения приложений в архитектуре “клиент-сервер”. Этот компилятор в настоящее время является самым быстрым в мире, его скорость компиляции составляет свыше 120 тысяч строк в минуту на компьютере 486DX33. Он предлагает легкость разработки и быстрое время проверки готового программного блока, характерного для языков четвертого поколения (4GL) и в то же время обеспечивает качество кода, характерного для компилятора 3GL. Кроме того, Delphi обеспечивает быструю разработку без необходимости писать вставки на Си или ручного написания кода (хотя это возможно).
В процессе построения приложения разработчик выбирает из палитры компонент готовые компоненты как художник, делающий крупные мазки кистью. Еще до компиляции он видит результаты своей работы - после подключения к источнику данных их можно видеть отображенными на форме, можно перемещаться по данным, представлять их в том или ином виде. В этом смысле проектирование в Delphi мало чем отличается от проектирования в интерпретирующей среде, однако после выполнения компиляции мы получаем код, который исполняется в 10-20 раз быстрее, чем то же самое, сделанное при помощи интерпретатора. Кроме того, компилятор компилятору рознь, в Delphi компиляция производится непосредственно в родной машинный код, в то время как существуют компиляторы, превращающие программу в так называемый p-код, который затем интерпретируется виртуальной p-машиной. Это не может не сказаться на фактическом быстродействии готового приложения.
Объектно-ориентированная модель программных компонент. Основной упор этой модели в Delphi делается на максимальном реиспользовании кода. Это позволяет разработчикам строить приложения весьма быстро из заранее подготовленных объектов, а также дает им возможность создавать свои собственные объекты для среды Delphi. Никаких ограничений по типам объектов, которые могут создавать разработчики, не существует. Действительно, все в Delphi написано на нем же, поэтому разработчики имеют доступ к тем же объектам и инструментам, которые использовались для создания среды разработки. В результате нет никакой разницы между объектами, поставляемыми Borland или третьими фирмами, и объектами, которые вы можете создать. В стандартную поставку Delphi входят основные объекты, которые образуют удачно подобранную иерархию из 270 базовых классов.
Рисунок 2 – Структура разрабатываемого программного продукта
Рассматриваемая структура изображена на рисунке 2.
2.5 Блок-схема
да
Рисунок 3 – Функциональная схема программного продукта
2.6 Работа с ПП, справочной системой
Справочная система представлена в виде Web-страницы, что вызывается gри нажатии F7. Ссылка на адрес её расположения указана в листинге программы: WinExec('C:\Program Files\Internet Explorer\Iexplore.exe F:\Моя курсовая работа\Моя Web-страница\Справка.mht',1);
Запустите Primer4. Всплывает окно (рисунок 4):
Рисунок 4 – Главная форма
Вводим состояния и алфавит (рисунок 5):
Рисунок 5 – Главная форма с заполненными строками
Нажимаем на кнопку «Конечный Автомат». Заполняем управляющую таблицу. Проверим конечный автомат (рисунок 6):
Таблица 1 – Компоненты программы
Имя компонента в модуле | Назначение компонента | События компонента | Назначение обработчиков событий | Примечания |
MainMenu | Самая главная форма, где расположены все компоненты | |||
BitBtn1 | Кнопка для создания конечного автомата | OnClick | Создание управляющей таблицы. | |
BitBtn2 | Кнопка выхода | OnClick | Закрытие программы. | |
BitBtn3 | Кнопка для создания граматики. | OnClick | Создания првил грмматики. | |
BitBtn4 | Кнопка для вызова правил ввода. | OnClick | Открывается форма с правилами ввода. | |
BitBtn5 | Кнопка проверки конечного автомата. | OnClick | Проверка конечного автомата на недостижимые символы. | |
BitBtn6 | Кнопка очистки поля | OnClick | Очищает поле, где расположены правила найденной грамматики. | |
BitBtn7 | Кнопка вызова справки о программном продукте. | OnClick | ||
Edit | Cтрока для ввода символов состояния и алфавита. | Ввод символов состоянии и алфавита конечного автомата. | ||
StringGrid | Компонент для управляющей таблицы | |||
ListBox | Поле для правил грамматики |
В таком случае, невозможно построить грамматику. Строим конечный автомат, в котором все состояния достижимы. И только тогда строим грамматику. В таблице 1 предоставлена информация о компонентах программы.