рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Автоматы-распознаватели с магазинной памятью

Реферат Курсовая Конспект

Выберите учебное заведение

Автоматы-распознаватели с магазинной памятью

Автоматы-распознаватели с магазинной памятью - раздел Математика, Основы ДИСКРЕТНОЙ МАТЕМАТИКИ Далеко Не Для Всех Регулярных Множеств Можно Построить Ка-Распознаватель, Так...

Далеко не для всех регулярных множеств можно построить КА-распознаватель, так как КА не имеет возможности сосчитать и запомнить количество символов обрабатываемой цепочки. Для этой цели используется специальное устройство - магазин, в который можно помещать символы или удалять их, запоминая или сравнивая количество символов входной цепочки. Такой автомат называется автоматом-распознавателем с магазинной памятью (сокращенно - МП-автоматом).

МП-автомат задается :

1.Конечным множеством входных символов (включая символ конца цепочки "-+").

2.Конечным множеством магазинных символов (включая маркер

дна магазина - /).

3.Конечным множеством состояний.

4.Упpавляющей таблицей, котоpая каждой комбинации: входной символ, магазинный символ(верхний символ магазина), состояние - ставит в соответствие действие с магазином, входным символом, и состоянием.

5.Hачальной конфигурацией (начальное состояние и начальное содеpжимое магазина).

6.Множеством допускающих конфигураций (комбинаций - состояние МП-автомата и верхний символ магазина в момент, когда приходит символ "конец цепочки").

Допускаемые операции над входом

1.Держать входной символ (Д).

2.Перейти к очередному символу (П).

Примечание: запрещено запрашивать входной символ после прихода

символа -+ ("конец цепочки").

Допускаемые операции над магазином

1.Втолкнуть в магазин магазинный символ, к примеру А (Вт.А).

2.Вытолкнуть из магазина верхний символ, к примеру А (Выт.А).

3.Оставить магазин без изменений (О).

Примечания: а) запрещено выталкивание символа дна магазина /;

б) допускается действие с несколькими символами

(верхним в магазине и следующих за ним);

в) в ряде случаев допускается действие "Заменить",

т.е. верхний символ магазина заменяется некоторой цепочкой. Например "Зам Аав" означает, что верхний символ магазина заменяется на цепочку Аав. Для определенности при записи содержимого магазина будем полагать, что символ дна / занимает самое левое положение. Магазин до операции "Зам Аав" ВВА/; после - АавВА/.

Результатом работы для МП-pаспознавателя будет сообщение"допустить" или "отвеpгнуть". Входная цепочка допускается МП-pаспознавателем , если под воздействием этой цепочки автомат, начавший pаботу в начальной конфигурации ( в начальном состоянии и с начальным содеpжимым магазина) приходит к допускающей конфигурации после поступления символа "конец цепочки", иначе цепочка отвеpгается.

Рассмотрим строение ячейки в таблице переходов МП-распознавателя.

--- Операции с магазином

---+-----¬

¦ Вт. /¦

Состояния ----+ Выт./П+--- Операции над входом

¦Si / Д¦

L---/----

"Вт."- втолкнуть в магазин символ

"Выт."- вытолкнуть из магазина верхний символ

"0"- оставить магазин без изменения

"П"-переход к следующему символу входной цепочки

"Д"- держать текущий символ входной цепочки

"Si"- перейти в состояние

Ряд ячеек управляющей таблицы может без деления на поля заполняться символом Е (состояние ошибки). Если МП-распознаватель попал в такое состояние, то обработка цепочки прекращается и такая цепочка отвергается.

Пример: Постpоить МП-pаспознаватель для pаспознания множеств следующего вида : {0(n) 1(n) ¦ n>0}.

Построим стратегию работы МП-автомат для распознания задан

1.Первыми МП-автомат ожидает прихода серии "0".

2.Поступление каждого "0" сопровождается вталкиванием в магазин символа А для того, чтобы запомнить их количество и сравнить потом с количеством "1".

3.После поступления первой "1" ,нули не должны поступать.

4.Поступление "1" сопровождается выталкиванием из магазина А.Таким образом контролируется равенство количества "0" и "1".Цепочка до-

пускается , если при поступлении "-+" магазин будет пустым.

Зададим МП-автомат:

1. Множество входных символов {0,1,-+};

2. Множество магазинных символов {/,А};

3. Множество состояний {S1,S2}.

4. Hачальная конфигурация - состояние S1, магазин пуст.

Таблица переходов имеет вид (Е-состояние ошибки):

----------T---------T---T-----¬

¦ 0 ¦ 1 ¦ -+ ¦

-------T------+---------+---------+---------+

¦ ¦ ¦ Вт. А /¦ ¦ ¦

¦ ¦ / ¦ / ¦ Е ¦ Отв. ¦

¦ ¦ ¦ S1 / П¦ ¦ ¦

¦ S1 +------+----/ --+---------+---------+

¦ ¦ ¦ Вт.А /¦ Выт.А /¦ ¦

¦ ¦ А ¦ / ¦ / ¦ Отв. ¦

¦ ¦ ¦S1 / П¦S2 / П¦ ¦

+------+------+----/---+----/---+---------+

¦ ¦ ¦ ¦ ¦ ¦

¦ ¦ / ¦ Е ¦ Е ¦ Доп. ¦

¦ ¦ ¦ ¦ ¦ ¦

¦ S2 +------+---------+---------+---------+

¦ ¦ ¦ ¦ Выт.А /¦ ¦

¦ ¦ А ¦ Е ¦ / ¦ Отв. ¦

¦ ¦ ¦ ¦S2 / П¦ ¦

L------+------+---------+----/---+----------

Разберем цепочку 0011-+ с помощью МП-автомата:

г===========T=============T===========¬

¦ Цепочка ¦ Состояние ¦ Магазин ¦

¦-----------+-------------+-----------¦

¦ 0011-+ ¦ S1 ¦ / ¦

¦ ¦ ¦ ¦

¦ 011-+ ¦ S1 ¦ А / ¦

¦ ¦ ¦ ¦

¦ 11-+ ¦ S1 ¦ А А / ¦

¦ ¦ ¦ ¦

¦ 1-+ ¦ S2 ¦ А / ¦

¦ ¦ ¦ ¦

¦ -+ ¦ S2 ¦ / ¦

¦ ¦ ¦ ¦

L===========¦=============¦===========-

Цепочка допущена т.к. конечная конфигурация МП-автоматадопускающая (состояние S2, в магазине пусто).

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Основы ДИСКРЕТНОЙ МАТЕМАТИКИ

МЕЖДУНАРОДНОГО НАУЧНО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Автоматы-распознаватели с магазинной памятью

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Условные обозначения, принятые в конспекте лекций
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-граммаикой, если правые части всех правил этой грамматики начинаются стерминальных символов и для правил с одинаковыми левыми ча