Конечные автоматы - распознаватели - раздел Математика, Основы ДИСКРЕТНОЙ МАТЕМАТИКИ
Конечный Автомат(В Дальнейшем Ка) - Абстрактное Вычислительно...
Конечный автомат(в дальнейшем КА) - абстрактное вычислительное устройство с фиксированным и конечным объемом памяти, которое на входе читает цепочки(последовательности символов некоторого алфавита), а на выходе сообщает об их принадлежности к некоторому множеству, для распознания которого он построен.
Принцип работы конечных автоматов различных уровней широко применяется в вычислительных устройствах, как на аппаратном так и на программном уровнях: это компиляторы, трансляторы программ, различные кодировщики, антивирусные программы и т.п. В принципе работу любой программы можно представить как работу цепочки конечных автоматов различной сложности. Рассмотрим построение простейших КА - распознавателей.
В процессе построения такого конечного автомата должны быть определены следующие параметры:
а) входной алфавит V конечного автомата (конечное множество входных символов);
б) конечное множество состояний S;
в) начальное состояние КА - Sнач (состояние, с которого начинает
работу КА при обработке новой цепочки);
г) множество допускающих состояний - Sдоп (подмножество множества состояний S, с которым сравнивается достигнутое КА состояние после прихода символа "конец цепочки");
д) таблица переходов (управляющая таблица), которая паре текущее состояние - входной символ ставит в соответствие новое состояние).
Примечания:
1.В множество входных символов V обязательно включают особый символ "конец цепочки", который сообщает КА о том, что нужно достигнутое состояние сравнить с множеством Sдоп и, если оно приналежит этому множеству, пропустить цепочку; в противном случае цепочка отвергается. В тексте этот символ будет иметь вид -+.
2.Часто при распознании цепочек возникает ситуация, когда невозможно поставить текущей паре состояние-входной символ новое состояние. По сути это означает, что распознаваемая цепочка не принадлежит распознаваемому множеству, хотя она и не просмотрена до символа "конец цепочки". Такие ситуации в таблице переходов помечаются символом "Е" ("error"); попав в такое состояние КА отвергает текущую цепочку и переходит в начальное состояние. В конкретных программных реализациях может вызываться обработчик ошибок, выдаваться сообщение о характере ошибки и т.п.
Начинает работать КА из начального состояния. Символы распознаваемой цепочки поступают посимвольно, начиная с первого и изменяют состояния в соответствии с таблицей переходов. После поступления символа "конец цепочки", достигнутое состояние автомата фиксируется и сравнивается с множеством допускающих состояний. На основании этого сравнения цепочка допускается или отвергается. По сути КА работает как фильтр, который пропускает "правильные" цепочки. Другая трактовка КА - компактный алгоритм распознания регулярных, в том числе и бесконечных множеств, который строит программист перед началом кодирования (реализацией алгоритма на конкретном языке).
Построение КА для распознания заданного множества цепочек - процесс творческий и неоднозначный. Теоретически для распознания одного и того же множества цепочек можно построить бесконечное множество КА. Описанный выше принцип распознания применим далеко не ко всякому регулярному множеству.
МЕЖДУНАРОДНОГО НАУЧНО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Конечные автоматы - распознаватели
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Условные обозначения, принятые в конспекте лекций
N - множество всех натуральных чисел (N = {1,2,3,...});
Nо - множество всех натуральных чисел и ноль (Nо={0,1,2,3,...});
ї - знак принадлежности (" а ї А &quo
Действия с цепочками
Для цепочек допустимы следующие действия
а) конкатенация (сцепление) цепочек:
x = aba, y = cab; xy = abacab;
б) возведение цепочек в степень:
x=ab; (х)^1 = ab; (
Число элементов множества
Для любого конечного множества М, число элементов (мощность множества) будем обозначать n(M).
Пусть задано несколько множеств (подмножеств универсального множества): А,В,С,
Свойства бинарных отношений
Симметричность.
Отношение R называется симметричным, если для любого элемента этого отношения (х,y) в множестве R есть соответствующая пара (y,x). Другими словами, есл
Простые высказывания; логические связки
Простые высказывания будем обозначать p, q, r, ...Основное свойство простого высказывания: высказывание может быть или ложно(False, 0, "Hет") или истинно(True,1, "Да&
Составные высказывания; таблицы истинности
Используя простые высказывания, логические связки(операции) и скобки, которые меняют порядок выполнения действий, можно строить составные высказывания (наибольший приоритет при выпо
Логические законы
Пример 2 Построить таблицу истинности для В = ~(p -> q) / q.
Таблица истинности
----T---T----T--------T----------¬
¦ p ¦ q ¦p->q¦~(p
Отношения между высказываниями
Как было сказано выше, высказывание (простое или составное) полностью характеризуется таблицей истинности (число строк в этой таблице определяется по формуле 2^n, где n - количество
Аргументы
Под аргументом будем понимать утверждение того, что некоторое высказывание (заключение) следует из других высказываний (посылок).
Одной из задач логики является проверка пр
Общие понятия и определения
Граф G как математический объект - это совокупность двух множеств: непустого множества вершин V и множества ребер E, элементы которого представляет собой неупорядоченные (для ориент
Элементы графов
Граф без кратных ребер называют полным, если каждая пара вер-
шин соединена ребром.
Граф H называют частью графа G, если множество вершин графа H
принадле
Диаметр, радиус и центр графа
Задан единичный связный неориентированный граф G.
Минимальная длина простой цепи с началом V' и концом V" называется расстоянием между этими вершинами d(V',V").
Параметры протяженности (диаметр, радиус и центр) графа
Задан единичный связный неориентированный граф G. Максимальная длина простой цепи с началом V' и концом V" называется протяженностью между этими вершинами g(V',V").
Эквивалентность состояний КА
Два состояния конечного автомата эквивалентны тогда и только тогда, когда, начав работу из этих состояний, конечный автомат будет допускать одни и те же цепочки. Другими словами, ес
Недостижимые состояния
Недостижимыми называются такие состояния КА, которые не могут быть достигнуты из начального состояния воздействием любых входных символов. Такие состояния исключаются из таблицы пер
Недетерминированный конечный автомат
Недетерминированный конечный автомат (в дальнейшем НКА) представляет собой обычный КА с той разницей, что в таблице переходов паре входной символ - состояние ставится в соответствие
Автоматы-распознаватели с магазинной памятью
Далеко не для всех регулярных множеств можно построить КА-распознаватель, так как КА не имеет возможности сосчитать и запомнить количество символов обрабатываемой цепочки. Для этой цели используетс
Автоматы-трансляторы с магазинной памятью
В ряде случаев при обработке регулярного множества кроме распознания необходимо его преобразование в другое множество.
Такие действия может выполнять МП-транслятор, на выхо
Задачи на построение МП-распознавателей.
Таблица 1
г========T=============================================¬
¦ N п/п ¦ Построить МП-распознаватель для следующих ¦
¦ ¦ регулярных множеств ¦
¦--------+----
Задачи на построение МП-трансляторов
Таблица 2
г=========T=============================================¬
¦ N п/п ¦ Построить МП-транслятор, который преобразует¦
¦ ¦ цепочку А в цепочку В. ¦
¦-------
Эквивалентные преобразования КС-грамматик
Для построения распознавателей грамматик, других целей очень часто необходимо преобразовать правила исходной грамматики к соответствующему виду. При этих преобразованиях язык, порож
Достижимых) нетерминалов
В множестве Р правил грамматики G непродуктивным называют нетерминал из которого нельзя получить цепочку терминалов. Для поиска в множестве правил непродуктивных нетерминалов исполь
Изменение направления рекурсии
Для построения распознавателей в правилах грамматики не должно быть левосторонней рекурсии, т.е. правил вида A -> Ax. Пусть в исходной грамматике есть следующее правило: A ->
Построение КА для распознания автоматных грамматик
Любое регулярное множество, которое распознается КА, можно описать с помощью автоматной грамматики. Алгоритм построения грамматики следующий:
1.Начальный символ грамматики
Построение КА-распознавателей для праволинейных грамматик
Праволинейной называется контекстно-свободная грамматика, вправых частях правил которой имеется не более одного нетерминала и этот нетерминал заканчивает правило. В праволинейных грамматиках допуск
Построение МП-распознавателей для q-грамматик
КС-грамматика (грамматика второго типа) называется q-граммаикой, если правые части всех правил этой грамматики начинаются стерминальных символов и для правил с одинаковыми левыми ча
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов