Частичное предвосхищение сверхсобытий автоматами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА

На правах рукописи УДК 519.71

Мастихина Анна Антоновна

ЧАСТИЧНОЕ ПРЕДВОСХИЩЕНИЕ СВЕРХСОБЫТИЙ АВТОМАТАМИ.

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

1 0 пл") о^?

МОСКВА - 2012

005016790

005016790

Работа выполнена на кафедре математической теории интеллектуальных сист( Механико-математического факультета Московского государственного унинерсите имени М.В.Ломоносова.

Научный руководитель доктор физико-математических наук,

профессор

Гасанов Эльяр Эльдарович

Официальные оппоненты Подловчеико Римма Ивановна,

доктор физико-математических наук, профессор,

Научно-исследовательский вычислительный цент] Московского государственного университета имен М.В.Ломоносова, ведущий научный сотрудник '

Лялин Илья Викторович,

кандидат физико-математических наук,

Элайн Технолоджп, старший разработчик

Ведущая организация Российский государственный

гуманитарный университет (РГГУ)

Защита диссертации состоится 8 июня 2012 г. в 16 ч. 45 мин. на заседании диссе тационного совета Д.501.001.84 при Московском государственном университете име! М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинск! горы, д.1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического ф культета МГУ (Главное здание, 14 этаж).

Автореферат разослан 27 апреля 2012 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ, д.ф .-м.н., профессор

Иванов А.О.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

Понятие автомата является одним из центральных понятий в математической кибернетике. Задачи анализа поведения автоматов и синтеза автоматов с заданным поведением являются одними из ключевых задач теории автоматов. В диссертации исследуется вопрос о возможности использования автомата для предсказания своей входной последовательности и рассматривается задача синтеза автоматов, наилучшим образом предсказывающих некоторые наперед заданные множества входных последовательностей. Эта задача является актуальной для теории автоматов и представляет как теоретическую, так и практическую ценность, поскольку может быть использована во многих прогнозирующих системах к в технических устройствах, таких, например, как биржевые системы, оптимизирующие компиляторы, устройства обработки видео-изображений, фильтры шумоподавления и т.п.

Понятие автомата с предвосхищением появилось еще в начале развития теории автоматов1. Такой автомат использует в своей работе не только данные, уже поступившие на вход, но и некоторые значения, которые должны поступить в будущем. Используя эти значения, можно существенно ускорить работу устройства, а в случае, если предполагаемый символ не совпал с поступившим на вход на самом деле, происходит откат алгоритма, и выигрыша во времени не случается.

Соответственно, большое значение имеет выбор предполагаемого следующего символа. В качестве еще не поступивших данных часто используется наиболее вероятное значение, то есть для последовательности, символы которой нужно предсказать, известны вероятности встретить ту или иную комбинацию, либо эта вероятность вычисляется на основе поступившей части последовательности2.

Также можно использовать для предсказания некоторую информацию о строении последовательности. Например, если она порождена некоторой

1 Трдхтеиброт Б.А.. Бврлзшг Я М. Конечные антоматы (понсухение и сшгтсз) ■ ' М.: Науки. 1970

2Hutter М. Optimalitv of Universal Bayesian Sequence Prediction for General Loss and Alphabet// Journal of Machine Learning Research X.4. — 2003. — Pp. 971-1000.

формальной грамматикой. Наиболее популярны регулярные3 и контекстно-свободные грамматики4, они используются в языках программирования и относительно просты для разбора.

В статье А.Г.Вереникина и Э.Э.Гасанова0 были введены угадывающие автоматы — конечные автоматы, угадывающие сверхслово или множество сверхслов. Это значило, что через некоторое конечное время после начала подачи сверхслова автомат начинает угадывать каждый следующий символ, то есть на выходе в момент времени t выдавать элемент входной последовательности с номером t + 1. Было показано, что угадываемы только множества периодических сверхслов.

