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

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

ЖЕЛТОВ Павел Валерианович

Представление моделей и алгоритмов в лингвопроцессорах сетями Петри

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата технических наук

УЛЬЯНОВСК - 2005

Работа выполнена в Казанском государственном техническом университете имени А.Н. Туполева на кафедре компьютерных систем и информационной безопасности

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

Официальные оппоненты: доктор технических наук, профессор

Защита состоится 16 февраля 2005 г. в 15 часов на заседании диссертационного совета Д 212.277.02 при Ульяновском государственном техническом университете по адресу: 432027, Ульяновск, ул. Северный Венец, 32, УлГТУ, Главный корпус, ауд. 211.

С диссертацией можно ознакомиться в научной библиотеке Ульяновского государственного технического университета.

ЗАХАРОВ Вячеслав Михайлович

СОСНИН Петр Иванович

доктор технических наук, профессор СУЛЕЙМАНОВ Джавдет Шевкетович

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

Автореферат разослан « » января 2005 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Крашенинников В.Р..

П шд

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

Актуальность темы. В связи с развитием вычислительной техники активно ведутся работы по созданию различных систем искусственного интеллекта, таких как системы машинного перевода (МП), подсистемы общения с базами данных (БД) и базами знаний (БЗ), экспертные системы и др.

Общим для всех этих систем является наличие лингвопроцессора (ЛП), преобразователя, осуществляющего анализ текста на естественном языке (ЕЯ), и переход к его формальному представлению, а также синтез - построение текста по его представлению. Как правило, ЛП содержат морфологический анализатор (МА) и синтаксический анализатор (CA), а также блоки синтеза. Однако задача анализа сложнее задачи синтеза, и ЛП, настроенные на анализ, обратимы в направлении синтеза, поэтому создание анализаторов достаточно актуально. В России и за рубежом в развитие этих исследований большой вклад внесли Ю.Д. Апресян, И.М. Богуславский, Р.Г. Бухараев, Ю.Р. Валькман, В.А. Вудс, Б.Ю. Городецкий, В.М. Захаров, Л.Л. Иомдин, Киммо Коскинь-еми, О.С. Кулагина, М.Г. Мальковский, И.А. Мельчук, Л.Г. Митюшин, A.C. Нариньяни, O.A. Невзорова, Н.В. Перцов, Э.В. Попов, Д.А. Поспелов, В.Д. Соловьев, П.И. Соснин, Д.Ш. Сулейманов, Л.Л. Цинман, С.А. Шаров и др. Анализ этих работ показывает, что должен быть решен обширный круг проблем, связанных с разработкой структур данных, моделей и алгоритмов ЛП. Особенно актуальным является целостный анализ ЛП как технических объектов и разработка сквозной методологии моделирования, используя однотипный математический аппарат..

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

Целью работы является разработка сетевых моделей на основе сетей Петри и алгоритмов для морфологического корректора и анализатора, синтаксического анализатора и классификатора ЛП.

В соответствии с поставленной целью в работе решаются следующие задачи:

1. Представление моделей ЛП сетями Петри.

2. Разработка структур данных, моделей и алгоритмов морфологического анализатора.

3. Разработка структур данных, моделей и алгоритмов морфологического корректора (МК).

4. Разработка структур данных, моделей и алгоритмов синтаксического анализатора.

5. Разработка структуры данных, модели и алгоритма синтаксического классификатора (СК).

6. Разработка и описание комплекса программ, реализующих ЛП.

Математический аппарат. В работе применены методы моделирования систем, аппарат сетей Петри, реляционное проектирование с помощью СУБД и теория алгоритмов.

Научная новизна положений, выносимых на защиту.

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

2. Предложены гибкие сети для моделирования схем следования, сетевые модели функционирования ЛП и его компонент на основе сетей Петри.

3. Смоделированы взаимодействия блоков ЛП, а также их компоненты: алгоритмы и структуры данных.

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

5. С помощью сетей Петри смоделирована параллельная обработка информации в ЛП, повышающая быстродействие системы.

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

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

Практическая ценность работы. Сетевые модели и алгоритмы, предложенные в диссертации, позволяют решать задачи разработки пакетов прикладных программ для автоматизации обработки текстов на ЕЯ, в частности корректоров, помогающих пользователям обнаруживать и исправлять ошибки в ЕЯ-тексге. Атрибутивно-типовые модели, разработанные в диссертационной работе, обеспечивают компактное хранение да^р^гдари, бМстрый доступ к данным. Гибкие

{ т •* Эв* €<• «4

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

Реализация и внедрение результатов. Теоретические и практические результаты диссертационной работы, в том числе их программная реализация, были внедрены на кафедрах компьютерных технологий и сравнительно-сопоставительного языкознания Чувашского государственного университета. Результаты исследований используются в учебном процессе при проведении лекций и лабораторных работ по курсу «Модели и методы искусственного интеллекта». Результаты исследований поддержаны грантами 98-01-03287 Российского фонда фундаментальных исследований и А04-1.5-180 Федерального агентства по образованию.

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на Итоговой научной конференции «Технические науки: Сегодня, завтра» (Чебоксары, 1997), Всероссийских конференциях фестивалях творчества студентов «Юность Большой Волги» (Чебоксары, 1999; 2000), Всероссийском семинаре «Проблемы прикладной лингвистики» (Пенза, 2001), Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов - 2002» (Москва, 2002), Всероссийских межвузовских научно-технических конференциях «Информационные технологии в электротехнике и электроэнергетике» (Чебоксары, 2002; 2004), в Казанской школе по компьютерной и когнитивной лингвистике TEL - 2003 (Казань, 2003), научной школе «Математическое моделирование, численные методы и комплексы программ» (Саранск, 2003), на научных студенческих конференциях (Чебоксары, 2000; 2001; 2002; 2003; 2004), Всероссийской научной конференции «Динамика нелинейных элек- * тротехнических и электронных систем» (Чебоксары, 2003), Региональной научной конференции «Волжские земли в истории и культуре России» (Чебоксары, 2003), семинаре по моделированию (Казань, 2004). На конкурсе работ студентов и молодых ученых в 2004 г. работа награждена дипломом Министерства образования и науки Российской Федерации.

Публикации. По результатам выполненных исследований опубликовано 35 работ, из них 18 статей и 17 тезисов докладов.

Структура и объем работы. Работа содержит введение, 4 главы, заключение, список использованной литературы и приложение. Объем работы 171 страница Работа содержит 31 рисунок и 105 таблиц.

Краткое содержание работы

Входная информация ЕЯ Входные данные

М

12

Выходные данные

Рис. 1. Концептуальная схема лингвопро цессора

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

В первой главе рассмотрена концептуальная модель ЛП как системы:

ЬР=<Р№,$А где — формальный аппарат; М — формальная

модель; 5 — структуры данных; А — алгоритмы анализа и синтеза; / — интерфейс, преобразующий входные данные во внутреннее представление и наоборот.

Концептуальная модель ЛП ЕЯ рассматривается в работе в виде схемы на рис.1. При этом формальный аппарат должен удовлетворять следующим требованиям: 1) формальная мощность; 2) вычислительная эффективность. Исходя из этих параметров проанализированы известные ЛП. Сделан вывод о том, что проанализированные ЛП, несмотря на все их достоинства, не сбалансированы по сложности. В связи с этим становится актуальной задача разработки ЛП, в котором достаточно простыми и наглядными были бы как структуры данных и формальный аппарат, так и алгоритмы.

Так как одной из областей применения ЛП являются системы машинного перевода (МП), то был разработан специальный сравнительно-сопоставительный подход к созданию ЛП.

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

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

граммных продуктов.

Сеть Петри определяется как

СНР,Т,А,Мо), (1)

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

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

С учетом этого были разработаны гибкие сети, примененные во второй главе, в морфологическом корректоре.

Гибкой сетью называется сеть вида

_ С=(Р, Т, А, Мо, С2), _(2)

где Р-{рг\1=\, п } - конечное множество позиций сети; 7-{/,|/-1,от } -конечное множество переходов сети; А - множество алгебраических представлений фрагментов сети; М0: о ~ начальная маркировка сети - функция, задающая начальное распределение меток по позициям сети; ТУо - множество натуральных чисел, включая 0; Л - таблица, или функция, заданная таблично и управляющая структурой сети по мере и смыслу поступающих сообщений, в зависимости от событий, происходящих в реальной системе. Таким образом, сеть в целом, не считая О, задается как четверка (Р, Т, А, М0). Как видно из определения гибкой сети, она определяется полностью алгебраическим пред-к ставлениемЛ.

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

В разработанном ЛП применены следующие формализмы:

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

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

3. Для синтаксического классификатора разработана формальная модель синтаксических отношений на основе сетей Петри (1), их типовая классификация и алгоритмы анализа.

Таким образом, сети Петри впервые столь широко использованы в ЛП.

Архитектуру разработанного ЛП - направленного на анализ -можно представить следующим образом (рис 2). ЛП представляет собой систему программных мо-

Рис.2. Архитектура лин-гвопроцессора

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

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

Разработанный ЛП может работать и как синтаксический анализатор, и как морфологический.

В первом случае на его вход подается предложение, а на выходе выдается его синтаксическая структура (СинтС); а во втором случае на вход подается словоформа (С), а на выходе выдается ее морфологическая структура (МорфС). При этом морфологический анализатор ЛП

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

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

1) разделение словоформ на типы;

2) сопоставление с каждым типом шаблона, задающего возможную структуру словоформы;

3) описание лексем с их морфологическими характеристиками (атрибутивный аспект);

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

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

Для моделирования и реализации атрибутивно-типовой модели применены формальный аппарат сетей Петри (1) и соответственно реляционный аппарат. В атрибутивно-типовой модели существуют следующие типы отношений: а) шаблоны; б) атрибуты.

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

Таблица 1

Лексема 1 Лексема 2 ... Лексема п

По шаблону происходит морфологический анализ. По атрибутам определяются морфологические характеристики словоформы. Атрибуты - это отношения, в левой части которых находятся лексемы, а в правой - связанные с ними морфологические характеристики (табл. 2).

Лексемы Морфолог, хар. 1 Морфолог, хар. 2 Морфолог, хар. и

Г

TLexem

<

i

Структура данных для записи морфологических характеристик в рамках данной модели имеет следующий вид:

//само слово в виде строки lexem: string-, LexS) //морфемы

morphemes: array of string-, II основа root: string-,

i//Часть речи PartofSpeech: string-, //морфологические характеристики Attributes-, array of Attribute-, Здесь тип Attribute имеет следующую структуру: //название //атрибут Name: string-, Attribute //значение . Value: string;

Существуют следующие алгоритмы морфологического анализатора:

1) морфемного анализа;

2) определения морфологических характеристик.

Все они моделируются в работе с помощью сетей Петри (1), а реализуются в терминах, близких к языкам программирования. Их взаимодействие с атрибутивно-типовой моделью можно показать на примере сетевой модели (рис.3) t2 извлечения данных с по-

мощью шаблонов (сетевая модель для атрибутов имеет схожий вид и структуру).

Описание позиций и переходов: t\ - изменяет атрибуты позиций Рх - р6 на атрибуты, соответствующие строке табли-

_ цы (заголовок - в табл.1,

Рис. 3. Сетевая модель извлечения дан- ____„

_ номер - это атрибут марке-ных с помощью шаблонов l J г

pa в pi). Переход увеличивает атрибут маркера в /?7 на 1; (2 - проверка совпадения шаблона и словоформы; h - вводит в атрибут значение о том, что словоформа не подходит под шаблон; р$ - входная позиция, маркер имеет атрибут «словоформа, разложенная на лексемы»; р7 -счетчик номера строки таблицы;

Р\ - Рб~ содержат лексемы и номер строки. Атрибуты маркера - «номер строки» и «часть речи».

Сеть Петри имеет приоритеты: приоритет h ниже приоритета th который ниже приоритета t2. Работа сети Петри: при инициализации устанавливается начальная маркировка р\ - р%, она соответствует первой строке таблицы шаблона. Срабатывание перехода t2 означает соответствие установленных маркировок атрибутам маркера в р%. Срабатывание h означает несоответствие установок маркера строкам таблицы шаблона. Срабатывание t\ означает установку атрибутов, соответствующих следующей строке таблицы шаблона.

Алгоритм извлечения данных с помощью вующий приведенной модели: ~flag:=false;

while(not(eoflJable))and not(flag)) do with Lexem,Lexs do for i:=1 to к do

if (morphemes [i)-Table [Ree]. morphemes [/]) •{ and(root=Table[Rec] .root)

then flag:=false; Rec~Rec+1; //Считываем часть речи из пути к таблице Lexem Morphs. PartofSpeech:=Path(PartofSpeech);

Составлена математическая модель нахождения морфемы с помощью сетей Петри (1). Введем следующие позиции и переходы: р\ -таблица частиц с атрибутами «номер» и «морфема»; t} - подсчет морфем; rec:=rec+1; р2 - содержит маркер с атрибутом гес, т.е длина таблицы, вначале 0; р3 - накапливает морфемы, пока они все не будут

Рис. 4.

Сетевая модель нахождения морфемы

шаблона, соответст-

пересчитаны; t2 - выбор морфемы с номером г ее. затем rec.-rec-1, создает маркер с атрибутами i и j, i=len(particle), j=len(lexem), т.е. устанавливает номера сравниваемых букв внутри морфемы и слова, равные их длинам; h - имеет предикат «;<1», т.е. проверка: указывается ли начало морфемы; р4 - маркер с атрибутами играет роль морфемы; U - получение символов из слова и морфемы как дополнительных атрибутов Ли/ маркера; р$ - входная позиция, в ней слово; /?6 - позиция для маркера с атрибутом l-particle\i\, p-, - позиция для маркера с атрибутом h=lexetn [/]; ts - имеет предикат «=», т.е. равенство букв / и h; t6 - имеет предикат «Ф», т.е. неравенство букв; р% - готовность к обработке предыдущей частицы; рд - результат проверки, что буквы равны; h - имеет предикат «если />1», выполняет /:=/-1; рю - готовность к проверке на начало слова; ts - имеет предикат «у>1». Выполняет j:=j-1; ig - имеет предикат <</<1»; рп - выходная позиция. Маркер в ри означает, что поиск завершен. Используя приведенные обозначения, математическую модель нахождения морфемы можно представить сетью, приведенной на рис.4.

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

+p{2}[(t2,p4,p5)]+p{4}[(t4,ps,p6,p7)]+p{5} [(t2,p2,p4)]+ (3)

+p{mt7,P>o)]+p№[M]+p{\0}[(t9,p4)].

Алгоритм определения морфемы просматривает словоформу с конца:

// Не найдено flag: =false-,

II берем последнюю морфему из таблицы морфем Rec\- Table. Length, morphemes Table[Rec].morpheme; /:= length (morpheme); /:= k; while (not (Table, eofj) and not (flag)) do r II сравниваем побуквенно морфему и словоформу /:= particle [/]; h.= lexem [/']; // если буква морфемы равна букве словоформы ifl=h then

ГIf i<=\ then ГУ/ найдено; возвращаем морфему J -J. flag- true

] \j-eturn (morpheme)

else if not (/'<=1) then i:=i-1; ifj>= 1 then J:=j-1;

else

if (не конец таблицы) then II берем предыдущую запись

Rec ~ Ree-1; morpheme:= Table [Rec\. Morpheme; I V. i:= length(morpheme);j - length (lexem).

Временная сложность данного алгоритма не превышает (п+\)/2 сравнений, где п - общее число морфем в базе данных.

Составлена математическая модель определения части речи с помощью ¿'-сетей Петри С=(Р. Т, А, Мо), где Р - конечное множество позиций сети, Т - конечное множество переходов сети, А -алгебраическое представление сети, М0 - начальная маркировка сети. Введем следующие позиции р и переходы t: р\ - входная позиция; г\ - позиция, решающая, является ли слово существительным; Х\ - переход, выполняющий процедуру, соответствующую Г\, р9 - выходная позиция. Появление в ней маркера свидетельствует о том, что часть речи определена, за исключением срабатывания t\, tx- установка атрибута «часть речи не определена»; рг и р5 - продолжение определения, является ли слово существительным, глаголом или наречием; г3 - позиция, решающая, глагол или нет; х3 - переход, выполняющий процедуру, соответствующую г3; г$ - позиция, решающая, является ли слово наречием; х5 - переход, выполняющий процедуру, соответствующую г5; p-i - готовность к определению, является ли слово причастием; г7 -позиция, решающая, является ли слово причастием; х7 - переход, выполняющий процедуру, соответствующую г7; />§ - готовность к определению, является ли слово прилагательным; гг - позиция, решающая, является ли слово прилагательным; х8 - переход, выполняющий процедуру, соответствующую г8; р6 - готовность к определению, является ли слово местоимением; г6 - позиция, решающая, является ли слово к местоимением; х6 - переход, выполняющий процедуру, соответст-

вующую г6; рл - готовность к определению, является ли слово числительным; г л, ~ позиция, решающая, является ли слово числительным; J х4 - переход, выполняющий процедуру, соответствующую г4;

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

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

А = р{1}г{\}[(ь,р3,р9)]+

р{2}г{2}[(х2,р9,рХ0)]+р{3} г{3} [(хг,р$,р9)] + +р{4}г{4}

[(Х4,Р2,Р9)\+Р{5}Г{5}[(Х5,Р7,Р9)]

+ р{ь}г{6}[(х6,рьр<>)] + (4) +р{1}г{1}[{хър,,р9)]+р{%}г{%) [(*8,р6,р9)]+р{10}[(/ьр9)].

Рис. 5. Сетевая модель определения части речи

Для анализа поведенческих свойств модели (рис. 5) по ее алгебраическому пред-

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

На основании приведенной математической модели разработан общий алгоритм определения части речи:

if (IsSubstantive) or (IsVerb) or (IsAdverb) else if (Is Participle) else if(IsAdjective) else if (IsPronoun) else if(IsNumeral) else if (IsGerund) else if (IsLinkWord) В данном алгоритме проверка на принадлежность словоформы той или иной части речи осуществляется на основе приоритетов. Так, приоритет причастия больше приоритета прилагательного, поэтому вначале проверяется принадлежность словоформы к причастию, и только потом - к прилагательному.

Указанные процедуры алгоритма (IsSubstantive, IsVerb, IsAdverb, IsParticiple, IsAdjective, IsPronoun, IsNumeral, IsGerund, IsLinkWord) осуществляют проверку на принадлежность конкретной части речи по шаблону и при успешном распознавании - извлечение морфологических характеристик из соответствующих данной части речи атрибутивных отношений. Таким образом, они моделируют взаимодействие

алгоритмов и атрибутивно-типовой модели.

Сложность алгоритма определения частей речи также не превышает (п+1)/2 сравнений, где п - общее число морфем.

Разработан морфологический корректор на основе гибких сетей Петри (2). При анализе и синтезе словоформ необходимо не только создать базу данных морфем и словарь основ, но и установить возможные комбинации морфем в словоформе, точнее порядок их следования и их сочетаемость друг с другом и с корнями. Эту информацию удобно представить в виде диаграммы следования лексем (рис.6), где Рх - входная позиция, содержащая словоформу; - переход, определяющий характеристики лексемы 1; Рг, р* - позиции, указывающие на возможность следования другой лексемы; Ь - переход, определяющий характеристики лексемы 2; Н - переход, определяющий характеристики лексемы 3; Ь - переходы, определяющие характеристики лексем; р5, р6, ръ р% - конечные позиции.

лексема 4

Рис.6. Фрагмент диаграммы следования на сетях Петри

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

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

1) все её лексемы (корни и морфемы) содержатся в одном из имеющихся путей;

2) порядок лексем в словоформе соответствует порядку лексем в пути, т.е. является лексикографическим.

Составленная атрибутивно-типовая модель носит сравнительно-сопоставительный характер и уникальна. Она позволяет описать поведенческие свойства лексем.

В третьей главе разрабатывается структурно-алгоритмическая модель синтаксического анализатора ЛП.

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

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

Для анализа простых предложений ЕЯ достаточно около 16 СинтО, что было выявлено путем анализа типов. Все СинтО бинарные и ориентированные. Ориентированность подразумевает то, что все отношения представлены в формате:

Длевая часть) - Х(правая часть), где X - главное слово, а V - зависимое.

Все СинтО смоделированы с помощью сетей Петри.

Представим бинарное синтаксическое отношение с помощью сетей Петри (1) на примере СинтО! (первое подлежащно-сказуемостное СинтО).

Введем следующие позиции: р\ - содержит маркер с атрибутом X, который, возможно, является сказуемым; - содержит маркер с атрибутом V, который, возможно, является подлежащим; р3 - содержит маркер, если СинтО, может быть установлено; р4 - вспомогательная позиция; и следующие переходы: t\ - проверка условия, что X - сказуемое; ¡2 - проверка условия, что У - подлежащее (существительное, местоимение или числительное).

Сеть Петри на рис.7 моделирует СинтО].

Р\ и Ра у^гРт, При наличии в позиции р\ сказуемого X срабатывает Если это происходит, то при наличии в

Рис 7 Модель СинЮ позиции Р2 подлежащего Г срабатывает г2. При этом устанавливается, что первое подлежащно-сказуемостное отношение имеет место. Аналогично моделируются остальные 15 синтаксических отношений.

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

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

г

X

SyntR J

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

//Массив, содержащий перечень СинтО, присутствующих //в данном предложении. //СинтС < SyntRelations

SyntS //Массив узлов дерева, отражающий связи между СинтО.

SyntNodes

Структура данных, в которой содержится набор СинтО, представляет собой список

SyntRelations = array of SyntR. Каждый элемент этой структуры выглядит следующим образом: '// часть речи в виде строки JPartofSpeech: string; III Характеристики в виде списка Attributes: array of string: Г// часть речи У J PartojSpeech: string; j II характеристики [attributes: array of string, II название отношения в виде строки Name: string;

Атрибутами каждого элемента СинтО (X (главное слово) или Y (зависимое слово)) являются часть речи, к которой относится X или Y в формате, принятом в данном разделе и соответствующем сокращениям в работе, а также морфологические характеристики данного элемента.

Существуют два основных алгоритма синтаксического анализатора:

1) предсинтаксического анализа;

2) формирования СинтС: а) установления СинтО; б) установления связей между СинтО.

Модель на рис. 8 устанавливает СинтО между МорфС, и МорфС; предложения, основываясь на описанном наборе СинтО, которые выступают в роли шаблонов. Как видим из схемы, алгоритм представляется в виде и-1 итераций для предложения, состоящего из п МорфС. На каждом шаге (i - номер шага) делается попытка установить СинтО

V

между МорфС, и оставшимися п-г МорфС. Проверка на возможность существования СинтО между двумя МорфС обозначается как СинтО?

п-1 шаг. МорфС,,.] МорфС„

2 шаг. МорфС2 МорфСэ... МорфС,

1 шаг. МорфС! МорфС2... МорфС, СинтО?

СинтО?

СинтО?

СинЮ?

СинтО?

V"

'и

■п

Р5

Рис.8. Схема установления СинтО Рис.9. Сетевая модель установления СинтО

Составлена математическая модель установления СинтО между МорфС, и МорфС; (рис. 9), с помощью ¿'-сетей С-(Р, Т, А, М0) где Р -конечное множество позиций сети, Т - конечное множество переходов сети, А - алгебраическое представление сети; Мо - начальная маркировка сети. Введем следующие позиции и переходы: г\ - решающая позиция, проверяющая совпадение части речи СинтОX и МорфС, и части речи СинтО. Г и МорфС,; X] - переход, соответствующий г^ рх -входная позиция; р2- выполнение условия для г\, г2 - решающая позиция, проверяющая содержание атрибутов СинтО X в МорфС, и атрибутов СинтО. У в МорфС,; х2 - переход, соответствующий г2; рг - выполнение обоих условий; р4 - невыполнение условий для Г\ или г2, р$ -выходная позиция; ^ - выполнение оператора /;=/+1, т.е. увеличить длину списка 5угйКе1аПопу; записать номер / в ЗуМЯеШИотзаписать номер в ¡ЗумЯеШйою.У; запомнить имя СинтО; 8уМЮ=Ше; г2 -проверка условия 8уп1Ю~/аЬе (установлено ли СинтО).

