Содержание к диссертации
Введение
Глава 1 . Лингвопроцессоры и формальные модели. Анализ и разработка 11
1.1. Концептуальная схема и основные определения 11
1.2. Анализ имеющихся лингвопроцессоров и разработка методов их моделирования 15
1.3. Анализ и разработка формального аппарата 22
1.4. Структурная схема разрабатываемого лингвопроцессора .41
Выводы 42
Глава 2. Модели и алгоритмы морфологического анализатора 44
2.1. Атрибутивно-типовая модель 44
2.2. Сетевые модели морфологического корректора и их алгоритмы 57
2.3. Сетевые модели морфологического анализатора и их алгоритмы 69
Выводы 98
Глава 3. Модели и алгоритмы синтаксического анализатора 101
3.1. Структура данных для синтаксического анализатора 101
3.2. Синтаксические отношения 105
3.3. Сетевые модели синтаксического анализатора и их алгоритмы 112
3.4. Синтаксический классификатор 126
3.5. Моделирование параллельной обработки информации в лингвопроцессорах 131
Выводы 135
Глава 4. Разработка и описание комплекса программ..137
4.1. Структура программного комплекса 137
Заключение 154
Список использованной литературы 158
Приложение 168
- Анализ имеющихся лингвопроцессоров и разработка методов их моделирования
- Структурная схема разрабатываемого лингвопроцессора
- Сетевые модели морфологического анализатора и их алгоритмы
- Сетевые модели синтаксического анализатора и их алгоритмы
Введение к работе
Актуальность темы. В связи с развитием вычислительной техники интенсивно ведутся работы по созданию различных систем искусственного интеллекта. Эти системы призваны смоделировать некое подобие человеческого мышления. А так как человеческое мышление тесно связано с речью, то создание формальных моделей языка призвано играть в данном направлении важную роль.
Формальная модель естественного языка (ЕЯ) представляет собой знания о ЕЯ, формализованные средствами какого-либо математического аппарата.
Формальные модели языка, реализованные на компьютере, входят в качестве составных частей в системы машинного перевода (МП), подсистемы общения с базами данных (БД) и базами знаний (БЗ) на неограниченном ЕЯ, экспертные системы и другие информационные системы. Разработка систем, способных понимать ЕЯ, считается основной целью исследований в области искусственного интеллекта.
Общим для всех этих систем является наличие лингвопро-цессора (ЛП), т.е. преобразователя, осуществляющего анализ текста на естественном языке, переход к его формальному представлению и синтез - построение текста по его представлению. Как правило, лингвистические процессоры содержат морфологический и синтаксический блоки анализа и синтеза. Причем задача анализа гораздо сложнее задачи синтеза, а лингвопроцессоры, настроенные на анализ, обратимы в направлении синтеза, поэтому создание анализаторов является актуальным. Из работ, выполненных в России и за рубежом, наиболее интересными являются исследования Ю.Д. Апресяна, И.М. Богуславского, Р.Г. Бухараева, Ю.Р. Балькмана, В.А. Вудса,
В.Ю. Городецкого, В.М. Захарова, Л.Л. Иомдина, Киммо Кос-киньеми, О.С. Кулагиной, М.Г. Мальковского, И.А. Мельчука, Л.Г. Митюшина, А.С. Нариньяни, О,А. Невзоровой, Н.В. Перцо-ва, Э.В. Попова, Д.А. Поспелова, В.Д. Соловьева, П.И. Соснина, Д.Ш. Сулейманова, Л,Л. Цинмана, С.А. Шарова и других. Анализ этих работ показывает, что в современной науке существует обширный круг проблем, связанных с разработкой моделей и алгоритмов лингвопроцессоров. Особенно актуальным является целостный анализ лингвопроцессоров как технических объектов и разработка сквозной методологии моделирования, используя однотипный математический аппарат.
Объектом исследований являются лингвопроцессоры.
Предметом исследований являются структуры, модели и алгоритмы морфологического и синтаксического анализаторов ЛП.
Целью работы - разработка сетевых моделей и алгоритмов для морфологического корректора и анализатора, синтаксического анализатора и классификатора ЛП.
В соответствии с поставленной целью в работе решаются следующие задачи:
Представление моделей лингвопроцессоров сетями Петри.
Разработка структур данных, моделей и алгоритмов морфологического анализатора,
Разработка структур данных, моделей и алгоритмов морфологического корректора (МК).
Разработка структур данных, моделей и алгоритмов СА.
Разработка структуры данных, модели и алгоритма синтаксического классификатора {СК}.
Разработка и описание комплекса программ, реализующих ЛП.
Математический аппарат. В работе применены методы моделирования систем, аппарат сетей Петри, реляционное проектирование с помощью СУБД, теория алгоритмов и технология программирования.
Научная новизна.
В диссертации впервые широко использованы Сети Петри для моделирования блоков лингвопроцессора и самого ЛП. Предложенные модели представлены в алгебраической форме.
Предложены гибкие сети для моделирования схем следования, сетевые модели функционирования лингвопроцессора и его компонент на основе сетей Петри.
Смоделированы взаимодействия блоков ЛП, а также их компоненты: алгоритмы и структуры данных.
4. Лингвопроцессор исследован как система с учетом
взаимосвязей между ее компонентами. Структуры данных и алго
ритмы сбалансированы по сложности, что делает систему удоб
ной и эффективной в применении.
С помощью сетей Петри смоделирована параллельная обработка информации в лингвопроцессоре, повышающая быстродействие системы
На основе полученных моделей и алгоритмов разработан комплекс программ, реализующий ЛП, состоящий из морфологического анализатора и корректора, а также синтаксического анализатора и классификатора.
Достоверность полученных результатов оценивается на основе результатов экспериментов.
Практическая ценность работы. Сетевые модели и алгоритмы, предложенные в диссертации, позволяют решать задачи разработки пакетов прикладных программ для автоматизации обработки текстов на ЕЯ, в частности корректоров, помогающих
пользователям обнаруживать и исправлять ошибки в ЕЯ-тексте. Атрибутивно-типовые модели, разработанные в диссертационной работе, обеспечивают компактное хранение информации, быстрый доступ к данным. Гибкие сети и разработанные на их основе схемы следования делают возможной работу ЛП при неполных, нечетких и недостоверных данных. Созданные формальные модели ЕЯ могут быть положены в основу вопросно-ответных и экспертных систем. Морфологическая база данных может быть использована как информационно-справочная база для построения двуязычных ЛП. Полученные в диссертации результаты способствуют расширению сферы использования русского языка, как языка компьютерных технологий.
Реализация и внедрение результатов. Теоретические и практические результаты диссертационной работы, в том числе их программная реализация, были внедрены на кафедрах компьютерных технологий и сравнительно-сопоставительного языкознания Чувашского государственного университета. Результаты исследований используются в учебном процессе при проведении лекций и лабораторных работ по курсу «Модели и методы искусственного интеллекта». Представление моделей гибкими сетями были получено при выполнении научных исследований в рамках проекта № 98-01-03287, поддержанного Российским фондом фундаментальных исследований.
Основные положения, выносимые на защиту:
Сетевые модели, алгоритмы и структуры данных морфологического анализатора лингвопроцессоров.
Сетевые модели, алгоритмы и структуры данных морфологического корректора лингвопроцессоров.
Сетевые модели, алгоритмы и структуры данных синтаксического анализатора лингвопроцессоров.
Сетевая модель и алгоритм синтаксического классификатора.
Комплекс программ, реализующий разработанные модели и алгоритмы в ЛП.
Апробация работы. Основные положения и результаты работы докладывались и обсуждались на Итоговой научной конференции «Технические науки: Сегодня, завтра» (Чебоксары, 1997), Всероссийской конференции-фестивале творчества студентов «Юность Большой Волги» (Чебоксары, 1999, 2000), Всероссийском семинаре «Проблемы прикладной лингвистики» (Пенза, 2001), Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов - 2002» (Москва, 2002), Всероссийской межвузовской научно-технической конференции «Информационные технологии в электротехнике и электроэнергетике» (Чебоксары, 2002, 2004), Казанской школе по компьютерной и когнитивной лингвистике TEL-2003 (Казань, 2003), Научной школе «Математическое моделирование, численные методы и комплексы программ» (Саранск, 2003), научной студенческой конференции (Чебоксары, 2000, 2001, 2002, 2003, 2004), Всероссийской научной конференции «Динамика нелинейных электротехнических и электронных систем» (Чебоксары, 2003}, Региональной научной конференции «Волжские земли в истории и культуре России» (Чебоксары, 2003), семинаре по моделированию (Казань, 2004)..
На конкурсе работ студентов и молодых ученых в 2004 г. работа была награждена дипломом Министерства образования Российской Федерации.
Публикации. По результатам выполненных исследований опубликовано 35 работ.
Структура и объем работы. Работа содержит введение, 4 главы, заключение, список использованной литературы, приложение. Объем работы - 171 страница.
В первой главе рассмотрена концептуальная модель лин-гвопроцессора как системы. Сделан вывод о том, что проанализированные лингвопроцессоры, несмотря на все их достоинства, не сбалансированы по сложности. Предложены сети Петри и гибкие сети как аппарат для построения моделей и как аппарат для моделирования взаимодействия компонентов системы, таких как формальные модели, структуры данных и алгоритмы, т. е. как мета-аппарат. Представлена архитектура разработанного лингвопроцессора - направленного на анализ.
Вторая глава посвящена разработке структурно-алгоритмической модели морфологического анализатора. Она состоит из атрибутивно-типовой модели, структур данных и алгоритмов анализа. Для моделирования и реализации атрибутивно-типовой модели применены формальный аппарат сетей Петри и реляционный аппарат соответственно В атрибутивно-типовой модели существуют следующие типы отношений: а) шаблоны; б) атрибуты. Основные понятия сетей Петри отображены в соответствующие термины и понятия лингвопроцессора.
В третьей главе излагается структурно-алгоритмическая модель синтаксического анализатора лингвопроцессора. Основной задачей синтаксического анализатора лингвопроцессора является преобразование морфологической структуры предложения, поступающей с выхода морфологического блока, в синтаксическую структуру. Так как морфологическая структура предложения состоит из морфологической структуры отдельных словоформ, то переход от морфологической структуры предложения к его синтаксической структуре осуществляется путем установле-
ния синтаксических связей между морфологической структуры слов и между самими связями. При этом морфологические структуры отдельных словоформ служат для установления этих связей. В работе эти связи представлены синтаксическими отношениями.
В четвертой главе описывается созданный на базе разработанных алгоритмов комплекс программ. В его состав входят: 1) морфологическая база данных; 2) морфологический анализатор; 3) морфологический корректор; 4) синтаксический анализатор; 5) синтаксический классификатор. Проведен анализ результатов работы лингвопроцессора, который показал, что время работы программы имеет квадратичную зависимость от количества слов анализируемого текста.
В приложении приводится интерфейс комплекса программ.
Анализ имеющихся лингвопроцессоров и разработка методов их моделирования
Б настоящее время разработано большое число лингвопроцессоров для анализа различных языков, однако большинство из них являются зарубежными и коммерческими, поэтому они нигде подробно не описаны и нет возможности провести их анализ.
Что же касается научных разработок, то наибольшую известность получили две из них: ЛП "ЭТАП" для ЕЯ группы Ю. Д. Апресяна, разработанный в России и примененный для англорусского машинного перевода и лингвопроцессорная оболочка PC-KIMMO, разработанная группой специалистов из Summer Institute of Linguistics, США, под руководством Гарри Симмонса на основе формального аппарата, разработанного финским ученым Kimmo Koskenniemi [1-2,85]. Первый ЛП подробно описан в литературе и настроен на английский и русский языки, но не доступен всем желающим ввиду его коммерческой направленности, второй является открытым и помещен в Интернете [1-2] .
В лингвопроцессоре для русского языка, разработанном группой ученых под руководством Ю.Д. Апресяна в 1992 году, реализованы модели трех уровней: морфологического, синтаксического, семантического [1-2]. Прикладным аспектом данного лингвопроцесора является машинный перевод с русского на английский и наоборот, а также общение с БД на ЕЯ. Он представляет собой мощный комплекс программ и может быть применен во многих прикладных системах. Группой Ю.Д. Апресяна проведен всеобъемлющий анализ структуры русского языка и разработаны универсальные модели.
Разработанный формальный аппарат удобен как для лингвистов так и для программистов. Он обладает достаточной мощностью и позволяет создавать формальные модели практически любых ЕЯ. Аппарат представляет собой систему специальных правил и нотаций. Недостатком данного формального аппарата является то, что он использует файловое представление и для извлечения правил и данных требуются специальные трансляторы, извлекающие информацию из файлов и преобразующие ее в надлежащий вид. Данный ЛП насчитывает большое число словарей и файлов и более подходит для больших научно-коммерческих групп, так как его трудно заполнить одному или нескольким специалистам. Исходные тексты, согласно литературе написаны на языке PL/1 [1-2].
Что же касается PC-KIMMO, то он является достаточно простым инструментарием, предоставляющим возможность заполнения его данными практически любого языка. Он состоит из трех блоков: фонологического, реализующего фонологические и орфографические правила; морфологического и синтаксического и использует в качестве формального аппарата специальную систему правил вывода. Система правил для описания лингвистических знаний достаточно проста и не требует специальной математической подготовки. Исходные тексты написаны на языке C++. Его недостатком является сложность формальной модели ввиду того, что ограниченность и простота системы правил вывода порождает достаточно сложные записи и теряется их наглядность .
Обобщая вышесказанное, можно сделать вывод о том, что проанализированные ЛП несмотря на все их достоинства, не сбалансированы по сложности. Поэтому актуальной является задача разработки оптимизированного ЛП, в котором достаточно простыми и наглядными были бы как структуры данных и формальный аппарат, так и алгоритмы обработки. В качестве wполигона" для тестирования ЛП часто выбираются системы МП.
При построении систем машинного перевода актуальна стыковка лингвопроцессоров для разных языков. Этой проблеме посвящено большое количество исследований, проведенных для языков одинакового строя (в основном флективных) [1-2,53]. В основном эти исследования проводились для европейских языков, имеющих схожую морфологию (флективную), близкий строй предложения. Из отечественных разработок широко известными являются англо-русская система машинного перевода группы Ю.Д. Апресяна и система машинного перевода с французского на русский группы О.С. Кулагиной [1-2,53]. Русский, английский и французский имеют схожие во многом морфологию и синтаксис.
Казалось бы, для решения данной задачи достаточно построить русский и английский блоки, а затем осуществить их стыковку. Причем, согласно, это было сделано так, что входной и выходной языки получали независимые описания, а переход от одного языка к другому совершался на уровне универсальной семантической структуры [1-2] . Но так как формализация семантики естественных языков является задачей далекой от завершения и очень сложной, то в упомянутых системах переход осуществлялся на уровне нормализованной синтаксической структуры. Это значит, что описания рабочих языков в определенных точках подгонялись так, чтобы выходной язык соответствовал входному [1-2].
Структурная схема разрабатываемого лингвопроцессора
Разработанный лингвопроцессор (ЛП) естественного языка (ЕЯ) представляет собой систему программных модулей, на вход которой поступает предложение на естественном языке, а на выходе получается синтаксическая структура данного предложения [14,55]. В разработанном ЛП различают два уровня анализа текста - морфологический и синтаксический. Каждый из уровней состоит из набора алгоритмов, реализующих анализ поступающей структуры ЕЯ, и структур данных, служащих для хранения анализируемой информации и извлечения необходимых для анализа данных о ЕЯ из формальной модели ЕЯ. Разработанный ЛП может работать и как синтаксический, и как морфологический анализатор,
В первом случае на его вход подаются предложения ЕЯ, а на выходе выдается его синтаксическая структура (СинтС); во втором случае на вход подается произвольная словоформа ЕЯ, а на выходе выдается его морфологическая структура (МорфС).
Входное предложение разлагается на набор словоформ, которые поступают на блок морфологического анализатора, проверяющего их на правильность написания и производящего их анализ. Проанализированные словоформы выдаются в виде набора морфологических структур, которые затем анализируются синтаксическим анализатором и объединяются в синтаксическую структуру, которая классифицируется и отправляется на выход. Так как с выхода блока морфологического распознавателя поступает набор омонимов, то для последующего синтаксического анализа выбираются те из них, которые удовлетворяют распознаваемому шаблону, остальные омонимы, не вписавшиеся ни в одну из имеющихся синтаксических моделей, отбрасываются. Синтаксическая структура предложения тоже может иметь некоторую омонимию. В этом случае на выход подаются все имеющиеся синтаксические омонимы. При этом морфологический анализатор ЛП осуществляет не только анализ словоформы, но и проверку на корректность (правильность написания), а синтаксический анализатор осуществляет еще и классификацию предложения по типам.
1.Рассмотренные ЛП не являются сбалансированными по сложности между структурами данных и алгоритмами, поэтому актуальной является разработка ЛП, в которых оптимальными по сложности были бы как структуры данных, так и алгоритмы их обработки. Для успешного построения сбалансированного по сложности ЛП необходимо тщательно выбрать формальный аппарат, причем требуются формализмы не только для представления различных языковых уровней, но и для моделирования взаимодействия таких компонент ЛП, как формальная модель, реализованная с помощью специальных структур данных и алгоритмы.
2. Предложены концептуальная схема и архитектура лин гвопроцессора для разработки сквозной методологии моделирования, на основе которой возможно провести целостный анализ лингвопроцессора как технического объекта, используя однотипный математический аппарат,
3. При построении систем машинного перевода актуальна стыковка лингвопроцессоров для разных языков, что ставит задачу разработки специального сравнительно-сопоставительного подхода в проектировании лингвопроцессоров применительно к их использованию в системах машинного перевода. Предложены принципы сравнительно-сопоставительного подхода в разработке лингвопроцессоров.
4. Предложены сети Петри и гибкие сети в качестве однотипного математического аппарата для построения моделей и как аппарат для моделирования взаимодействия компонентов системы, таких как формальные модели, структуры данных и алгоритмы.
Сетевые модели морфологического анализатора и их алгоритмы
Рассмотрим построение алгоритмического формального аппарата на основе сетей Петри и его применение в компьютерной лингвистике на конкретном примере [22-33,83]. Пусть требуется построить схему морфемного разбора существительного для русского языка. Под схемой разбора подразумевается формальная модель, представляющая порядок следования морфем. Составим математическую модель морфемного анализа с помощью сетей Петри С=(Р, Т, А, Мо) / где Р - конечное множество позиций сети, Т - конечное множество переходов сети, А -алгебраическое представление сети, Мо - начальная маркировка сети. Введем следующие позиции р и переходы t: pi.- наличие слова для анализа; Р2 - произведен поиск префикса;готовность к поиску частицы; Рз - поиск частицы выполнен; р4 - произведено нахождение окончания; имеется готовность к поиску суффикса; р5 - поиск суффикса выполнен; Ре - осуществлен поиск темы; анализ слова завершен; ti - найти префикс; t2 - найти частицу как атрибут. Маркер приобретает атрибут k=length(lexem)-length(particle); t3 - найти окончание как атрибут. k=k-length(ending); U - найти суффикс как атрибут. k=k-length(suffix); t5 - найти тему как атрибут. Используя эти обозначения, математическую модель морфемного анализа можно представить в виде сети, приведенной на рис.2.8.
Переходы иерархические. Ниже приведены модели ti и t2. Алгебраическое представление А сети Петри имеет следующий вид: A = p{lH(ti,p2)]+p{2}[{t2,p3)]+p{3}[(t2,p4]]+ (2.3) +p{4}[(t4,P5)]+p{5}[(t5,p6)]. Начальная маркировка Мо задана в табл.2.71. Для анализа поведенческих свойств модели рис. 2.8 построена лента достижимости {табл.2.71). Анализ свойств сети Петри будем проводить по ее ленте достижимости. Напомним некоторые определения, используемые при анализе [84]: сеть Петри называется К-ограниченной, если существует постоянное число К, такое, что число маркеров в любой позиции сети не превышает К. Если К=1, то сеть Петри называется безопасной; маркировка Mj достижима из маркировки МІ, если существует последовательность перекодов, переводящая сеть из Мі в Mj, і, j=0,...,N (за счет использования символа ш число маркировок сети Петри всегда конечно); маркировку Mf, достижимую из начальной маркировки М0, называют целевой, если попадание в Mf интерпретируется как завершение функционирования сети. На множестве маркировок М = {Mo,Mi,. .. ,MN} задается подмножество Мц целевых маркировок (Мц может совпадать с М либо быть пустым); сеть Петри называется «живой», если в ней из любой маркировки, достижимой из М0, можно достичь, по меньшей ме ре, одну целевую маркировку. Справедливо очевидное утверждение: сеть Петри является «живой», если в ней отсутствуют достижимые из Мо тупиковые нецелевые маркировки и отсутствуют циклы-«ловушки», образованные только из нецелевых маркировок. Сеть Петри как инструмент операционного моделирования является корректной, если она «живая» и безопасная. И то и другое сравнительно просто распознается на ленте достижимости: - свойство безопасности проявляется в том, что все столбцы ленты заполнены только единицами и нулями (отсутствие символов (о говорит о том, что сеть ограниченная); - свойство «живости» проявляется отсутствием в ленте столбцов с пометкой «тупик», соответствующих нецелевым маркировкам, и отсутствием таких циклов, в которых все маркировки нецелевые и во вторую снизу клетку каждого столбца вписан один переход, т.е. в маркировке активизирован только один переход. Сеть Петри на рис. 2.8, согласно ее ленте достижимости (табл. 2.71), безопасная и «живая».
Целевой в сети является маркировка М5. В модели нет других тупиковых и дублирующих маркировок, а тупиковая маркировка Ms указывает на успешный разбор. Следовательно, алгоритм, построенный на этой модели, будет корректным.
Сетевые модели синтаксического анализатора и их алгоритмы
Составим математическую модель предсинтаксического анализа с помощью сетей Петри С=(Р, Т, А, м0), где Р - конечное множество позиций сети, Т - конечное множество переходов сети, А -алгебраическое представление сети, Мо - начальная маркировка сети [38-40]. Введем следующие позиции Р и перекоды Т: pi - входная позиция; р2 - готовность к проверке условия продолжения цикла; Рз - продолжение цикла; Р4 - выходная позиция; гі - позиция, решающая, продолжается ли цикл, т.е. Klength(Components) ; Xi - переход, соответствующий ri; ti - классифицировать і-й компонент; і=і+1; ti - инициализировать TSentence входным предложением и выделить компоненты предложения. Атрибут 1=0. Используя приведенные выше обозначения, математическую модель предсинтаксического анализа можно представить сетью, приведенной на рис.3.1, Алгебраическое представление А сети Петри имеет следующий вид: A = p{l}[ t2,p2)]+p{2}r{l}[(x1#p3,pe}]+p{3H{ti,p2)]. (3.2) Начальная маркировка Мо задана в табл.3.1. Для анализа поведенческих свойств модели рис. 3.1 построена лента достижимости (табл.3.1.). Анализ свойств сети Петри будем проводить по ее ленте достижимости. Сеть Петри на рис. 3.1, согласно ее ленте достижимости (табл. 3.1), безопасная и «живая». Целевой в сети является маркировка М . Целевая тупиковая маркировка М4 означает, что выполнение алгоритма может быть корректно завершено несколькими способами.
Следовательно, алгоритм корректен - зацикливаний и нецелевых тупиковых маркировок нет. Алгоритмы синтаксического анализатора можно разделить на два основных алгоритма: 1) алгоритм предсинтаксического анализа; 2) алгоритм формирования СинтС. Второй алгоритм тоже можно разделить на два алгоритма: а) алгоритм установления СинтО; б) алгоритм установления связей между СинтО. На вход данного алгоритма поступает предложение в виде строки. Затем выделяются компоненты предложения , т.е слово формы, разделенные разделителями. В число разделителей входят: точка- . ; точка с запятой - ; , запятая - , , двоеточие- : , пробел и т. д. Все буквы преобразуются к строчным. Выделенные из предложения словоформы заносятся в список Components структуры данных TSentence. После этого каждый из выделенных компонентов подается на блок морфологического анализа. В результате МорфС словоформы из Components [і] возвращается в MorphS [і]. II Инициализируем TSentence входным предложением TSentence.Sentence:= Входное предложение; // выделяем компоненты предложения GetComponents(TSentence); II Теперь они находятся в TSentence. Components: //получаем МорфС Tor i:= 0 to length{TSentence. Components)-1 do II классифицируем каждый компонент TSentence.Morphs[i]:= MorphsAnaliser (TSentence.Components [i]); II теперь его МорфС находится в MorphS [ij Модель и алгоритм установления СинтС Составим математическую модель установления СинтО между МорфСі и МорфСj с помощью сетей Петри С={Р, Т, А, Мо), где Р - конечное множество позиций сети, Т - конечное множество переходов сети, А -алгебраическое представление сети, Мо -начальная маркировка сети. Введем следующие позиции Р и переходы Т: Г! - решающая позиция, проверяющая, что совпадает часть речи СинтО.X и МорфСі, и совпадает часть речи СинтО.Y и МорфСj, xi - переход, соответствующий гі; Pi - входная позиция; Р2 - условие для Гі выполнено; г2 - решающая позиция, проверяющая, что атрибуты СинтО,X содержатся в МорфСі, а атрибуты СинтО.Y содержатся в МорфС к2 - переход, соответствующий Гг; Рз - оба условия выполнены; р4 - НЄ ВЬШОЛНеНЫ УСЛОВИЯ ДЛЯ Гі ИЛИ Тг г р5 - выходная позиция; ti - 1=1+1, т.е. увеличить длину списка SyntRelations; записать номер і в SyntRelations.X; записать номер в SyntRelations. Y; запомнить имя СинтО; SyntR?=true; t2 - SyntR?=false. Используя данные обозначения, математическую модель установления СинтО между МорфСі и МорфС] можно представить сетью, приведенной на рис.3.2. Алгебраическое представление А сети Петри имеет следующий вид
Похожие диссертации на Представление моделей и алгоритмов в лингвопроцессорах сетями Петри