В статье автора диссертации6 было введено понятие частичного угадывания, которое имеет место в случае, если автомат угадывает следующий символ не обязательно в каждый момент времени, но достаточно часто.

Вводится степень угадывания как предел отношения числа верно предсказанных символов за время t от начала слова к длине префикса t при t, устремленном к бесконечности.

В зависимости от того, брать ли нижний или верхний предел в случае, если они не равны, меняется смысл задачи. В первом случае угадывание должно происходить регулярно, вне зависимости от того, когда измерять долю угаданных символов. Случай же верхнего предела иллюстрирует ситуацию, когда у угадывающего есть возможность самостоятельно выбирать, когда подсчитывать эту долю. Частичная угадываемость исследуется и для верхней, и для нижней степени.

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

3Мнпго1 D., Pevc-dic В. The syntactic prediction with token automata: application to IfaiidiAS system // Theoretical Computer Science. — 2001. — Vol. 267. Issue 1-2. — Pp.121-129.

J\\ ¡les J., Elman J. L. Learning to count without a counter: A case study of dynamics and activation landscapes in recurrent networks. , ' Proceeding of (lit! .Scwtilwntli Annual ('«»Гепгисге of tl«; (Uigiiiliv« S/ienre StM-iVt v. - MIT Pris*. . 1 УУГ>, . Pp. 482Ц487.

0 Верен и кия А.Г., Гасанов Э."3. Об автоматной детерминнзапии множеств сверхслов / Дискретная математика. — 200G. — T.18, №2. — С. 84-97.

"Мастяхпиа A.A. О частичном угадывании сверхслов '/ Интеллектуальные системы. — 2007. — Т.11, вып.1-4 — С.609-610.

Цель работы. Цель работы состоит в нахождении критериев, позволяющих определить, является ли некоторое сверхсобытие частично угадываемым. В случае положительного ответа необходимо построить автомат, угадывающий данное сверхсобытие с как можно большей степенью.

Методы исследования. В работе используются методы дискретпой математики, а именно, теории автоматов и теории графов, также математического анализа.

Научная новизна.

Диссертация имеет теоретический характер. Результаты получены лично автором, являются новыми и состоят в следующем.

1. Получен критерий частичной угадываемости общерегулярных множеств. В случае, если множество угадываемо, строится угадывающий конечный автомат, причем он отличается от принимающего только выходной функцией. Также предложен способ построения угадывающего автомата, основанный на информации о словах, не встречающихся во множестве последовательностей. Получен способ нахождения для общерегулярного множества наибольшей возможной степени и построения автомата, угадывающего его с этой степенью.

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

3. Для сверхитераций детерминированных контекстно-свободных языков, сохраняющих детерминированность при итерации, получен критерий частичной угадываемости в смысле нижней степени.

4. Получены оценки степени угадывания, причем они достижимы, то есть для множеств с наименьшей возможной долей предложенный алгоритм угадывает именно столько.

Идея частичного угадывания состоит в том, что в случае, когда оно вообще возможно, последовательности должны обладать некоторыми ограничениями, которые нарушаются, только если последовательность оказы-

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

Практическая ценность. В работе понятие угадывания заданной последовательности заданным алгоритмом вводится как предел доли угаданных символов. Частичное угадывание множества последовательностей имеет место, если алгоритм угадывает часть символов каждой последовательности, то есть даже в худшем случае есть некоторый выигрыш.

Рассмотренные машины, реализующие алгоритмы угадывания — детерминированные автоматы — представляются естественными для этой цели.

Множества, все последовательности которых нельзя угадать никаким детерминированным автоматом, случайны в том смысле, что в каждый момент следующий символ может оказаться любым. Полученные критерии иллюстрируют, как отличается это свойство для множеств, порожденных разными формальными грамматиками.

Допустимы обобщения, такие как подсчет средней доли угадывания во всем множестве, а также комбинации с вероятностным подходом.

Результаты могут быть использованы в программировании при создании оптимизирующих компиляторов. Регулярные и 1Х(1)-грамматики широко распространены в этой области, так как они обладают широкими выразительными возможностями, но при этом достаточно просты для распознавания. Угадывающие автоматы могут иметь широкое применение при синтезе чипов для обработки интенсивных потоков данных, поскольку в этих устройствах без предсказания поступающих последовательностей невозможно добиться нужной производительности.

Для рассмотренных множеств критерии разграничивают случаи, когда имеет смысл предсказывать, основываясь на поступившей части информационного потока и общей структуре множества, и когда никакой алгоритм не сможет дать результата, лучшего, чем подбрасывание монеты.

Алгоритмы, предложенные для частичного угадывания, удобны, во-первых, тем, что практически не требуют специальных построений, так как основываются на устройстве, принимающем данное множество последовательностей. Во-вторых, среди некоторых множеств они угадывают существенную долю символов, иногда максимально возможную.

Апробация работы. Результаты данной работы докладывались и публиковались в тезисах следующих конференций.

Конференция студентов, аспирантов и молодых ученых мех-мат. ф-та МГУ (2008, Москва).

Международная конференция "Современные проблемы математики, механики и их приложений", посвященная 70-летию академика В.А.Садовипчего (2009, Москва).

Международная конференция студентов, аспирантов и молодых ученых "Ломоносов"(2009, 2010, 2011, 2012, Москва). Доклады на конференциях "Ломоносов-2010", "Ломоносов-2011" и "Ломоносов-2012" были отмечены грамотами за лучший доклад.

Международный семинар "Дискретная математика-2010" (2010, Москва).

54-ая научная конференция МФТИ "Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе"(2011, Москва-Долгопрудный-Жуковский).

X Международная конференция "Интеллектуальные системы и компьютерные науки" (Москва, 2011).

Также результаты докладывались па семинарах механико-математического факультета МГУ им. М.В.Ломоносова: на семинаре "Теория автоматов" под руководством академика, проф., д.ф-м.н. В.Б. Кудрявцева (2011 г.), на семинаре "Вопросы сложности алгоритмов поиска" иод руководством проф., д.ф-м.н. Э.Э.Гасанова (2006-2011 гг.), на семинаре МИ АН и ВЦ по теории сложности под руководством член-корр., д.ф-м.н. А.А.Разборова (2011 г.), на семинарах факультета ВМиК МГУ им. М.В.Ломоносова: на семинаре "Дискретная математика и математическая кибернетика" под руководством проф., д.ф-м.н. В.Б.Алексеева, проф., д.ф-м.н. А.А.Сапоженко, проф., д.ф-м.н. С.А.Ложкпна (2011 г.), на

семинаре "Теоретические проблемы программирования" под руководством проф., д.ф-м.н. Р.И.Подловченко, д.ф-.м.н. В.А.Захарова (2012 г.).

Публикации. По теме диссертации опубликовано 10 работ, список которых приведен в конце автореферата [1-10].

Структура и объем работы. Диссертация состоит ич введения и 4 глав. Объем диссертации 95 страниц. Список литературы содержит 25 наименований.

Будем рассматривать класс детерминированных, но, возможно, бесконечных автоматов ЯЛ.

Через г/д обозначим выходное сверхслово некоторого автомата 21 при подаче на его вход сверхслова а. Детерминированность автомата означает, что после подачи на его вход 4 первых символов сверхслова а он однозначно выдает некоторый выходной символ ¡/^(4).

Если а € {0,1}00, то обозначим

Автомат 21 угадывает сверхслово а 6 {ОД}* с (нижней) степенью а € [0,1]. если

21 угадывает сверхслово а € {0,1}** с верхней степенью а € [0.1], если

Величины ся(а) и са(а) будем называть соответственно степенью угадывания (предвосхищения) и верхней степенью угадывания сверхслова а автоматом 21.

Автомат 21 частично угадывает множество сверхслов А (частично угадывает в смысле верхнего предела), если За > 0, такое что Уа 6 А выполнено са'а) > <у > 0 (са(а) > <т > 0). Множество Л частично угадываемо, если найдется частично угадывающее его 21 € ЯН.

ОСНОВНЫЕ ПОНЯТИЯ

гя(л) = Ит^/Ч«, Г) = а.