Теперь алгоритм установления СинтО в предложении можно записать следующим образом: //от 1 до и /ог /:=1 ю п Ао Г //от / до п

/ог/:=/ ш п с!о ( //всего СинтО 16 /ог к.=\ Ш 16 ск) И попытка установления СинтО*

1

if(SyntR?(SyntR[k]MorphS\i},MorphS[/})=true) ■ then

\ f // устанавливаем флаг SyntREstablished\-true\ // выход из цикла break,;

//если флаг установлен, то выход из цикла VV if SyntREstablished=true then break

Временная сложность данных алгоритмов не превышает (п2-п)/1 сравнений для алгоритма установления СинтО между компонентами предложения, где я - число МорфС, и С2(п2-п)/2 сравнений для алгоритма установления связей между самими СинтО, где п - число СинтО предложения, а С2 - временная константа, зависящая от числа СинтО в формальной модели синтаксиса.

С помощью сетей Петри составлены математическая модель и алгоритмы синтаксического классификатора.

Временная сложность данных алгоритмов не превышает С2х, где х - число предложений в тексте, а С2 - число типов предложений в классификации.

а '

Рис. 10. Модель параллельной обработки информации в лингвопроцессоре В разделе 3.5 представлена модель асинхронной параллельной обработки информации в ЛП с помощью сетей Петри для увеличения скорости работы ЛП (рис.10).

Если последовательная обработка информации в ЛП занимает т*[(п+1)/2]+С!*(121-11)/2+... +С1 *(?хГ1):)/2+(кг гк1)/2+... +(к21Гкх)/2+С2х сравнений, где х - число предложений в тексте, т - число слов в тексте, п - число морфем в базе данных, С; - число синтаксических отношений в базе данных, I, - число морфологических структур в /-ом предложении, к, - число СинтО в /-ом предложении, С? - число типов предложений в классификации, то для модели параллельной обработки информации для анализа текста из х предложений будет требоваться в среднем С3*[(п+1)/2]+С1*(12¡4^/2+... *(12х-1х)/2+0с2г к[)/2+... + (Т^х-к^/2+С2 сравнений, где С} - минимальное количество слов, требующееся для установления СинтО (например для русского языка оно в среднем равно 2, т.к. большинство отношений бинарные).

В четвертой главе описывается созданный на базе разработанного ЯП программный комплекс. В его состав входят: 1) морфологическая база данных; 2) морфологический анализатор; 3) морфологический корректор; 4) синтаксический анализатор; 5) синтаксический классификатор.

Данный программный комплекс был внедрен в учебный процесс на кафедре компьютерных технологий факультета информатики и вычислительной техники Чувашского государственного университета имени И.Н. Ульянова и компьютерных систем информационной безопасности Казанского государственного технического университета имени АН Туполева и активно используется в учебном процессе и научных исследованиях.

Заключение

В диссертационной работе на основе сетей Петри разработаны сетевые модели и алгоритмы для ЛП. Получены следующие основные результаты:

1 Разработан ЛП, состоящий из двух блоков: морфологического и синтаксического анализаторов, являющийся сбалансированным по сложности между формальным аппаратом описания ЕЯ, структурами данных и алгоритмами. Для этого в качестве мета-аппарата, моделирующего компоненты ЛП и их взаимодействия, были выбраны сети Петри как единственный математический аппарат, который поддерживает функциональную спецификацию, моделирование и оценку, а также обеспечивает визуальную поддержку.

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

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

3 В морфологическом анализаторе предложены и разработаны:

а) атрибутивно-типовая модель ЕЯ; с помощью сетей Петри

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

б) модели и алгоритмы морфемного анализа для нахождения морфем и основ на сетях Петри.

Временная сложность этих алгоритмов не превышает (и+1)/2 сравнений, где п - общее число морфем в базе данных.

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

4. В морфологическом корректоре предложены:

а) гибкие сети Петри для представления схем следований морфем и атрибутивно-типовой модели;

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

5. В синтаксическом анализаторе:

а) разработана структура данных для представления синтаксической структуры предложения. Она состоит из двух массивов, в одном из которых хранятся найденные в предложении синтаксические отношения, а во втором - информация о связях между СинтО (соответствует узлам древовидной структуры), сочетает в себе все преимущества древовидной структуры и не имеет ее недостатков;

предложены и разработаны:

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

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

Временная сложность данных алгоритмов не превышает (п2-п)/1 сравнений для алгоритма установления СинтО между компонентами предложения, где п - число МорфС, и С2{п2-п)/2 сравнений для алго-

ритма установления связей между самими СинтО, где п - число СинтО предложения, а С2 - временная константа, зависящая от числа СинтО в формальной модели синтаксиса.

6. В синтаксическом классификаторе разработаны:

а) схема классификации предложений по типам;

б) структура данных для ее хранения;

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

Временная сложность данного алгоритма не превышает С2х, где х - число предложений в тексте, а С2 - число типов предложений в классификации.

7. На основе сетей Петри разработана модель параллельной обработки информации в ЛП. Получены оценки временной сложности ее работы.

8. На основе спроектированных структур данных и алгоритмов разработан программный продукт на языке Object Pascal, отлаженный в среде программирования Delphi. Программа имеет развитый пользовательский интерфейс, удовлетворяет временным показателям, успешно протестирована на кафедрах компьютерных технологий факультета информатики и вычислительной техники Чувашского государственного университета имени И.Н. Ульянова и компьютерных систем и информационной безопасности Казанского государственного технического университета имени А.Н. Туполева и внедрена в учебный процесс.

Список основных публикаций

1. Желтов П. В. Алгоритм распознавания однокоренных слов и его программная реализация / П. В. Желтов, А. В. Серолапкин //1 Все-рос. конф,- фестиваль творчества студентов «Юность Большой Волги». - Чебоксары, 1999. - С.85.

2. Желтов П. В. Объектно-ориентированная модель морфологического анализа / П. В. Желтов // Материалы XXXV науч. студ. конф. / Чуваш, ун-т. - Чебоксары, 2001. - С. 127.

3. Желтов П. В. Морфологический анализатор чувашского языка / П. В. Желтов // Материалы Междунар. конф. студентов и аспирантов по фундаментальным наукам «Ломоносов - 2002». - М.,2002. -С.11.

4. Желтов П. В. Алгоритмы морфемного анализа / П. В. Желтов,

B. П. Желтов // Деп. в ВИНИТИ 31.01.02, № 198-В2002. - Чебоксары, 2002. - 9 с.

5. Желтов П. В. Атрибутивно-типовая модель лексики в сравнительно-сопоставительном аспекте / П. В. Желтов // Вестн. Чуваш, гос. ун-та. Естественные и технические науки. № 2. - Чебоксары, 2003. - С.131-136.

6. Желтов П. В. Лингвистический процессор в системах искусственного интеллекта: Конспект лекций / П. В. Желтов. - Чебоксары: Чуваш, ун-т., 2004. - 80 с.

7. Желтов П. В. Модели и алгоритмы морфологического анализа / П. В. Желтов // Деп. в ВИНИТИ 29.01.2004, № 159-В2004. - Чебоксары, 2004. - 20 с.

8. Желтов П. В. Модели и алгоритмы синтаксического анализа / П. В. Желтов // Деп. в ВИНИТИ 19.02.2004, № 291-В2004. - Чебоксары, 2004. - 15 с.

9. Желтов П. В. Сетевые модели для анализа, синтеза и коррекции словоформ / П. В. Желтов // Деп.в ВИНИТИ 19.02.2004, № 200-В2004. - Чебоксары, 2004. - 15 с.

