Александр борисович об автоматной аппроксимации реальных языков

На правах рукописи

УДК 519.766 Холоденко Александр Борисович ОБ АВТОМАТНОЙ АППРОКСИМАЦИИ РЕАЛЬНЫХ ЯЗЫКОВ 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

МОСКВА - 2008

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

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

Официальные оппоненты: доктор физико-математических наук, профессор Чуличков Алексей Иванович;

кандидат физико-математических наук доцент Карташов Сергей Иванович.

Ведущая организация: Московский энергетический институт (технический университет).

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

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

Автореферат разослан 6 мая 2008 года.

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

Общая характеристика работы

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

Среди современных задач, связанных с работой с текстами на естествен ном языке, можно выделить поиск текстовой информации в больших и сверхбольших базах данных и знаний;

автоматическое рубрицирование тек стов;

построение интеллектуальных вопрос-ответных систем, способных, на пример, отвечать на наиболее типичные вопросы пользоватлей;

автомати ческий перевод текстов с одного языка на другой;

генерация текстов на за данную тему (например, всевозможных отчётов);

аннотирование и рефери рование текстов;

распознавание речи;

оптическое распознавание печатных и рукописных символов;

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

Исторически, одной из первых задач, потребовавших построения доволь но сложной модели естественного языка, была задача автоматического пе ревода, впервые сформулированная американцами А. Бутом и У. Уивером в 1946 году. Работы над системами автоматического перевода стимулировали развитие ряда языковых моделей, которые в дальнейшем нашли своё место во многих областях вычислительной техники. К примерам таких моделей можно отнести иерархию грамматик Хомского1 (в первую очередь – теорию автоматов2 и теорию контекстно-свободных грамматик3 );

грамматики Вуд са4 ;

вероятностные автоматы5 ;

грамматики зависимостей6 ;

модели Смысл текст 7 и многие другие. Изучение подобных моделей привело к созданию Хомский Н. Синтаксические структуры. // Новое в лингвистике. Вып. II. М., 1962.

Кудрявцев В.Б., Алёшин С.В., Подколзин А.С. Введение в теорию автоматов. -М.: Наука, 1985.

Ахо А. и Ульман Дж. Теория синтаксического анализа, перевода и компиляции. -М.: Мир, 1978.

Вудс В.А. Сетевые грамматики для анализа естественных языков // Кибернетический сборник. Но вая серия. Вып.13. -М.: Мир, 1978. С. 120-158.

Бухараев Р.Г. Основы теории вероятностных автоматов -М.: Наука, 1985.

Daniel Sleator and Davy Temperley. 1991. Parsing English with a Link Grammar. Carnegie Mellon University Computer Science technical report CMU-CS-91-196, October 1991.

Мельчук И. А. Опыт теории лингвистических моделей Смысл Текст. -M.: Наука, 1974.

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

проблема нахождения пересечения двух языков;

проблема сложности описания языка и так далее.

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

В том случае, если система обладала большим словарём, удовлетворитель ной работы без учёта особенностей языка добиваться уже не удавалось. Это также подстегнуло исследования по моделированию естественного языка, однако в области распознавания речи наибольшее распростронение получи ли вероятностные языковые модели. Самая простая из них – так называемая n-граммная модель8 до настоящего времени используется в большинстве со временных коммерческих систем распознавания речи.

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

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

Для значительной части романских и германских языков, а также для ряда азиатских языков (например, китайского и японского) в настоящее вре мя уже разработаны коммерческие системы распознавания речи. Удачной коммерческой системы для русского языка до сих пор не существует. Одной из основных причин этого является отсутствие эффективной модели для EAGLES. HANDBOOK of Standards and Resources for Spoken Language Systems, Mouton de Gruyter, 1997.

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

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

Цель работы Цели настоящей работы:

• решить задачу исправления ошибок в формальных языках;

• изучить частотные свойства естественных языков;

• определить и изучить классы формальных языков, близких к есте ственным;

