Линейно-ограниченные автоматы.

(Машина Тьюринга с ограниченной рабочей лентой) (до 90 минут)

Машина Тьюринга U_Т, которой для распознания слова aÎА* длины n (пишут |a|=n) необходима внешняя память с числом ячеек не более k,n, где k- число, не зависящее от анализируемой ячейки, называется автоматом с линейно-ограниченной памятью. Эти автоматы распознают контекстные языки.

Работа Л-О. автомата состоит из следующих этапов:

1) Просматривается слева направо записанное на ленте предложение и первая и последняя его буквы заменяются на нетерминированные символы.

2) ищет в слове подцепочки, являющиеся правыми частями определяющих его (автомата) работу правила НС-грамматики. Если такая подцепочка найдена, автомат заменяет правую часть соответствующего правила (т.е. найденную подцепочку) на левую часть. При этом в случае, если длина левой части правила меньше длины правой, то в оставшиеся свободные ячейки записывается так называемый «нейтральный» символ, не влияющий на работу Л.О. автомата. Если анализируемая цепочка входит в язык a(s), то должен найтись такой вариант работы Л.О.-автомата, при котором эта цепочка может быть преобразована в цепочку, состоящую из начального символа грамматики и последовательности нейтральных символов. В этом случае начинается третий этап работы.

3) Автомат просматривает цепочку до крайнего правого элемента (этот символ будет отмечен) и переходит в заключительное состояние. Если первоначальная цепочка в язык не входит, автомат при ее анализе либо придет в тупиковую конфигурацию, либо перейдет в заключительное состояние в момент, когда управляющая головка будет указывать на некоторый символ цепочки.

Пример: Построить распознающий ЛО-автомат для НС-языка a(s₁)={aⁿbⁿaⁿ}, если s₁- грамматика имеет следующие продукции:

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.

С учетом того, что вывод предложения a³b³a³Îa(s₁) возможен в эквивалентной грамматике с продукциями:

J®aCa, C®aCBa, C®b, aB®Ba bB®bb.

Представим конфигурации ЛО-автомата. в которые он приходит при распознавании следующей цепочки:

a₀q₁ aaabbbaaa a₀| a₀D q₁aabbbaaa a₀ |-- a₀Daabbbaaaq₁…

|-- q₂DaabbbaaaA |-- …|-- Daabq₂bbaaA |--…|--q₂DaabbBaaA|--…

|--Daaq₂bbBaaA |--…|-- q₂DaabBBaaA |--…|--Daaq₂bBBaaA |--…

|-- q₂DaaCBBaaA |--…|-- DaaCBq₂BaaA |--…|--q₂DaaCBaBaA |--…

|-- Daq₂aCBaBaA |-- …|--q₂DaCнннBaA|--…|--Dq₂aCнннBaA …

|--q₂DcннннннА|-- q?*|--q₂aCннннннa|--…|--q₂Jннннннн |--…|-- Jннннннннq_z

Примечания: Если анализируемая цепочка не входит в язык a(s₁)={aⁿbⁿaⁿ}, то ЛО-автомат при любом варианте анализа перейдет в тупиковую ситуацию. Например, один из вариантов анализа цепочки abaa следующий:

q₁abaa |--…|--q₂DbaA |--…|--…Dq₂baA |--…|--q₂DcaA |--…|--q₂aCaa|--q₂Jннa |--…

|--Jннq₂a –тупик.

Итак, алгоритм распознавания инициальным ЛО – автоматом , здесь q₀ – начальное состояние, F – множество заключительных состояний,

цепочек длины заключается в следующем:

· Образуется всевозможные конфигурации автомата длиной ℓ+1(ℓ- длина исходной цепочки , к которой добавляется единица – символ состояния q_i). Таких конфигураций конечное множество;

· Образуется из этих конфигураций всевозможные их последовательности без повторения(т.е. каждая конфигурация может входить в кортеж только один раз). Очевидно, что и такое множество наборов также конечно.

· Выделяется подмножество последовательностей, начинающихся с конфигураций до α и заканчивающихся конфигурациями вида . Если среди этих последовательностей найдется такая, которая определяет возможный вариант работы ЛО – автомата, цепочка допускается (т.е. распознана как элемент языка) автоматом, в противном случае – не допускается.

Теорема. Классы языков, допускаемых ЛО – автоматами, и НС – языков совпадают.

Лекция №22.

МАГАЗИННЫЕ АВТОМАТЫ(МП – АВТОМАТЫ).

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

Множество состояний

Магазинная память.

Структура МП

Текст лекции

МАГАЗИННЫЕ АВТОМАТЫ(МП – АВТОМАТЫ).

МП – автоматы, как частный случай машины Тьюринга, есть бесконечный автомат, внутренняя структура которого представляет собой магазинную память.

Дата добавления: 2015-12-01