10. Желтов П. В. Атрибутивно-типовая модель лексики / П. В. Желтов // Деп. в ВИНИТИ 07.04.04, № 571-В2004,- Чебоксары,2004,- 34 с.

11. Желтов П. В. Сетевые модели и их алгебраическое представление в лингвопроцессорах / П. В. Желтов // Деп. в ВИНИТИ 10.06.04, № 985-В2004. - Чебоксары, 2004. - 19 с.

12. Желтов П. В. Концептуальная модель лингвопроцессора / П. В. Желтов // Информационные технологии в электротехнике и электроэнергетике // Материалы V Всерос. науч.-техн. конф. - Чебоксары: Изд-во Чуваш, ун-та, 2004. - С.288-289.

13. Желтов П. В. Атрибутивно-типовая модель морфологического анализатора лингвопроцессора / П. В. Желтов // Информационные технологии в электротехнике и электроэнергетике: Материалы V Всерос. науч.-техн. конф,- Чебоксары- Изд-во Чуваш.ун-та, 2004. -

C.284-285.

14. Желтов П. В. Гибкие сети в моделировании лингвопроцессоров / П. В. Желтов // Информационные технологии в электротехнике и электроэнергетике' Материалы V Всерос науч.-техн. конф - Чебоксары: Изд-во Чуваш ун-та, 2004. - С.286-267.

15. Желтов П. В. Сравнительно-сопоставительный подход в проектировании лингвопроцессоров / П. В. Желтов // Математические

модели и их приложения: Сб. науч. тр. Вып. 6. -Чебоксары: Изд-во Чуваш ун-та, 2004. - С. 108-110."

16 Желтов П. В Алгебраическое представление сетевой модели морфологического анализатора лингвопроцессора / П. В. Желтов // Математические модели и их приложения: Сб. науч. тр. Вып. 6. -Чебоксары: Изд-во Чуваш, ун-та, 2004. - С.111-113.

17 Желтов П. В. Алгебраическое представление сетевой модели классификатора лингвопроцессора / П. В. Желтов // Математические модели и их приложения: Сб. науч. тр. Вып. 6. - Чебоксары:Изд-во Чуваш, ун-та, 2004. - С.110-111.

18. Желтов П. В. Исследование рекурсивных структур формальными методами / П. В. Желтов // Чебоксары, 2004. 20 с. Деп. в ВИНИТИ 05.01.2004, № 5-В2004. - Чебоксары, 2004. - 20 с.

19. Желтов П. В. Моделирование лингвопроцессоров сетями Петри / П. В. Желтов, В. М. Захаров // Эволюционное моделирование / Тр. Казан, городского семинара «Методы моделирования». Вып. 2. -Казань: Изд-во «Фэн», 2004. -С.90-93.

20. Захаров В. М. Моделирование обработки информации в лингво-процессорах сетями Петри / В. М. Захаров, П. В. Желтов // Препринт № 04П2. - Казань: Казан, гос. техн. ун-т., 2004. - 20 с.

Формат 60x84/16. Бумага офсетная. Печать офсетная. Печ.л. 1,5. Усл.печ.л. 1,39. Усл.кр.-отг. 1,39. Уч.-изд.л. 1,08. Тираж 100. Заказ Е1.

Типография Издательства Казанского государственного технического университета 420111 Казань, К. Маркса, 10

H

л

РНБ Русский фонд

2005-4 49102

Введение.

Глава 1. Лингвопроцессоры и формальные модели. Анализ и разработка.

1.1. Концептуальная схема и основные определения.

1.2. Анализ имеющихся лингвопроцессоров и разработка методов их моделирования.

1.3. Анализ и разработка формального аппарата.

1.4. Структурная схема разрабатываемого лингвопроцессора.

Выводы.

Глава 2. Модели и алгоритмы морфологического анализатора.

2.1. Атрибутивно-типовая модель.

2.2. Сетевые модели морфологического корректора и их алгоритмы.

2.3. Сетевые модели морфологического анализатора и их алгоритмы.

Выводы.

Глава 3. Модели и алгоритмы синтаксического анализатора.

3.1. Структура данных для синтаксического анализатора.

3.2. Синтаксические отношения.

3.3. Сетевые модели синтаксического анализатора и их алгоритмы.

3.4. Синтаксический классификатор.

3.5. Моделирование параллельной обработки информации в лингвопроцессорах.

Выводы.

Глава 4. Разработка и описание комплекса программ.

4.1. Структура программного комплекса.

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

Формальная модель естественного языка (ЕЯ) представляет собой знания о ЕЯ, формализованные средствами какого-либо математического аппарата.

Формальные модели языка, реализованные на компьютере, входят в качестве составных частей в системы машинного перевода (МП), подсистемы общения с базами данных (БД) и базами знаний (БЗ) на неограниченном ЕЯ, экспертные системы и другие информационные системы. Разработка систем, способных понимать ЕЯ, считается основной целью исследований в области искусственного интеллекта.

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

Б.Ю. Городецкого, В.М. Захарова, JI.JI. Иомдина, Киммо Кос-киньеми, О.С. Кулагиной, М.Г. Мальковского, И.А. Мельчука, Л.Г. Митюшина, А.С. Нариньяни, О.А. Невзоровой, Н.В. Перцо-ва, Э.В. Попова, Д.А. Поспелова, В.Д. Соловьева, П.И. Сосни-на, Д.Ш. Сулейманова, JI.JI. Цинмана, С.А. Шарова и других. Анализ этих работ показывает, что в современной науке существует обширный круг проблем, связанных с разработкой моделей и алгоритмов лингвопроцессоров. Особенно актуальным является целостный анализ лингвопроцессоров как технических объектов и разработка сквозной методологии моделирования, используя однотипный математический аппарат.

Объектом исследований являются лингвопроцессоры.

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

Целью работы - разработка сетевых моделей и алгоритмов для морфологического корректора и анализатора, синтаксического анализатора и классификатора ЛП.

В соответствии с поставленной целью в работе решаются следующие задачи:

1. Представление моделей лингвопроцессоров сетями Петри.

2. Разработка структур данных, моделей и алгоритмов морфологического анализатора.

3. Разработка структур данных, моделей и алгоритмов морфологического корректора (МК).

4. Разработка структур данных, моделей и алгоритмов СА.

5. Разработка структуры данных, модели и алгоритма синтаксического классификатора (СК).

6. Разработка и описание комплекса программ, реализующих ЛП.

Математический аппарат. В работе применены методы моделирования систем, аппарат сетей Петри, реляционное проектирование с помощью СУБД, теория алгоритмов и технология программирования.

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

1. В диссертации впервые широко использованы Сети Петри для моделирования блоков лингвопроцессора и самого ЛП. Предложенные модели представлены в алгебраической форме.

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

3. Смоделированы взаимодействия блоков ЛП, а также их компоненты: алгоритмы и структуры данных.

4. Лингвопроцессор исследован как система с учетом взаимосвязей между ее компонентами. Структуры данных и алгоритмы сбалансированы по сложности, что делает систему удобной и эффективной в применении.

5. С помощью сетей Петри смоделирована параллельная обработка информации в лингвопроцессоре, повышающая быстродействие системы

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

Достоверность полученных результатов оценивается на основе результатов экспериментов.

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

Реализация и внедрение резульгаоюв. Теоретические и практические результаты диссертационной работы, в том числе их программная реализация, были внедрены на кафедрах компьютерных технологий и сравнительно-сопоставительного языкознания Чувашского государственного университета. Результаты исследований используются в учебном процессе при проведении лекций и лабораторных работ по курсу «Модели и методы искусственного интеллекта». Представление моделей гибкими сетями были получено при выполнении научных исследований в рамках проекта № 98-01-03287, поддержанного Российским фондом фундаментальных исследований.

Основные положения, выносимые на защиту:

1. Сетевые модели, алгоритмы и структуры данных морфологического анализатора лингвопроцессоров.

2. Сетевые модели, алгоритмы и структуры данных морфологического корректора лингвопроцессоров.

3. Сетевые модели, алгоритмы и структуры данных синтаксического анализатора лингвопроцессоров.