• обобщить эвристические свойства n-граммных моделей на формаль ные языки.

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

Научная новизна и ценность работы Работа носит теоретический характер. Основные результаты диссертации являются новыми и состоят в следующем:

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

2. n-Граммная модель успешно модернизирована для работы с русским языком.

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

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

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

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

1. Введено понятие обобщенного слова как ориентированного информа ционного графа без (ориентированных) циклов с отметками в виде букв и весов на ребрах. При потенциально экспоненциальной мощно сти множества слов, представляемых обобщенным словом, построены полиномиальные алгоритмы нахождения пути в обобщенных словах из регулярных (O(n2 )) и контекстно-свободных языков (O(n3 )), где n яв ляется длиной обобщенного слова и не зависит от используемой грам матики. Данные алгоритмы находят применение в задачах коррекции результатов распознавания и в задачах проверки правописания.

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

Апробация работы Результаты диссертации докладывались на следующих семинарах механико математического факультета МГУ им. М.В.Ломоносова и научных конфе ренциях:

1. Семинар Теория автоматов под руководством академика, профессо ра, д.ф-м.н. В.Б. Кудрявцева (2002 – 2008гг.).

2. Семинар Теория дискретных функций и приложения под руковод ством профессора, д.ф-м.н. Д.Н. Бабина (1999 – 2008 гг.).

3. Международная конференция Информационные технологии в инно вационных проектах (Ижевск, 1999).

4. Международный семинар Диалог’99 по компьютерной лингвистике и ее приложениям (Таруса, 1999).

5. IV Всероссийская конференция Нейрокомпьютеры и их применение (Москва, 2000).

6. V International Congress on mathematical modeling, (Dubna, 2002).

7. IX Международный семинар Дискретная математика и её приложе ния (Москва, 2007).

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

Структура и объем диссертации Диссертация состоит из введения, пяти глав и списка литературы. Текст диссертации изложен на 99 страницах. Список литературы содержит 45 на именований.

Содержание работы Во введении даётся общая характеристика работы, а также приводятся основные понятия и результаты, изложенные в диссертации.

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

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

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

В этой главе рассматриваются:

• дискретные модели:

– регулярные языки;

– контекстно-свободные языки;

– системы, основанные на использовании лингвистических экс пертных систем и систем понимания и учёта смысла;

• вероятностные модели:

– n-граммы;

– системы, основанные на деревьях решений;

– вероятностные обобщения контекстно-свободных грамматик.

Здесь показаны преимущества и недостатки каждого из этих подходов, а также приведена общепринятая на сегодняшний день оценка качества модели, так называемый коэффициент неопределённости (в англоязычной литературе используется термин perplexity coecient 9 ). В случае n граммных моделей, которые и будут преимущественно изучаться в дальней шем в рамках данной работы, коэффициент неопределённости показывает среднюю степень ветвления в модели, то есть сколькими способами в сред нем может быть продолжено фиксированное начало предложения.

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

L. R. Bahl, J. K. Baker, F. Jelinek, and R.L. Mercer. Perplexity - a measure of the diculty of speech recognition tasks. Program of the 94th Meeting of the Acoustical Society of America J. Acoust. Soc. Am., vol. 62 p. S63, 1977. Suppl. no. 1.

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

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

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

В каждом таком графе есть источник (вершина без входящих рёбер) и сток (вершина без исходящих рёбер). Они называются начальной и конечной вершиной обобщенного слова соответственно.

Задача формулируется следующим образом.

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

1. слово, полученное конкатенацией букв, записанных вдоль этого пути, должно быть допустимым словом в грамматике ;

2. сумма весов, стоящих на рёбрах пути, должна быть минимальна.

В работе показано, что в случае, если грамматика задаётся конечным автоматом, данная задача может быть решена за время O(n2 ), где n - коли чество вершин в графе обобщённого слова. В том случае, если грамматика является контекстно-свободной, то данная задача может быть решена за время O(n3 ), где n - количество вершин в графе обобщённого слова.

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