с*{а) =Ит^(Р{аЛ) = сг.

Степень угадывания множества А

са(Л) = М са(а).

аеА

Также будут рассматриваться автоматы без выходов 21 = (А, С,}, <р, ^о).

Автомат 21 = {А, <р. дц) допускает сверхсобытие Я с помощью выделенного множества семейств состояний Г С 2®, если а € Я тогда и только тогда, когда множество состояний, проходимых автоматом бесконечное число раз при подаче на его вход сверхслова а, есть элемент Р.

В любом автомате можно выделить сильно связные компоненты Qi.---.Qk-. то есть совокупности состояний, достижимых друг из друга: е <2.,? = За € {0,1}*, т.ч. «¿>(д',а) =

Назовем сильно связную компоненту замкнутой, если из нее не достижима никакая другая сильно связная компонента.

Контекстно-свободная грамматика (./V, Т, Р, 5) (где N — множество нетерминальных символов (НС), Т — множество терминальных символов, 5б А' - аксиома, Р — множество правил вывода) находится в нормальной форме Грейбах, если все правила имеют вид А —» аВх-.-Вк, где В^, ...Вк 6 А\а € Т, или А —♦ а, или 5 —+ Л, где Л — символ для обозначения пустого слова. Причем, если грамматика простая ЬЬ( 1), для каждого нетерминального символа есть не более \Т\ правил .(с разными терминальными символами). Любую грамматику можно привести к нормальной форме Грейбах (то есть найти грамматику в нормальной форме Грейбах, порождающую тот же язык)7. Причем простая ££(1)-грамматика при приведении к нормальной форме Грейбах остается простой ЬЬ( 1).

Символ А достижим из символа В. если найдутся такие а 6 Т*, 0 € (ГиЛГ)*, что В =>* а Ар.

Символ грамматики А называется достижимым, если найдутся такие а е Т*,р £ (Ги /V)*, что 5 =>* аАр. Иначе символ называется недостижимым.

Нетерминальный символ А называется тупиковым, если не найдется такого слова /3 € Т*, что А =£>* /3.

' Ахи А.. Ульман Дж- Теории синтаксического анализа, перопола II компиляции: Пир. с англ. М.: Мир, 1У78.

Далее будем рассматривать грамматики в нормальной форме Грейбах и считать, что недостижимые и тупиковые символы отсутствуют. Также будем считать, что аксиома не встречается в правой части правил. Будем тогда говорить, что грамматика находится в нормальной форме.

Автомат с магазинной памятью — это семерка ((2, Е. Г. Z, Ф, до, где <3

— множество состояний, Е — входной алфавит, Г — магазинный алфавит, 2

— символ для обозначения пустого магазина, до £ <3 — выделенное начальное состояние, РСС} множество заключительных состояний, Ф — множество команд, каждая команда — отображение (ф х (Е и Л) х Г —»<3 х Г*).

Конфигурацией будем называть пару (?,£),(? € е Г*: текущее состояние и содержимое магазина.

Автомат работает потактово. Такт — работа автомата после поступения одного символа. Считаем, что А-такт выполняется мгновенно.

Автомат называется детерминированным, если для каждой конфигурации (д, £) имеется либо не более одной команды вида (д, о. —» г, /3), д, г 6 <3,£./3 £ Г* для каждого о £ Е и ни одной команды вида (д. А, —» г',Р'),г' е <3,0' 6 Г*, либо ни одной команды вида (д, а. £¡1 —> г, 0) и не более одной вида (д, А, —» г', 0').

СОДЕРЖАНИЕ РАБОТЫ

В первой главе рассматривается частичное угадывание в смысле нижнего предела конечными автоматами одного сверхслова. Получены оценки на число состояний автомата.

Пусть ЯЗст(а) — множество всех автоматов, угадывающих сверхслово а со степенью не меньшей ст.

Обозначим через ш (21) число состояний автомата 21 и введем

На{а) = шт аев„(а)

— минимальное число состояний автомата, угадывающего сверхслово а со степенью, не меньшей а.

Пусть А(п) — множество сверхслов с периодом п.

8

Теорема 1. 1) Если <7 = 1, то для любого п € N и любого ¡3 € А(п) выполнено

777.

— ^ Я„(в) ^ т < п,

где т — длина минимального периода сверхслова р.

2) Если а ^ то для любого п 6 N и любого 0 6 А(п) выполнено

В.ЛР) = 13) £сли <т > то для любого натурального п найдется такое периодическое сверхыово 7, что Ли (7) > п.

