|
(Машина Тьюринга с ограниченной рабочей лентой) (до 90 минут)
Машина Тьюринга UТ, которой для распознания слова aÎА* длины n (пишут |a|=n) необходима внешняя память с числом ячеек не более k,n, где k- число, не зависящее от анализируемой ячейки, называется автоматом с линейно-ограниченной памятью. Эти автоматы распознают контекстные языки.
Работа Л-О. автомата состоит из следующих этапов:
1) Просматривается слева направо записанное на ленте предложение и первая и последняя его буквы заменяются на нетерминированные символы.
2) ищет в слове подцепочки, являющиеся правыми частями определяющих его (автомата) работу правила НС-грамматики. Если такая подцепочка найдена, автомат заменяет правую часть соответствующего правила (т.е. найденную подцепочку) на левую часть. При этом в случае, если длина левой части правила меньше длины правой, то в оставшиеся свободные ячейки записывается так называемый «нейтральный» символ, не влияющий на работу Л.О. автомата. Если анализируемая цепочка входит в язык a(s), то должен найтись такой вариант работы Л.О.-автомата, при котором эта цепочка может быть преобразована в цепочку, состоящую из начального символа грамматики и последовательности нейтральных символов. В этом случае начинается третий этап работы.
3) Автомат просматривает цепочку до крайнего правого элемента (этот символ будет отмечен) и переходит в заключительное состояние. Если первоначальная цепочка в язык не входит, автомат при ее анализе либо придет в тупиковую конфигурацию, либо перейдет в заключительное состояние в момент, когда управляющая головка будет указывать на некоторый символ цепочки.
Пример: Построить распознающий ЛО-автомат для НС-языка a(s1)={anbnan}, если s1- грамматика имеет следующие продукции:
J®MCM, C®MCBM, C®b, MB®KB, KB®KM, KM®BM, bB®bb, M®a
† Решение:
Рассмотрим работу ЛО-автомата при анализе терминальной цепочки aaabbbaaa, выводимой в данной грамматике следующим образом:
J® MCM, MMCBMM, MMMCBMBMM, MMMCBKBMM, MMMCBKMMM, MMMCBBMMM, MMMbBBMMM, MMMbbBMMM, MMMbbbMMM, aMMbbbMMM, aaMbbbMMM, aaabbbMMM, aaabbbaMM, aaabbbaaM, aaabbbaaa.
С учетом того, что вывод предложения a3b3a3Îa(s1) возможен в эквивалентной грамматике с продукциями:
J®aCa, C®aCBa, C®b, aB®Ba bB®bb.
Представим конфигурации ЛО-автомата. в которые он приходит при распознавании следующей цепочки:
a0q1 aaabbbaaa a0| a0D q1aabbbaaa a0 |-- a0Daabbbaaaq1…
|-- q2DaabbbaaaA |-- …|-- Daabq2bbaaA |--…|--q2DaabbBaaA|--…
|--Daaq2bbBaaA |--…|-- q2DaabBBaaA |--…|--Daaq2bBBaaA |--…
|-- q2DaaCBBaaA |--…|-- DaaCBq2BaaA |--…|--q2DaaCBaBaA |--…
|-- Daq2aCBaBaA |-- …|--q2DaCнннBaA|--…|--Dq2aCнннBaA …
|--q2DcннннннА|-- q?*|--q2aCннннннa|--…|--q2Jннннннн |--…|-- Jннннннннqz
Примечания: Если анализируемая цепочка не входит в язык a(s1)={anbnan}, то ЛО-автомат при любом варианте анализа перейдет в тупиковую ситуацию. Например, один из вариантов анализа цепочки abaa следующий:
q1abaa |--…|--q2DbaA |--…|--…Dq2baA |--…|--q2DcaA |--…|--q2aCaa|--q2Jннa |--…
|--Jннq2a –тупик.
Итак, алгоритм распознавания инициальным ЛО – автоматом , здесь q0 – начальное состояние, F – множество заключительных состояний,
цепочек длины заключается в следующем:
· Образуется всевозможные конфигурации автомата длиной ℓ+1(ℓ- длина исходной цепочки , к которой добавляется единица – символ состояния qi). Таких конфигураций конечное множество;
· Образуется из этих конфигураций всевозможные их последовательности без повторения(т.е. каждая конфигурация может входить в кортеж только один раз). Очевидно, что и такое множество наборов также конечно.
· Выделяется подмножество последовательностей, начинающихся с конфигураций до α и заканчивающихся конфигурациями вида . Если среди этих последовательностей найдется такая, которая определяет возможный вариант работы ЛО – автомата, цепочка допускается (т.е. распознана как элемент языка) автоматом, в противном случае – не допускается.
Теорема. Классы языков, допускаемых ЛО – автоматами, и НС – языков совпадают.
Лекция №22.
МАГАЗИННЫЕ АВТОМАТЫ(МП – АВТОМАТЫ).
Продолжительность: 2 часа (90) минут
Ключевые (основные) вопросы (моменты)
Множество состояний
Магазинная память.
Структура МП
Текст лекции
МАГАЗИННЫЕ АВТОМАТЫ(МП – АВТОМАТЫ).
МП – автоматы, как частный случай машины Тьюринга, есть бесконечный автомат, внутренняя структура которого представляет собой магазинную память.
Дата добавления: 2015-12-01; просмотров: 57 | Нарушение авторских прав