4. Сетевая модель и алгоритм синтаксического классификатора.

5. Комплекс программ, реализующий разработанные модели и алгоритмы в ЛП.

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на Итоговой научной конференции «Технические науки: Сегодня, завтра» (Чебоксары, 1997), Всероссийской конференции-фестивале творчества студентов «Юность Большой Волги» (Чебоксары, 1999, 2000), Всероссийском семинаре «Проблемы прикладной лингвистики» (Пенза, 2001), Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов - 2002» (Москва, 2002), Всероссийской межвузовской научно-технической конференции «Информационные технологии в электротехнике и электроэнергетике» (Чебоксары, 2002, 2004), Казанской школе по компьютерной и когнитивной лингвистике TEL-2003 (Казань,

2003), Научной школе «Математическое моделирование, численные методы и комплексы программ» (Саранск, 2003), научной студенческой конференции (Чебоксары, 2000, 2001, 2002, 2003,

2004), Всероссийской научной конференции «Динамика нелинейных электротехнических и электронных систем» (Чебоксары, 2003), Региональной научной конференции «Волжские земли в истории и культуре России» (Чебоксары, 2003), семинаре по моделированию (Казань, 2004).

На конкурсе работ студентов и молодых ученых в 2004 г. работа была награждена дипломом Министерства образования Российской Федерации.

Публикации. По результатам выполненных исследований опубликовано 3i5 работ.

Структура и объем работы. Работа содержит введение, 4 главы, заключение, список использованной литературы, приложение. Объем работы - 171 страница.

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

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

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

В четвертой главе описывается созданный на базе разработанных алгоритмов комплекс программ. В его состав входят: 1) морфологическая база данных; 2) морфологический анализатор; 3) морфологический корректор; А) синтаксический анализатор; 5) синтаксический классификатор. Проведен анализ результатов работы лингвопроцессора, который показал, что время работы программы имеет квадратичную зависимость от количества слов анализируемого текста.

В приложении приводится интерфейс комплекса программ.

Выводы

1. Разработана структура данных для представления синтаксической структуры предложения. Эта структура данных состоит из двух массивов, в одном из которых хранятся найденные в предложении СинтО, а во втором - информация о связях между самими СинтО (соответствует узлам древовидной структуры) . Она сочетает в себе все преимущества древовидной структуры и не имеет ее недостатков.

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

3. Разработана модель на сетях Петри и алгоритм синтаксического анализа, состоящий из алгоритма установления СинтО между компонентами предложения СинтО и алгоритма установления связей между самими СинтО, временная сложность Л данных алгоритмов не превышает (п -п)/2 для алгоритма установления СинтО между компонентами предложения, где л -число МорфС, и С2(п2-п)/2 для алгоритма установления связей между самими СинтО, где л - число СинтО предложения.

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

5. С помощью сетей Петри разработана модель параллельной обработки информации в лингвопроцессоре. Если последовательная обработка информации в ЛП занимает т*[ (п+1) /2] +CS (l2i~h) /2+.+С!* (12х-Ы /2+ (к2,-^) /2+.Л (к2х-кх)/2+С2Х сравнений, где х - число предложений в тексте, т -число слов в тексте, п - число морфем в базе данных, Ci -число синтаксических отношений в базе данных, li - число морфологических структур в i-ом предложении, ki - число СинтО в i-ом предложении, С2 - число типов предложений в классификации, то для модели параллельной обработки информации для анализа текста из х предложений будет требоваться в среднем С3*[ (п+1)/2]+CS (l^-li)/2+.+С!* (12х-1К)/2+(к21-к1)/2+.+ (к2х-кх)/2+С2 сравнений, где С3 минимальное количество слов, требующееся для установления СинтО (например для русского языка оно в среднем равно 2, т.к. большинство отношений бинарные).

Глава 4.Разработка и описание комплекса программ

4.1. Структура программного комплекса

При разработке программного комплекса было решено исходить из таких принципов, как:

1) максимальная визуальная приближенность структур данных и алгоритмов программного комплекса к их описанию в главах 2 и 3;

2) простота и прозрачность структур комплекса программ и составляющих его модулей;

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

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

5) учет пожеланий сотрудников филологического факультета ЧГУ, работающих на кафедре сопоставительного и прикладного языкознания, самостоятельно изучивших программирование на языке Object Pascal в среде программирования Delphi и планирующих использовать разработанный комплекс программ в учебной и научной деятельности.

С учетом вышесказанного языком программирования был выбран Object Pascal, получивший широкое распространение не только среди программистов, но и среди представителей гуманитарных наук, интересующихся программированием, а в качестве программной среды для отладки комплекса программ был вы-# бран компилятор Delphi 6 фирмы Borland.

Среда программирования Delphi позволяет реализовывать современный графический интерфейс для демонстрации возможностей программного комплекса и является высоконадежной.

Программный комплекс был налажен с помощью компилятора Delphi б фирмы Borland и протестирован в операционных системах Windows 95, Windows 96, Windows NT 3.51, Windows NT 4.0, Windows ME, Windows 2000 и Windows XP.

Программный комплекс состоит из следующих модулей:

1) модуль, содержащий структуры данных морфологии (Unit MorphStruct);

2) модуль, содержащий алгоритмы морфемного анализа (Unit MorphemAlgorithms);

3) модуль, содержащий алгоритмы определения морфологических характеристик (Unit MorphAlgorithms);

4) модуль, содержащий структуры данных синтаксиса (Unit SyntStruct);

5) модуль, содержащий алгоритмы синтаксиса (Unit Synt-Algorithms);

6) модуль, содержащий алгоритм классификации предложений по типам (Unit Classification);

7) модуль пользовательского интерфейса (Unit Unitl) Морфологическая база знаний была подробно описана в разделе 2.2, синтаксическая база знаний - в разделе 3.2. Модуль

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

Рис .4.1. Схема взаимодействия модулей

4.1.1. Модуль MorphStruct Этот модуль содержит структуры данных, переменные и связанные с ними функции.

Интерфейс модуля(Interface). Типы данных.

Заключение

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

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

ЕЯ, а также используется как формальный аппарат описания ЕЯ, для создания формальных моделей

2. Разработаны принципы сравнительно - сопоставительного подхода к созданию формальных моделей ЕЯ и проектированию лингвопроцессоров, позволяющий легко объединять созданные ЛП для разных языков в систему МП.

3. Разработан ЛП состоящий из двух блоков: морфологического и синтаксического анализаторов.

4. В морфологическом анализаторе разработаны: а) атрибутивно-типовая модель ЕЯ; с помощью сетей Петри сформулирована ее взаимодействие с алгоритмами. Данная модель реализована с помощью реляционного аппарата в виде мор* фологической базы данных. б) модели и алгоритмы морфемного анализа для нахождения префиксов, суффиксов, аффиксов, частиц, окончаний на сетях Петри.

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

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

6. В синтаксическом анализаторе разработаны: а) структура данных для представления синтаксических структур предложения. Она состоит из двух массивов, в одном из которых хранятся найденные в предложении синтаксические отношения, а во втором информация о связях между СинтО (соответствует узлам древовидной структуры), сочетает в себе все преимущества древовидной структуры и не имеет ее недостатков. б) модель представления синтаксических отношений в виде сети Петри, структура данных для записи СинтО и записи набора из 16 СинтО, позволяющий разложить любое простое предложение на его синтаксические составляющие. в) модель и аппарат анализа синтаксической структуры на сетях Петри, состоящий из алгоритма установления СинтО между компонентами предложения и алгоритма установления связей между самими СинтО, объединяющий их в синтаксическую структуру.

Временная сложность данных алгоритмов не превышает (п2-п)/2 сравнений для алгоритма установления СинтО между компонентами предложения, где л - число МорфС, и С2(п2-п)/2 сравнений для алгоритма установления связей между самими СинтО, где п - число СинтО предложения.

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

1. Апресян Ю.Д., Богуславский И.М., Иомдин JT.J1. и др. Лингвистический процессор для сложных информационных систем.-М.: Наука, 1992. 256 с.