Теорема 2. Существует такое сверхслово, что ни один конечный автомат не угадывает его ни с какой степенью а £ (0,1].

Теорема 3. 1) Для любого а 6 [0, 5] существует сверхслово, которое угадывается любым конечным автоматом со степенью большей или равной а.

2) Ни для какого а € (5,1] ме существует такого сверхслова, что все автоматы угадывают его со степенью большей или равной а.

Во второй главе рассматривается частичное угадывание общерегулярных сверхсобытнй конечными автоматами.

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

Теорема 5. Пусть общерегулярное сверхсобытие Лх представимо в конечном инициальном автомате 01 = = п с помо-

щью некоторого Р С 2®, тогда следующие утверждения эквивалентны.

1. Сверхсобытие Л°°, Я С {0.1}*, не является частично угадываемым;

2. Уа е {0,1}* 3/3 6 {0,1}*, 7 £ {0,1}°°, что /За7 € Л00;

3. Хотя бы для одной замкнутой сильно связной компоненты автомата 21 выполнено € Р.

Теорема Т. Общерегулярное сверт.с.обытие Я\ Щ1 и и ... и где Я\, /?2- ■■•, Л^., Я[, Л'2,.... Я'к — некоторые регумрные события, частично угадываемо тогда и только тогда, когда частично угадываемо каждое из сверхсобытий Л|°, Л*...., Л£°.

Теорема 8. Пусть общерегулярное сверхсобытие L С {0,1}°° предста-вимо в конечном инициальном автомате 21 = ({0,1}, Q, tp, go).\Q\ = п. с помощью некоторого F С 2®. Сверхсобытие L не является частично угадываемьш тогда и только тогда, когда хотя бы дм одной замкнутой сильно связной компоненты Q автомата, 21 выполнено Q € F.

Обозначим класс автоматов, отличающихся от 21 только добавлением функции выхода, Ф(21) = {({0.1},Q,{0,1},¥>, V,»),^ : Q .{ОД}}.

Теорема 9. Рассмотрим общерегулярное множество L и автомат 21 = ({0,1}, Q, ip, qo), принимающий это множество с помощью F С при этом 4Qi, Qj € F, i ф j выполнено Qi П Qj = 0.

Тогда \/g S ffl выполнено c?{L) ^ таха'£ф(а) ca(£)■

Как следствие, возникает следующая теорема.

Теорема 10. Существует алгоритм, определяющий, является ли сверхсобытие L, представимое в приведенном автомате с п состояниями, частично угадываемым, и его сложность линейно зависит от п. Также существует алгоритм построения минимального автомата с наибольшей возможной степенью предвосхищения в случае, если сверхсобытие частично угадываемо.

В третьей главе рассматривается частичное угадывание сверхитераций простых LL{1)— грамматик. Угадывание производится автоматами с магазинной памятью, отдельно рассмотрен случай нижней и верхней степеней. Найдены оценки для степеней угадывания и грамматики, для которых эти оценки достигаются.

Теорема 11. Множество сверхслов, образованное сверхитерацией языка L(G), порожденного простой ЬЬ{\)-грамматикой G в нормальной форме, частично угадываемо в смысле нижней степени тогда и только тогда, когда хотя бы для одного нетерминального символа грамматики существует только одно правило вывода.

Обозначим за G(n,l) класс простых ££,(1)-грамматик в нормальной форме с параметрами |iV| = п и максимальной длиной команды (числом нетерминальных символов справа в команде) I.

За G°(n.l) обозначим класс таких грамматик из G(n,l), для которых L(G)00 частично угадываемо.

Теорема 12. Для произвольных п ^ 2.1 ^ 1 выполнено

inf sup c*(L(GD= l~l2 GgG"(nX) aera 2/" - ¿ - 1

inf sup c*{L{G),x) = 1.

GsG'Hi./jasOT

Назовем правило грамматики регулярным, если оно имеет вид А —» аВ (глубина стека соответствующего МП-автомата не увеличивается), Л, Б € N. Назовем правило стирающим, если правило имеет вид А —> а (глубина стека уменьшается). Остальные правила назовем удлинняющими.

НС В достижим по регулярным правилам по слову а из НС А, если существуют регулярные правила

А а(1)Ль А\ -> а(2)Л2,

Л|„| а(|а|)В.

Если существует такое слово а, то В достижим из А по регулярным правилам.

Назовем регулярной сильно связной компонентой R множество НС, попарно достижимых друг из друга по регулярным правилам.

Выходом из регулярной сильно связной компоненты R назовем правило для А 6 R. не являющееся регулярным или имеющее вид А —» аВ, где В i R.

Опишем алгоритм Ю, разделяющий НС грамматики G — (N, {0,1}, Р, S) на классы следующим образом.

1-й шаг.

Рассмотрим регулярные сильно связные компоненты, все выходы пз которых являются стирающими, занесем их в класс D\.

Далее удалим из грамматики НС из класса D\. То есть преобразуем грамматику G в грамматику G' = (N1, {0,1}, Р'. S), где N' — N \ Du а Р' получается из Р удалением правил, начинающихся с элементов D\ и вычеркиванием элементов Д из правых частей других содержащих их правил.

и

Например, если Д - {Л}, то правило В -* а АС из Р в Р' будет иметь вид В —> аС.

Пусть сделано г шагов.

Опишем (г + 1)-й шаг.

В грамматике рассмотрим сильно связные регулярные компоненты, все выходы из которых являются стирающими. Все НС из таких компонент занесем в класс Д;+1.

Удалим из правил грамматики правила, начинающиеся с НС из класса Д+1, а также вычеркнем элементы Д+1 из других правил. Получившуюся грамматику назовем

Алгоритм останавливается, когда некоторый класс Д. оказывается пуст или на А:-ом шаге объединение классов и-=1 Д есть множество всех НС N.

Теорема 13. Множество сверхслов Цй)™, где <3 = (./V, {0,1}, Р, £) — простая Ы(1)-грамматика в нормальной форме, частично угадываемым в смысле верхней степени тогда и только тогда, когда после работы алгоритма 2) выполнено и*_] Д ф N, где к — номер шага, на котором алгоритм 3) остановился.