Кроме того, в данной главе приведены два примера применения постро енной техники: в задаче коррекции результатов оптического распознавания символов и в задаче поиска минимального исправления ошибочно написан ного слова (так называемая задача spellchecker’а).

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

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

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

Если в общем виде вероятностная модель позволяет вычислить вероят ность того, что слово = ai1 ai2... ais является допустмым словом языка, то в n-граммной модели делается допущение о том, что P (aij |ai1 ai2... aij1 ) P (aij |aijn+1 aijn+2... aij1 ).

Это приводит к тому, что вероятность P (ai1 ai2... ais ), расписанная в виде произведения условных вероятностей P (ai1 ai2... ais ) = P (ai1 ) P (ai2 |ai1 )... P (as |ai1 ai2... ais1 ), может быть оценена через произведение вероятностей вида P (aij |aijn+1 aijn+2... aij1 ). Очевидно, что в таком случае модель сво дится к конечному множеству вероятностей, каждую их которых можно оценить на этапе обучения системы, вычислив частоту встречаемости соответствующих слов в обучающей выборке.

Как уже было отмечено, для моделирования русского языка такие моде ли подходят плохо. В этой главе предложено обобщение n-граммной модели, которое позволило распространить аппарат n-граммных моделей и на рус ский язык. Главными трудностями в русском языке на пути создания таких моделей являются большое количество словоформ (что приводит к серьёзно му увеличению словарей системы) и относительно свободный порядок слов.

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

D. Kanevsky, M. Monkowsky, J. Sedivy. Large Vocabulary Speaker-Independent Continuous Speech Recognition in Russian Language. Proc. SPECOM’96, St.-Petersburg, October 28-31, 1996.

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

Каждая из этих моделей была построена и обучена на материале россий ской периодики. При этом было показано, что полученные характеристики языковых моделей примерно соответствуют среднестатистическим характе ристикам моделей для английского языка (коэффициент неопределённости в модели, основанной на леммах, составил около 230;

для моделей на англий ском языке этот коэффициент обычно оказывается в районе 100). Коэффи циент неопределённости в категорной модели (построенной исключительно на морфологической информации) оказался около 20.

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

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

В четвёртой главе вводится обобщение понятия n-граммной модели на бесконечные формальные языки. А именно, вводится частота встречае мости слова w на s-ом месте, а затем рассматривается предельная частота встречаемости слова w как предел при s.

Более точно:

Пусть A = (A, Q,, QF, q0 ) - конечный детерминированный автомат, A входной алфавит, S - множество состояний, QF Q - множество финальных состояний, : A Q Q - функция переходов, q0 - начальное состояние автомата.

Введем несколько важных обозначений.

Через LA = { A |(q0, ) QF } обозначим язык, порождаемый автоматом A. В тех случаях, когда не возникает разночтений, индекс A мы будем опускать.

Для натурального числа s N обозначим через L(s) множество слов языка L длины s:

L(s) = { L : || = s}.

Через PL обозначим множество префиксов слов языка L, включая сами слова:

PL = { A | A, L}, L PL.

Через L обозначим множество слов языка L, оканчивающихся на, то есть L = { A L| A, = }.

Пусть |w| = n. Обозначим через lw (s) число слов языка L, имеющих с (s n + 1)-ой по s-ую букву подслово w, то есть lw (s) = |PLw (s)|.

Введём Gw (s) – частоту встречаемости слова w на s-ом месте как lw (s) Gw (s) =.

lw (s) |w |=|w| Через Gw = lim Gw (s) обозначим предельную частоту встречаемости s слова w среди слов той же длины.

Пусть w A - слово и a A - буква, |wa| = n.

Введём величину w,a (s) как lwa (s) w,a (s) =.

lw a (s) |w |=|w| Определение. Величину w,a = lim w,a (s), s если она существует, назовём n-граммой языка L для пары (w, a).

Определение. Язык L назовём марковским языком порядка n, если существуют все n-граммы w,a, где |wa| = n и существуют все частоты Gv, где |v| = n.