2. Апресян Ю.Д. Образ человека по данным языка: попытка системного описания // Вопросы языкознания. М.: Наука, 1995, №1.

3. Васильев В. В., Кузьмук В. В. Сети Петри, параллельные алгоритмы и модели мультипроцессорных систем. Киев, 1990. 216 с.

4. Валькман Ю.Р. Интеллектуальные технологии исследователь ского проектирования: формальные системы и семиотические модели. Киев: Port-Royal, 1998. 250 с.

5. Вентцель Е.С. Исследование операций: Задачи, принципы, методология. 2-е изд. М., 1988. 208 с.

6. Вудс В.А. Сетевые грамматики для анализа естественного языка II Кибернетический сборник. М., 1976. Вып. 13. - С. 121-158.

7. Гатиатуллин А.Р. Интегрированный программно-информацион ный комплекс «Морфема» // Сборник трудов Международного семинара но компьютерной лингвистике и ее приложениям «Диалог-98». Казань, 1998. - С.453-466.

8. Гатиатуллин А.Р. Реализация синтаксического генератора предложений татарского языка // Сборник трудов Математического центра имени И.И. Лобачевского. Т.4. Компьютерная лингвистика Казань, 1999. - С.41-50.

9. Григорьев А.В. Представление генетических алгоритмов се тями Петри в задаче размещения: Автореф. дис. . канд. техн. наук // Чувашский гос. ун-т. Чебоксары, 2002. 22 с.

10. Димитриев А.П. Стохастическая оптимизация в задаче размещения на сетях Петри: Автореф. дис. . канд. техн. наук // Чувашский гос. ун-т. Чебоксары, 2001. 23 с.

11. Десрочерс А. А., Ал-Джар Р. Й. Приложения сетей Петри в производственных системах: Моделирование, управление и анализ производительности. Нью-Йорк, 1995. 270 с.

12. Желтов П.В., Желтов В.П. Разработка лингвопроцессора для анализа естественного языка. Вестник Чувашского государственного университета. Естественные и технические науки. № 2. Чебоксары, 2002.

13. Желтов П.В. Лингвистический процессор в системах искусственного интеллекта. Конспект лекций. Чуваш, гос.ун-т.-Чебоксары. 2004.

14. Желтов П.В. Концептуальная модель лингвопроцессора. Информационные технологии в электротехнике и электроэнергетике. Материалы V Всероссийская научно-техническая конференция, Чебоксары, Изд-во Чуваш, ун-та, 2004. С.288-289.

15. Желтов П.В. Сравнительно-сопоставительный подход в проектировании лингвопроцессоров. Математические модели и их приложения: Сб. науч. Тр. Вып. 6 Чебоксары: Изд-во Чуваш, ун-та. 2004. 2 с.

16. Желтов П.В, Захаров В.М. Моделирование лингвопроцессоров сетями Петри // Эволюционное моделирование / Труды Казанского городского семинара «Методы моделирования». Вып. 2. Казань: Изд-во «Фэн», 2004. 4 с.

17. Желтов П.В., Желтов В.П. О различных представлениях графа. Технические науки: Сегодня и завтра: Тезис докладов юбилейной итоговой научной конференции. Чебоксары: Изд-во Чуваш. ун-та, 1997. 2с.

18. Желтов П.В. Атрибутивно-типовая модель лексики в сравнительно-сопоставительном аспекте. Вестник Чувашского государственного университета. Естественные и технические науки. № 2. Чебоксары, 2003.

19. Желтов П.В. Атрибутивно-типовая модель лексики. Чуваш, гос. ун-т. Чебоксары. Деп. в ВИНИТИ 07.04.04 № 571-В2004.

20. Желтов П.В Атрибутивно-типовая модель лексики. Математика в высшем образовании. Тезисы докладов 12-й международной конференции. Чебоксары: Изд-во Чуваш, ун-та. 2004. С.124.

21. Желтов П.В. Морфологический анализатор чувашского языка. Материалы Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2002», М., 2002 .

22. Желтов П.В. Объектно-ориентированная модель морфологического анализа. Материалы XXXV научной студенческой конференции/ Чуваш, гос. ун-т, Чебоксары, 2001 .

23. Желтов П.В., Желтов В.П. Алгоритмы морфемного анализа. Чуваш, гос. ун-т. Чебоксары, 2002. - 9с.: Деп. в ВИНИТИ, 31.01.02 №198-В2002.

24. Желтов П.В., Желтов В.П. Объектно-ориентированное программирование и морфологический анализ.Чуваш.гос.ун-т. Чебоксары, 2001, Деп. в ВИНИТИ №1056-В2001.

25. Желтов П.В., Желтов В.П. Программный морфологический анализатор. Чуваш, гос.ун-т. Чебоксары, 2001. - 27 с:. Деп. в ВИНИТИ №483-В2001.

26. Желтов П.В. Модели и алгоритмы морфологического анализа Чуваш, гос.ун-т.-Чебоксары.2004.-20 с.-Рус.- Деп.в ВИНИ-ТИ.29.01.2004,№159=В2004

27. Желтов П.В. Алгебраическое представление сетевой модели морфологического анализатора лингвопроцессора. Математические модели и их приложения: Сб. науч. Тр. Вып. б Чебоксары: Изд-во Чуваш, ун-та. 2004. 2 с.

28. Желтов П.В. Алгоритм распознавания однокоренных слов и его программная реализация. Наука, творчество, информация: Материалы XXXIII научной студенческой конференции / Чуваш, ун-т, Чебоксары, 1999 г. 1 с.

29. Желтов П.В., Серолапкин А.В. Алгоритм распознавания однокоренных слов и его программная реализация, I Всероссийская конференция фестиваль творчества студентов «Юность большой Волги», Чебоксары , 1999. 1с.

30. Желтов П.В. Программный лексический анализатор, Материалы XXXIV научной студенческой конференции/ Чуваш, ун-т, Чебоксары, 2000. 1 с.

31. Желтов П.В., Серолапкин А.В. Программный лексический анализатор. II Всероссийская конференция-фестиваль творчества студентов "Юность Большой Волги", Чебоксары , 2000. 1с.

32. Желтов П.В., Желтов В.П. Структурно-функциональные модели лексики. Материалы XXXVII научной студенческой конференции /Чуваш, ун-т, Чебоксары, 2003.

33. Желтов П.В. Сетевые модели для анализа, синтеза и коррекции словоформ. Чуваш. гос.ун-т.-Чебоксары. Деп.в ВИНИТИ,19.02.2004,№200-В2004.

34. Желтов П.В., Желтов В.П., Димитриев А.П. Представление словоформ с помощью сетей Петри. Материалы V Всероссийской научной конференции «Динамика нелинейных дискретных электротехнических и электронных систем». Чебоксары: Изд-во Чуваш, ун-та, 2003.

35. Желтов П.В. Гибкие сети в моделировании лингвопроцессо-ров. Информационные технологии в электротехнике и электроэнергетике. Материалы V Всероссийская научно-техническая конференция, Чебоксары, Изд-во Чуваш, ун-та, 2004. С.286-267.

36. Желтов П.В., Желтов В.П. Петри-машина, предназначенная для обработки алгоритмов. Материалы V Всероссийской научной конференции «Динамика нелинейных дискретных электротехнических и электронных систем». Чебоксары: Изд-во Чуваш, ун-та, 2003.

37. Желтов П.В. Проблемы синтаксического анализа русского языка. Материалы XXXVI научной студенческой конференции/ Чуваш. ун-т, Чебоксары, 2002 .1с.

38. Желтов П.В. Синтаксический анализатор простых предложений русского языка. Проблемы прикладной лингвистики: Сборник материалов Всероссийского семинара. Часть I. Пенза, 2001. 1с.

39. Желтов П.В. Модели и алгоритмы синтаксического анализа Чуваш, гос.ун-т.-Чебоксары. Деп.в ВИНИТИ, 19.02.2004,№291-В2004.

40. Желтов П. В. Алгебраическое представление сетевой модели классификатора лингвопроцессора. Математические модели и их приложения: Сб. науч. Тр. Вып. 6 Чебоксары: Изд-во Чуваш, ун-та. 2004. 2 с.

