Навигация
Теоретические и практические основы разрабатываемой темы
36295
знаков
1
таблица
7
изображений
1 Теоретические и практические основы разрабатываемой темы
1.1 Теория конечных автоматов
Конечный автомат(в дальнейшем КА) - абстрактное вычислительное устройство с фиксированным и конечным объемом памяти, которое на входе читает цепочки(последовательности символов некоторого алфавита), а на выходе сообщает об их принадлежности к некоторому множеству, для распознания которого он построен.
По сути КА работает как фильтр, который пропускает "правильные" цепочки. Другая трактовка КА - компактный алгоритм распознания регулярных, в том числе и бесконечных множеств, который строит программист перед началом кодирования (реализацией алгоритма на конкретном языке).
Далеко не для всех регулярных множеств можно построить
КА-распознаватель, так как КА не имеет возможности сосчитать и запомнить количество символов обрабатываемой цепочки. Для этой цели используется специальное устройство - магазин, в который можно помещать символы или удалять их, запоминая или сравнивая количество символов входной цепочки. Такой автомат называется автоматом распознавателем с магазинной памятью (сокращенно – МП-распознавателем).
Но в ряде случаев при обработке регулярного множества необходимо его преобразование в другое множество. Такие действия может выполнять МП-транслятор, на выходе которого будет формироваться выходная цепочка.
МП-транслятор задается :
1.Конечным множеством входных символов (включая символ конца цепочки "¶").
2.Конечным множеством выходных символов.
3.Конечным множеством магазинных символов (включая маркер дна магазина - '¤').
4.Конечным множеством состояний.
5.Упpавляющей таблицей, котоpая каждой комбинации трех параметров: входной символ, магазинный символ(верхний символ магазина), состояние - ставит в соответствие четыре параметра: действие с магазином, входным символом, состоянием и выходным символом.
5.Hачальной конфигурацией (начальное состояние и начальное содеpжимое магазина).
6.Множеством допускающих конфигураций (комбинаций - состояние МП-транслятора и верхний символ магазина в момент, когда приходит символ "конец цепочки").
Допускаемые операции над входом:
1.Держать входной символ (Д).
2.Перейти к очередному символу (П).
Примечание: запрещено запрашивать входной символ после прихода символа "¶"("конец цепочки").
Допускаемые операции над магазином
1.Втолкнуть в магазин магазинный символ, к примеру А (Вт.А).
2.Вытолкнуть из магазина верхний символ, к примеру А (Выт.А).
3.Оставить магазин без изменений (О).
Ряд ячеек управляющей таблицы может без деления на поля заполняться символом Е (состояние ошибки). Если МП-транслятор попал в такое состояние, то обработка цепочки прекращается и такая цепочка отвергается.
Результатом работы для МП-транслятора будет сообщение "допустить" или "отвергнуть" и цепочка получаемая на выходе. Входная цепочка допускается МП-транслятором , если под воздействием этой цепочки автомат, начавший работу в начальной конфигурации ( в начальном состоянии и с начальным содержимым магазина) приходит к допускающей конфигурации после поступления символа "конец цепочки", иначе цепочка отвергается.
Рассмотрим строение ячейки в таблице переходов МП-транслятора.
Рис. 1 – вид ячейки МП-транслятора
Построение МП-транслятора для распознания заданного множества цепочек - процесс творческий и неоднозначный. Теоретически для распознания одного и того же множества цепочек можно построить бесконечное множество КА. Описанный выше принцип распознания применим далеко не ко всякому регулярному множеству.
1.2 Области прикладного применения теории конечных автоматов
Принцип работы конечных автоматов различных уровней широко применяется в вычислительных устройствах, как на аппаратном, так и на программном уровнях: это компиляторы, трансляторы программ, различные кодировщики, антивирусные программы и т.п. В принципе работу любой программы можно представить как работу цепочки конечных автоматов различной сложности.
2 Разработка программного продукта
2.1 Современные требования к программным продуктам
К современным программным продуктам (далее ПП) предъявляется ряд требований. Современные ПП должны обладать дружественным интерфейсом, позволяющим пользователю просто работать с приложением, а не теряться в догадках о назначении той или иной кнопки или другого элемента управления. В идеале приложение должно очень корректно и последовательно “проводить” пользователя от этапа ввода данных до получения конкретного результата. Приложение должно обладать развитой системой поддержки пользователя, а именно справочной подсистемой, грамотно изложенным руководством пользователя и так далее. Для обеспечения этих и других требований используется стандартизованный интуитивно понятный интерфейс, принятый во многих графических операционных системах, что позволяет пользователю начинать работу с приложением не с изучения назначений его элементов управления, а непосредственно с изучения предметной области, в которой функционирует приложение, с тем, чтобы сразу после этого приступить к работе с приложением.
Похожие работы
... позволяет связывать твёрдотельные модели, сборки или чертежи, созданные с помощью SolidWorks 97, с файлами других приложений, что значительно расширяет возможности автоматизации процесса проектирования. С помощью технологии OLE можно использовать информацию, полученную в других приложениях Windows, для управления моделями и чертежами SolidWorks. Например, размеры модели могут быть рассчитаны в ...
... 2.2 Понятия языка Лисп ________________________________ 2.2.1 Атомы и списки _____________________________ 2.2.2 Внутреннее представление списка _____________ 2.2.3 Написание программы на Лиспе _______________ 2.2.4 Определение функций _______________________ 2.2.5 Рекурсия и итерация _________________________ 2.2.6 Функции интерпретации выражений ____________ 2.2.7 Макросредства ...
... оптимальные варианты оснащения офиса коммерческой компании комплектом оборудования, достаточным для решения поставленной задачи Глава 1. 1.1 Постановка задачи. Целью данного дипломного проекта является разработка системы управления работой коммерческой компании. Исходя из современных требований, предъявляемых к качеству работы управленческого звена коммерческой компании, нельзя не отметить, что ...
... 2Локальные вычислительные системы представляют собой совокуп- 2ность технических и программных средств в ограниченном пространс- 2тве в единую автоматизированную информационную сеть, функциониру- 2ющую с высокой производительностью на основе использования высо- 2коскоростных каналов связи. Обычно локальные сети охватывают несколько рядом стоящих зданий. Наиболее яркое воплощение ...
0 комментариев