Множество марковских языков порядка n обозначим через M(n). Через M обозначим класс марковских языков, то есть языков, являющихся мар ковскими при любом порядке n:

M= M(n).

n= Показано, что в классе регулярных языков существуют языки, не явля ющиеся марковскими, поэтому выделение и изучение подкласса марковских регулярных языков оказывается оправданным. Тем не менее, число мар ковских регулярных языков достаточно велико. Обозначим через MN класс марковских языков, задаваемых автоматами не более чем с N состояниями;

через RN обозначим класс всех регулярных языков, задаваемых автоматами не более чем с N состояниями. Тогда справедлива следующая теорема:

Теорема 4.4 (Оценка числа марковских языков) Для достаточно больших N MN.

RN e Оказывается, что классы марковских языков строго вкладываются друг в друга. Это показывают Теорема 4.1 и Теорема 4.2.

Теорема 4.1.

Если язык является марковским порядка n, то он также является мар ковским порядка k n.

Теорема 4.2.

Для любого n N существует язык L, такой, что L Mn1, но при этом L Mn.

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

M (1) M (2) M (3)... M (n)...

С другой стороны, если язык L фиксирован, то ситуация становится об ратной. А именно, справедлива Теорема 4.3.

Пусть язык L = LA задан автоматом A = {A, Q,, QF, q0 }. Тогда из L M(2|Q| ) следует, что L M.

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

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

Определение. Активной матрицей автомата A назовём матрицу ин цедентности его активного графа (взятую с учетом кратностей ребер).

Справедлива следующая теорема, дающая пример достаточного условия марковости:

Теорема 4.5.

Если активная матрица автомата A имеет единственное максимальное по модулю собственное значение, то задаваемый этим автоматом язык является марковским.

Доказательство теоремы 4.5 содержит способ нахождения произвольной n-граммы для языка L. В соответствии с этой процедурой, искомая n-грамма либо будет вычислена, либо будет доказано, что такой n-граммы не суще ствует. В соответствии с Теоремой 4.4 для установления принадлежности языка L к классу марковских языков достаточно проверить только суще ствование n-грамм при n = |Q|, где Q – множество состояний задающего язык L автомата. Таким образом, установление принадлежности произволь ного языка L классу марковских языков может быть получено за конечное число шагов.

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

Показано, что класс марковских языков не замкнут относительно основ ных теоретико-языковых операций: объединения, пересечения и дополнения, поэтому необходимо рассматривать более узкие классы языков. Примером такого класса является, например, класс каскадно-дефинитных языков.

Понятие дефинитных языков (то есть таких языков, функция переходов которых забывает далёкую предысторию) является прямым переносом идеологии марковских языков непосредственно на теорию автоматов. Од нако это свойство оказывается слишком жестким: любой дефинитный язык является марковским языком и все его n-граммы (для любого фиксирован ного n) равны между собой. Поэтому сами по себе дефинитные языки не очень интересны в свете рассмотрения марковских языков. Тем не менее, из них можно получить новый класс языков, с одной стороны небольшой (его доля среди всех языков, задаваемых автоматами с N состояниями, стремит ся к нулю с ростом N ), а с другой стороны – в некотором смысле всюду плотный в множестве марковских языков.

Пусть A1 = (A, Q1, 1, Q1, q0 ), A2 = (A, Q2, 2, Q2, q0 ). Пусть также q 1 F F Q1 и q 2 Q2. Введём операцию склейки двух автоматов по паре состояний (q 1, q 2 ).

Определение. Результатом склейки автоматов A1 и A2 называется автомат A = (A, Q1 Q2 \ {q 1 },, Q1 Q2 \ {q 1 }, q0 ), где F F 1 (q, a) Q1 \ {q 1 } и 1 (q, a) = q если q q2 Q1 \ {q 1 } и 1 (q, a) = q если q (q, a) = 1 (q 2, a) = q если q Q2.