41. Желтов П.В. Сетевые модели и их алгебраическое представление в лингвопроцессорах. Чуваш, ун-т. Чебоксары,2004.19 с. Деп. в ВИНИТИ. 10.06.04, № 985-В2004.

42. Желтов В.П., Желтова JI. В. Моделирование систем и дискретные математические модели: Текст лекций. Чебоксары, 1995. 124 с.

43. Желтов П.В., Губанов А.Р. Опыт составления программ по русскому языку. Материалы XXXVI научной студенческой конференции/ Чуваш. Ун-т, Чебоксары, 2002. 1 с.

44. Желтов П.В., Желтов В.П. Создание региональных компьютерных фондов. Материалы региональной научной конференции «Волжские земли в истории и культуре России» (г.Чебоксары, 20-21 июня 2003 г.). Москва: Вуз и школа, 2003. 5 с. (стр.168-172).

45. Желтов П.В. Исследование рекурсивных структур формальными методами Чуваш, гос.ун-т.-Чебоксары. 2004.-20 с.-Рус.-Деп.в ВИНИТИ.05.01.2004,№5-В2004

46. Захаров В.М., Желтов П.В. Моделирование обработки информации в лингвопроцессорах сетями Петри. Казань, 2004. 20 с. (Препринт / Изд-во Казан, гос. техн. ун-та. Казань, 04П2) .

47. Кибрик А.Е. Для чего нужны формальные модели языка ? // Сборник трудов Формально-логические и компьютерные модели языков в рамках российской конференции по искусственному интеллекту КИИ-9б Казань: Изд-во "Фэн". -1996. -С.3-5.

48. Кишиневский М.А., Таубин А.Р., Цирлин B.C. Сети Петри и анализ переключательных схем // Кибернетика. 1982. №4.

49. Котов В.Е. Алгебра регулярных сетей Петри // Кибернетика. 1980. №5.

50. Котов В.Е. Сети Петри. М., 1984. 160 с.

51. Кузьмук В. В. Применение модифицированных Е-сетей для построения параллельных алгоритмов // Докл. АН УССР. Сер.А. 1985. № 8. С. 65-68.

52. Кулагина О.С. Исследования по машинному переводу. М. Наука. 1979. 320 с.

53. Кутанов А. Т., Юдицкий С. А. Комплекс моделей компьютеризированной системной инженерии: CASE-технологии // Автоматика и телемеханика. 1995. № 1. С. 174 187.

54. Лавров С.С. Архитектура баз знаний // Программное обеспечение вычислительных комплексов новой архитектуры. Новосибирск НФ ИТН и ВТ АН СССР, 1986.-С.3-13.

55. Лескин А. А., Мальцев П. А., Спиридонов А. М. Сети Петри в моделировании и управлении. Л., 1989. 133 с.

56. Мальковский М.Г. Диалог с системой искусственного интеллекта. -М.: Изд-во МГУ, 1985.-214 с.

57. Математическое моделирование технологических процессов и метод обратных задач в машиностроении / А.Н. Тихонов, В.Д. Кальнер, В.Б. Гласко. М., 1990. 264 с.

58. Мурата Т. Сети Петри: Свойства, анализ, приложения // Тр. ин-та инженеров по электротехнике и радиоэлектронике: Пер. с англ. Т. 77. 1989. № 4. С. 41 85.

59. Нариньяни А.С. Автоматическое понимание текста новая перспектива // В сб. Трудов 130. -С. 203-208.

60. Нариньяни А.С. Искусственный интеллект: стагнация или новая перспектива? -Пущине: РАЙИ//В сб. Трудов в 3-х томах 133. T.I. С. 15-29.

61. Никонов В.В., Подгурский Ю.Е. Применение сетей Петри // Зарубеж. радиоэлектроника. 1986. № 11. С. 17-37.

62. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М., 1984. 264 с.

63. Прос Дж.-М., Ксай Кс. Сети Петри: Средство для разработки и управления производственными системами. Мец; Нью-Йорк, 1996. 200 с.

64. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: «Мир», 1980. 476 с.

65. Розенблюм Л.Я. Сети Петри // Техническая кибернетика. 1983. № 5. С. 12 40.

66. Руднев В. В. Словарные сети Петри // Автоматика и телемеханика. 1987. № 4. С. 102 108.

67. Русская грамматика М.: Наука, 1980. Т. 1: Фонетика. Фонология. Ударение. Интонация. Словообразование. Морфология. 783 с. Т 2: Синтаксис. 709 с.

68. Рыжов В.А. Динамичные сети Петри. М., 1988. 24 с.

69. Соловьев В.Д.Запоминание порядка слов в предложе-нии//Когнитивная и компьютерная лингвистика. Казань :Изд.КГУ, 1994, 49-56.

70. Соснин П.И. Человеко-компьютерная диалогика.- Ульяновск: Ульяновский государственный технический университет, 2001.285 с.

71. Сулейманов Д.Ш., Гатиатуллин А.Р. Формальное описание значений аффиксальных морфем // Сборник трудов Международного семинара по компьютерной лингвистике и ее приложениям «Диалог-98». Казань, 1998.-С.713-725.

72. Сулейманов Д.Ш., Гатиатуллин А.Р. Интегрированный программно-информационный комплекс «Морфема» // Сборник трудов шестой национальной конференции с международным участием КИИ-98 в трех томах. T.I. Пущине, 1998. -С.208-214.

73. Сулейманов Д.Ш., Гатиатуллин А.Р. Синтаксический анализатор предложений татарского языка // Сборник трудов Математического центра имени Н.И. Лобачевского. Т.4. Компьютерная лингвистика. Казань, 1999. - С.111-126.

74. Таль А. А., Юдицкий С. А. Иерархия и параллелизм в сетях Петри: Сложные автоматные сети с параллелизмом // Автоматика и телемеханика. 1982. № 7.С. 113-123; № 9. С. 83-89.

75. Татарская грамматика. В 3-х томах. Казань: Татарское кн. изд-во, 1993.

76. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М., 1984. 496 с.

77. Хан А.А., Хура Г.С., Сингх X., Нанда Н.К. Представление логических операций уравнениями состояний на основе сети Петри / Тр. инженеров ин-та электротехники и радиоэлектроники. Т.69. 1981. № 4. С.93-95.

78. Хомский Н. Синтаксические структуры // Пер. с англ.: Chomsky N. Syntactic Structures в сб. «Новое в лингвистике», вып.2. М.: Изд-во ин.лит., 1962.

79. Шаров С.А. Средства компьютерного представления лингвистической информации. URL: http//nl-web/.

80. Ширяев В. Д. Основы алгоритмизации. Учеб. пособие. Саранск, 1993.

81. Юдицкий С.А., Владиславлев П.Н. Предпроектное моделирование функционирования организационных систем. М.: ООО Издательство «Научтехлитиздат», 2004. 120 с.

82. Evan L. Antworth.PC-KIMMO: A two-level processor for Morphological analisys.- SUMMER INSTITUTE OF LINGUISTICS: Occasional Publications in Academic Computing, 1990 (опубликовано в Интернете, www.sil.org).

83. Khodabandeh A. Introduction to Artifex and its Petri Nets. Chech., 1999.

84. Petri C. A. General net theory Proc. Jt. IBM Seminar, Univ. Newcastle Upon Tyne. Set. 1976.

85. Simulation modeling and analysis / Averill M. Law, W. David Kelton. 2nd ed. p. cm. (McGraw-Hill series in industrial engineering and management science), 1991.

86. Victor H. Yngve, The depth hypothesis// Proceedings of symposia in applied mathematics, vol XII (русский перев.: Новое в зарубежной лингвистике, Вып. 4 М.: Прогресс, 1965 - с. 126-138).

87. Edward L. Keenan, Bernard Comrie. Noun phrase accessibility and universal grammar. In "Linguistic Inquiry", Vol. 8, no 1, 1997, p. 63 -98 (русский перев.: Новое в зарубежной лингвистике, вып. 11 - М.: Прогресс, 1982).