Обозначим 1тт((2) ~ минимальная длина правила грамматики С.

Обозначим наибольшую длину цепи регулярных правил в грамматике б'1', то есть наибольшее г, такое что существуют А\ —+ а^А?. Л2 —> а2Л3,Аг —> аГАг+1 е Р('5, причем Ль ...Аг+х попарно различны.

Яс(С) = тах,=0.....кг'с(С).

Обозначим за (2(1', I. Дс) класс простых ££(1)-грамматик С с параметрами / ,„(о = V, = I, Яе(с) = лс.

За С?0(ГЛ,.йс) обозначим класс таких грамматик из (2(1', I, которые являются частично угадываемыми.

Теорема 14. Для произвольных 1^1. П.с, V ^ 1 выполнено

ае&ы = ЖТТ' КПЛ1- 1Ж)*-1}'

где к — номер шага, на котором алгоритм 2), примененный к й, останавливается.

В четвертой главе рассмотрено частичное угадывание в смысле нижней степени сверхитераций детерминированных контекстно-свободных языков,

таких, что их итерация также является детерминированным языком. Получен критерий и построен автомат с магазинной памятью.

Теорема 15. Пусть язык L* допускается детерминированным автоматом с магазинной па.штъю 21 = {Q, {0.1}, Г, Z, Ф, qц, F). Множество L°° является частично угадываемым тогда и только тогда, когда для некоторой пары (q,A),q 6 Q. А € Г существует только одна команда вида (q,a,A —> r,ß),ci 6 {0,1},г eQ,ße Г*.

Рассмотрим класс детерминированных автоматов с магазинной памятью с то состояниями, п магазинными символами и максимальной длиной команды I (под длиной подразумевается число магазинных символов в правой части команды), каждый из которых допускает такой язык L", что Lх является частично угадываемым. Обозначим этот класс М(п, т,1). Пусть L(93) — язык, допускаемый автоматом 25.

Теорема 16. Для любых п. m.l ^ 2 верно

inf sup c^iLi®)*) ----ггт-г.

БЛАГОДАРНОСТИ

Автор выражает глубокую благодарность своему научному руководителю профессору Гасанову Э.Э. за постановку задачи и помощь в работе, академику Кудрявцеву В.Б. за многочисленные полезные советы на всех этапах подготовки диссертации и всему коллективу кафедры математической теории интеллектуальных систем механико-математического факультета Московского государственного университета имени М.В.Ломоносова за теплую творческую атмосферу.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации автора по данной теме из списка ВАК:

1. Мастихина A.A. О частичном угадывании сверхслов // Интеллектуальные системы. — 2007. — Т. 11, вып.1-4 — С.609-619.

2. Мастихина A.A. Критерий частичного предвосхищения общерегулярных свехсобытий // Дискретная математика. — 2011.—Т.23, вып.4 — С.103-114.

3. Мастихина A.A. Частичное угадывание сверхсобытий, порожденных простыми £>£(1)-грамматиками /'/ Интеллектуальные системы. — 2011. — Т.15, вып.1-4 - С.507-532.

Публикации не из списка ВАК:

4. Мастихина A.A. Частичное угадывание сверхсобытий, образованных детерминированными контекстно-свободными языками. Материалы X международной конференции "Интеллектуальные системы и компьютерные науки—2011. — С.157-160.

5. Мастихина A.A. О частичном угадывании сверхслов. Международная конференция "Современные проблемы математики, механики и их приложений", посвященная 70-летию академика В.А.Садовничего (30 марта Ц 2 апреля 2009 г., Москва). Материалы конференции. С. 365-366.

6. Мастихина A.A. Частичное угадывание регулярных выражений. Международная конференция студентов, аспирантов и молодых ученых кЛомоносов-2009н> (2009, Москва). С.45-46.

7. Мастихина A.A. О частичном угадывании регулярих выражений. Международный семинар "Дискретная математика-2010"(2010, Москва). Издательство механико-математического факультета МГУ, Москва, 2010. 385-387.

8. Мастихина A.A. О частичном угадывании множеств сверхслов, заданных общерегулярными выражениями. Международная конференция студентов, аспирантов и молодых ученых "Ломоносов-2010"(2010, Москва).

9. Мастихина A.A. Частичное угадывание некоторых контекстно-свободных языков. Международная конференция студентов, аспирантов и молодых ученых "Ломоносов-2011"(2011, Москва).

10. Мастихина A.A. Частичное предвосхищение множеств последовательностей. Труды 54-й научной конференции МФТИ (10-30 ноября, 2011). Т.1. М.:МФТИ, 2011. С.60-61.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡00 экз. Заказ № ЛЯ