(q, a) если q Каскадно-дефинитные языки получаются из класса дефинитных языков рекурсивно путём применения операции склейки двух автоматов по паре состояний.

Оказывается, введённая таким образом операция склейки двух автома тов по паре состояний позволяет получать автоматы с заданными свойства ми из набора простейших автоматов: циклов и отрезков.

Сформулируем сначала следующее утверждение.

Утверждение. Множество {Gab } является системой биграмм для некоторого регулярного языка L тогда и только тогда, когда для любо го i, 1 i |A| выполнено:

i M i, (1) где i – сумма по i-ому столбцу, Mi - максимум по i-ой строке в матрице переходов для автомата, задающего язык L.

Определение. Условие (1) будем называть условием биграммности множества {Gab }, а соответствующую ей матрицу будем называть биграммной матрицей.

Теорема 5. Для всякой рациональной биграммной матрицы найдётся автомат A, матрица биграмм которого A будет в точности совпадать с исходной биграммной матрицей, и который может быть получен из простей ших автоматов – отрезков и циклов путём применения к ним операции склейки автоматов.

В том случае, если биграммная матрица автомата A содержит ирраци ональные числа, то для любого 0 её можно приблизить рациональной биграммной матрицей и построить автомат, имеющий в точности заданную рациональную биграммную матрицу. Это утверждение сформулировно в ра боте в виде теоремы 5.2:

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

При этом под расстоянием между двумя матрицами мы понимаем макси мум поэлементного модуля разности, то есть для двух биграммных матриц = {Gab } и = {Gab } (, ) = max |Gab Gab |.

a,bA Таким образом, для произвольной биграммной матрицы может быть по строен автомат A, имеющий биграммную матрицу, сколь угодно близкую к данной. При этом следует отметить, что Теорема 5.1 даёт конструктивный способ построения такого автомата.

Я выражаю глубокую и искреннюю благодарность своему научному ру ководителю – доктору физико-математических наук, профессору Дмитрию Николаевичу Бабину за постановку задач, постоянную поддержку и внима ние к работе.

Я благодарю научного сотрудника лаборатории Проблем теоретической кибернетики, кандидата физико-математических наук Ивана Леонидовича Мазуренко за ценные обсуждения.

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

Публикации автора по теме диссертации 1. Холоденко А.Б. Использование лексических и синтаксических ана лизаторов в задачах распознавания для естественных языков. // Интел лектуальные системы. Т.4, вып. 1-2, 1999, с.185-193.

2. Холоденко А.Б. О построении статистических языковых моделей для систем распознавания русской речи. // Интеллектуальные системы. Т.6, вып. 1-4, 2002, с.381-394.

3. Холоденко А.Б. О марковских регулярных языках. // Материалы IX Международного семинара "Дискретная математика и её приложения", 18 23 июня 2007 года -М., Изд-во механико-математического факультета МГУ, 2007. с.358-361.

4. Холоденко А.Б. О языковых моделях для систем распознавания русской речи. // Интеллектуальные системы в производстве: Периодический научно-практический журнал - 2003. - №1 -Ижевск: Изд-во ИжГТУ, 2003. с.

146-155.

5. Холоденко А.Б. Лексический анализатор в распознавании последо вательных образов. // Информационные технологии в инновационных про ектах: Материалы докладов. Международная конференция, 20-22 апреля 1999 г. -Ижевск: ИжГТУ, 1999, с. 43-44.

6. Холоденко А.Б. Исправление ошибок в формальных языках. // Ней рокомпьютеры и их применение: Сборник докладов. IV Всероссийская кон ференция, Москва. 16-18 февраля 2000 г. -М.: Издательское предприятие редакции журнала "Радиотехника", 2000, с. 627-630.

7. Kholodenko A. To the creating of the language models for Russian. // V International Congress on mathematical modeling. September 30 - October 6, 2002, Dubna, Moscow Region. Book of abstracts, V. 2, -M.:"Janus-K", 2002, p. 97.