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

Оглавление.

Введение, постановка задачи исследования.

Глава I. Анализ функций, методов и способов реализации диалоговых систем.

1.1 .Анализ реализации предметных областей диалоговых систем на основе грамматик.

1.2.Функциональные особенности существующих диалоговых систем. 33 1.3 .Алгоритмическое обеспечение грамматического разбора языка.

1.4.Методы оценки сложности алгоритмов синтаксического анализа.

1.5.Выводы по гл. 1.

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

2.1. Особенности моделирования процессов синтаксического анализа.

2.2. Грамматика - как математическая система, определяющая язык.

2.3. Распознаватели, автоматы с магазинной памятью и преобразователи-как базовые модели синтаксического анализа.

2.4. Синтаксический анализ на основе преобразователя с магазинной памятью.

2.5. Выводы по гл. 2.

Глава III. Теоретические основы построения и анализа алгоритмов распознавания естественных языков.

3.1. Построение синтаксического анализа на основе КС-грамматик, восходящие и нисходящие алгоритмы.

3.2. Анализ использования алгоритма динамического программирования

3.3 Разработка позиционного алгоритма синтаксического анализа.

3.4. Матричные способы анализа, распознавания и оценки неоднозначности КС-грамматик.

3.5. Выводы по гл. 3.

Глава IV. Вычислительный эксперимент по отладке алгоритма.распознавания естественных языков.

4.1 .Объектно-ориентированный подход к обоснованию архитектуры диалоговой системы.

4.2. Особенности формирования архитектуры диалоговой системы.

4.3. Формирование словаря предметной области.

4.4. Реализация вычислительного эксперимента.

4.5. Выводы по гл. 4.

Основные результаты работы.

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

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

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

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

ЭВМ", выдача и обработка приказов, формирование ответов на естественном языке позволяют не только во многом высвободить трудовые ресурсы, но и качественно изменить функции специалистов, занятых в процессе управления различными техническими комплексами и устройствами. Их использование позволяет также качественно улучшить ряд показателей систем: обеспечить более надежное и безопасное управление технологическими комплексами, достигнуть эффективного и надежного управления ТС ОВТ и судном в различных условиях и ситуациях.

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

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

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

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

С увеличением числа непрофессиональных пользователей ЭВМ, большое значение приобретает использование естественного языка общения, который обеспечивает свободный доступ человека к ЭВМ, адаптацию и надежность их взаимодействия. Естественный язык является универсальным языком, и применим для всех групп пользователей. Связь с ЭВМ на естественном языке, по существу, является идеальной формой связи. Таким образом, под диалогом пользователя с ЭВМ, в соответствии с точкой зрения, характерной для разработчиков систем искусственного интеллекта, специалистов по прикладной лингвистике и естественному языку, понимается общение, приближающееся к свободному речевому общению людей при совместном решении различных задач [14,16,35,48,70].

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

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

Переход к диалогу в системе " оператор-ЭВМ" на основе свободного общения на ограниченном естественном языке, проходил в несколько этапов. Следует отметить, что вместе с усложнением языка общения усложнялись и способы представления в ЭВМ знаний о предметной области общения диалоговых систем. Например, Д.А. Поспелов [7] в этом плане предлагает следующую топологию существующих диалоговых систем. Наиболее простым классом являются диалоговые системы, которые базируются на языках операторного типа, традиционных для программирования. Их поддержка осуществляется специальными средствами математического обеспечения, дающих возможность работы в режиме диалога в рамках соответствующей операционной системы.

Следующим шагом на пути приближения ЭВМ к пользователю были диалоговые системы, опирающиеся на жесткий информационный язык с заданным форматом. К этому классу относились многочисленные системы информационного поиска с языками дескриптивного типа. Принцип распознавания сообщения-запроса по ключевым словам из-за его универсальности и простоты используется также и в диалоговых системах со слабо формализованными [5,32,84] или нормализованными [73,90,92] естественными языками. Системы этого типа были способны понимать ограниченное число предложений естественного языка определенной структуры.

Дальнейшим шагом в развитии систем понимания естественного языка, являются так называемые лингвистические процессоры [1,14,35,42,68,69], способные осуществлять различные виды анализа входных сообщений (синтаксический, морфологический, семантический) и ориентированные на работу с конкретной предметной областью.

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

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

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

Язык при этом обычно рассматривается как способ организации цепочек абстрактных символов, а его структура объясняется в терминах правил манипулирования символами. Один из подходов состоит в использовании порождающей системы, называемой грамматикой. Цепочки языка можно строить точно определенными способами с применением правил грамматики. В грамматике, определяющей язык, используется два конечных непересекающихся множества символов - множества терминальных и нетерминальных символов. Из терминальных символов образуются слова (цепочки) определяемого языка. Нетерминальные символы служат для порождения слов. Множества правил грамматики описывают процесс порождения цепочек языка. По виду правила грамматики можно классифицировать на: праволинейные, контекстно-свободные (или бесконтекстные), контекстно-зависимые (или неукорачивающие), общего вида (без ограничений).

В задачах перевода естественных языков доминирующий подход связан с рассмотрением упрощенного подмножества естественного языка, которое может обрабатываться одним из расширенных вариантов контекстно-свободных грамматик. К настоящему времени разработаны три во многом сходные системы грамматического разбора, ориентированные на естественный язык любой сложности. Первая из них — система Торна, Братли и Дьюара [50], остальные две — Боброва и Фрезера и Вудса [59].

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

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

Чтобы можно было производить разбор естественного языка в полном объеме, требуется использовать вместо «рекурсивных сетей переходов» программы разбора, основанные на «расширенных сетях переходов», которые могут «производить изменения содержимого множества регистров, ассоциированных с сетью, а переходы на них могут быть условными в зависимости от содержимого этих регистров» [96]. При этом осуществляется «добавление к каждой дуге сети переходов произвольного условия, которое должно быть выполнено для перехода по дуге, и множества действий по построению структуры, которые должны выполняться, если имеет место переход».

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

Понятие семантической сети, введенное Квиллианом [87], также широко используется при разработке диалоговых систем [3,15,18,21,29,33,41,44,45,47, 50,52,61,63,78,79,81,82,94,100,102,104,105,107], хотя и не имеет четкого опредеи ления. Неформальное использование семантических сетей реализовано Шубертом [101], который показал, что невозможно дагь точное определение семантической сети, не ограничивая области применения. Семантические сети характеризуются следующими особенностями:

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

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

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

Ряд исследований посвящено оценке свойств различных абстрактных языков, а также алгоритмам их грамматического анализа. Эти исследования позволили разработать целый ряд алгоритмов разбора и их представлений. Расширенный обзор алгоритмов разбора изложен в работе[2]. В качестве теоретической основы построения алгоритмов распознавания предложений естественного языка лежит определенный математический аппарат, содержащий в себе различные элементы теории множеств, графов и математической логики [1, 2,10,14,81]. Посредством этого математического аппарата, определяются необходимые математические понятия и средства описания синтаксической структуры естественного языка. Он включает в себя анализ фундаментальных базовых модулей, выступающих в качестве основных средств определения языков, таких как: генераторы и распознаватели, а также анализаторы, преобразователи и автоматы с магазинной памятью.

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

К 1950 -1960 годам относятся первые работы Н.Хомского, оказавшие большое влияние на развитие формальных математических методов описания и анализа языков. Математической теории языков и ее приложению к естественным языкам посвятили свои исследования многие крупнейшие специалисты: В.Н.Глушков, А.П. Ершов, С.С.Лавров, А. А.Летичевский, В.Н.Редько, Е.Л. Ющенко, Д. Кнут, А.Ахо, Д.Грис, Дж, Ульман и другие.

Методы формирования и моделирования естественных языков решены И.Л. Братчиковым и его учениками: Графеева Н.Г.,Тойрих Х.И. и др.[8,9,10]. Эти работы посвящены моделированию свойств конечных языков и его приложению к задаче анализа естественных языков, в которых рассмотрены вопросы с теоретической и прикладной точек зрения разработки и уточнения математических моделей естественных языков на базе теории формальных грамматик.

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

Задаче формального описания и математическим методам разбора естественных языков огромное внимание уделялось В.Ш.Кауфланом, А.А.Летичевс-ким, А. ван Вейнгаарденом, Д.Кнутом и рядом других авторов.

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

Одной из важнейших задач теории формальных языков, да и информатики в целом является разработка эффективных и удобных для реализации методов синтаксического анализа и разбора предложений естественных языков. Задача разработки алгоритмов синтаксического анализа, актуальна при создании практически любых диалоговых систем, осуществляющих синтаксический анализ или разбор входных предложений естественных языков. Данным вопросом занимались многие исследователи, причем в большинстве работ рассматриваются методы обработки предложений, построенных именно на основе контекстно-свободных грамматик. Большой вклад в эти исследования внесли В.Н. Редько, М.Р.Шура-Бура, В.М.Курочкин, Е.Айронс, А. Ахо, Р.Вагнер, Дж. Лайон и другие.

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

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

Проблема понимания машиной даже ограниченного естественного языка далека еще от окончательного своего практического решения [7,10,95]. Главное ограничение, с которой столкнулись все программы разбора для контекстно-свободных грамматик, заключается в том, что они не могут справиться со сложностью полного естественного языка. Существенным недостатком естественных языков с точки зрения их машинной обработки, является высокая сложность их синтаксической и семантической структуры.

Основные теоретические недостатки, присущие различным алгоритмам разбора контекстно-свободных грамматик, подробно обсуждались Хомским[6].

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

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

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

Цель работы: Совершенствование методов математического моделирования алгоритмов управления технологическими процессами, заданных на естественном языке, путем анализа и распознавания контекстно-свободных грамматик применительно к диалоговым системам.

Объект исследования: Диалоговые системы распознавания естественного языка при управлении технологическим процессом.

Предмет исследования: Алгоритмы синтаксического анализа контекстно-свободных грамматик при описании алгоритмов управления технологическим процессом.

Методы исследования: Теория формальных грамматик, теория графов, алгоритмов, дискретная математика, математическая логика.

Задачи исследований:

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

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

2. Формирование алгоритма распознавания языка в соответствии с требованиями по совершенствованию диалоговых систем и оценка эффективности методов моделирования синтаксического анализа естественных языков.

3. Разработка теоретических основ построения и анализа алгоритмов распознавания естественных языков.

4. Формулировка и формализация метода моделирования контекстно-свободных грамматик.

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

Основные результаты работы.

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

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

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

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

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

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

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

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

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

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

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

10.Результаты исследований внедрены и реализованы в НПФ "Меридиан", в програмном комплексе "Диалог-ТП". Они могут быть использованы как в учебном процессе, так и при разработке алгоритмического обеспечения диалоговых систем на базе компьютерных тренажерных комплексов по подготовке операторов судовождения и операторов погрузочно-разг-рузочных терминалов в НИИ и научно-проектных огранизациях флота.

1..Анисимов А. В. Об аппарате управления в синтаксических анализаторах // Киберне-тика. 1974. № 6.

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

3. Ахо А., Хопкрофт Дис., Ульман Дис. Временная и ленточная сложности языков, допускаемых математическими автоматами // Языки и автоматы. М.: Мир, 1975.

4. Бадд Т. Объектно-ориентированное программирование в действии. СПб.: Питер, 1997.

5. БеллманР., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1964.

6. Блидман А.Ф., Прохоров А.Г. Технология перегрузочных работ на речных портах. М.: Транспорт, 1990.

7. Болотова Л. С. и др. Системы искусственного интеллекта. М., 1998.

8. Братчиков И. JI. Синтаксис языков программирования. М.: Наука, 1975.

9. Братчиков И.Л., Фитиалов С.Я., Цейтин Г.С. О структуре словаря и кодировке информации для машинного перевода. //Материалы по машинному переводу, сб. ст.: Издательство СПб. университета 1989.

10. Бурденов И. Б., Косачев А. С., Кулямин В. В. Использование конечных автоматов для тестирования программ // Программирование. 2000. № 2.

11. Варжапетян А. Г., Глущенко В. В. Системы управления. Учебное пособие. М.: Вузовская книга, 2000.

12. Васильев В. В. Компьютерное понимание текстов. М., 1988.

13. Взаимодействие последовательных процессов // Языки программирования. М.: Мир, 1972.

14. Виноград Т. Программа, понимающая естественный язык. М.: Мир, 1976.

15. Вихров М. М., Гаскаров Д. В., Грищенков А. А., Шнуренко А. А. Управление и оптимизация производственно-технологическими процессами / Под ред. Д. В. Гас-карова. СПб.: Энергоатомиздат, Санкт-Петербургское отделение, 1995.

16. Воас Д. Качество ПО: восемь мифов // Открытые системы. 1999. № 9—10.

17. Волкова В. Н., Денисов А. А. Основы теории системы и системного анализа. СПб.: Изд. СПГУТУ, 1997.

18. Вудс В. А. Сетевые грамматики для анализа естественных языков // Киб. сборник, новая сер. Вып. 13. — М.: Мир, 1976.

19. Выставкин А. П. Автоматизация научных исследований. — М.: ИРЭ, 1990.

20. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1988.

21. Гладкий А. В. Лекции по математической лингвистике для студентов МГУ. Новосибирск: Изд-во Новосибирского ун-та, 1966.

22. Гриневич Г.П. Комплексно-механизированные и автоматизированные склады на транспорте. М.: Транспорт, 1987.

23. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975.

24. Гросс М., Лантен А. Теория формальных грамматик / Пер. с франц. М.: Мир, 1971.

25. Грушецкий В. В. Синтаксические структуры // Системное и теоретическое программирование. Новосибирск: ВЦ СО АН СССР.

26. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.

27. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.

28. Дерябин Р.В. Производственная деятельность морского порта. М.: Транспорт, 1988.

29. Дейл Н., Уимз Ч., Хедингтон М. Программирование на С++. М.: Изд-во ДНК, 2000.

30. Дейтел X. М., Дейтел П. Д. Как программировать на С++. М.: Бином, 1999.

31. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985.

32. Ершов А. П. Введение в теоретическое программирование. М.: Наука, 1977.

33. Иондин J1. Автоматическая обработка текста на естественном языке: модель согласования. М., 1990.

34. Йордон Э., Аргнис К. Структурные модели в объектно-ориентированном анализе и проектировании. М.: Лори, 1999.

35. Казаков А.П., Фадеев Н.П. Организация и планирование работы речных портов. М.: Транспорт, 1989.

36. Канне С., Долк Д., Енг-Кек Мтуен. Тестирование программного обеспечения. Киев: DiaSoft, 2000.

37. Карпов Ю. Г. Теория алгоритмов и автоматов. Курс лекций. СПб.: СПбГТУ Нестор, 1998.

38. Клини С. К. Введение в математику / Пер. с англ. ИЛ, 1957.41 .Клир Д. Абстрактное понятие системы как методологическое средство // Исследования по общей теории систем. М.: Прогресс, 1969.

39. Кнут Д. О переводе (трансляции) языков слева-направо // Языки и автоматы. М.: Мир, 1975.

40. Кознов Д. В. Конечный автомат — основа для визуальных представлений поведения объектов // Объектно-ориентированное визуальное моделирование. СПб.: Изд-во СПбГУ, 1999.

41. Колман Р., Фолб П., Арбиб М. Очерки по математической теории систем. М.: Мир, 1971.

42. Кон П. Универсальная алгебра. М.: Мир, 1968.

43. Константинов В. И., Нуриев Р. М. Метаязык трансляции контекстно-свободных языков // Вычислительные системы. Вып. 57. 1973.

44. Корн Г., Горн Т. Справочник по математике. М.: Наука, 1984.

45. БСосарев Ю.А. Естественная форма диалога с ЭВМ. Ленинград "Машиностроение",! 989

46. Круглый стол «Парадигмы искусственного интеллекта» // Новости искусственного интеллекта. 1998. № 3.

47. Кузнецов Б. П. Психология автоматного программирования // BYTE / Россия. 2000. №1.

48. Кузнецов О. П. Неклассичекие парадигмы в искусственном интеллекте // Изв. РАН. Теория и системы управления. 1995. № 3.

49. Кук В., Бейз Г. Компьютерная математика. М.: Наука, 1990.

50. Куржанский А. Б. Управление и наблюдение в условиях неопределенности. М.: Наука, 1977.

51. Лавров С. С., Гончарова Л. И. Автоматическая обработка данных, хранение информации в памяти ЭВМ. М.: Наука, 1971.

52. Лавров С. С., Ордян А. А. Об одном расширении алгоритма Кнута для анализа бесконтекстных языков // ЖВМ и МФ. 1975. № 15-4.

53. Летичевский А. А., Синтаксис и семантика формальных языков // Кибернетика, 1968. №4, 1,9.

54. Любашин А. Промышленные и встраиваемые системы на «стандартном» пути // PC WEEK. № 15. 2000.

55. Мальцев А. И. Алгоритмы и рекурсивные функции. М.: Наука, 1965.

56. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971.

57. Мовшович С. М. Продолжение синтаксического анализа после обнаружения ошибки//Программирование. Вып. 2. 1975.61 .Морская доктрина РФ на период до 2020 года//Морские вести России №23-24/2001.

58. Мостовой И.Ф. Эксплуатация портовых складов. М.: Транспорт, 1994.

59. Пеман Д. 1П(11)-грамматики и детерминированные языки // Языки и автоматы. М.: Мир, 1975.

60. Первозванский А. А. Математические модели в управлении производством. М.: Наука, 1975.

61. Перебудов Ф. И., Тарасенко Ф. П. Введение в системный анализ. Учебное пособие для вузов. М.: Высшая школа, 1989.

62. Перевозчикова О. Л., Шевченко В. В. О синтаксическом анализе и локализации ошибок//Кибернетика. 1976. № 4.

63. Пертен Ю.А. Механизация и автоматизация складов и штучных грузов. Л.: Машиностроение, 1972.

64. Плоткин Б. В., Францев Р.Э. Реализация алгоритмов синтаксического анализа для различных классов контекстно-свободных языков // Тезисы докладов VIII Санкт-Петербургской Междунар. конф. «Региональная информатика-2002». СПб.: СПИ-ИАРАН, 2002.

65. Плоткин Б. В., Францев Р. Э. Позиционный алгоритм анализа контекстно-свободных языков // Прикладная математика и информатика. Вып. 7. СПб.: СПГУВК, 2002.

66. Попов Э.В. Общение с ЭВМ на естественном языке. М.Наука,1982.

67. Поттосин И. В. О критериях добротности программ // Системная информатика. Вып. 6. Новосибирск: Наука, 1998.

68. Пригожин И., Стенгерс И. Порядок из хаоса. М.: Эдиториал УПСС, 2000.

69. Птипьер К. Синхронный С++ для интерактивных приложений // Открытые системы. 1999. № 3.

70. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.

71. Романовский И. В. Дискретный анализ. СПб.: Невский диалект, 1999.

72. Романовский И. В. Дискретный анализ. СПб. : Невский диалект, 2000.

73. Росс Д. Структурный анализ: язык для передачи понимания // Требования и спецификации в разработке программ. М.: Мир, 1984.

74. Рыков А. С. Методы системного анализа: оптимизация. М.: Экономика, 1999.

75. Сеймур Гинзбург. Математическая теория контекстно-свободных языков / Пер. с англ. М.: Мир, 1970.

76. Синтаксический анализ формальных языков // Сб. переводов. Ростов: Изд-во Ростовского ун-та, 1971.

77. Скрогг Г. Семантические сети как модели памяти // Новое в зарубежной лингвистике. Вып. 12. М., 1983.

78. Советов Б. Я., Яковлев С. А. Моделирование систем. М.: Высшая школа, 1998.

79. Сонкин В. JL, Мартинов Г. М., Любимов А. Б. Интерпретация диалога в Windows-интерфейсе систем управления // Приборы и системы управления. № 12. 1998.

80. Транспортный комплекс России, М.2001.

81. Тъюринг А. Может ли машина мыслить? Саратов: Колледж, 1999.

82. Фостер Дис. М. Автоматический синтаксический анализ. М.: Мир, 1978.

83. Хомский Н. Формальные свойства грамматик // Кибернетический сборник, новая серия. Вып. 2. М.: Мир, 1966.

84. Хомский Н., Шютценбергис М. П. Алгебраическая теория контекстно-свободных языков //Кибернетический сборник, новая серия. Вып. 3. М.: Мир, 1966.

85. Хомский Н. Аспекты теории синтаксиса. М.: Изд-во МГУ, 1972.

86. Цейтин Г. Е., Ющенко Е. П. Некоторые вопросы теории параметрических моделей языков и параллельный синтаксический анализ // Труды Всесоюз. симп. по методам реализации новых алгоритмических языков. Ч. 2.

87. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.

88. Шевченко В. В. Об одном подходе к проблеме синтаксического анализа // Кибернетика. 1974. № 4.

89. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.

90. Griffiths.Т.V., Petrick S.R., On the relative efficiencies of context-free grammar recognizers, Comm. ASM 8, 1965, №5.

91. Halliday M.A.K., Notes on Transitivity and Theme in English, J. of Lng. 3, 1989.

92. Halliday M.A.K., Functional Diversity in Language as seen from a Consideration of Modality and Mood in English., Foundations of Language. 6, 1990.

93. Woods W.A., Procedural Semantics for aQuestion-Answer Mashine, Proc. Fall Joint Comput. Conf., New York, Spartan, 1981.

94. King D. et al. On object state testing/ZProceeding The Eighteenth Annual Inter. Сотр. Software & Applications Conf. Los Alamitos: IEEE Computer Society Press, 1993.

95. Martin K.C. Designing object-oriented С++ using the Booch method. NJ: Pt. Hall,1995.

96. Jacobson I. Object-oriented software engineering. MA: Add. Report AI 91

97. J. Hartman. Automatic control understanding for natural programs. Technical Report AI 91-161, University of Texas at Austin, 1991. PhD thesis.

98. C.N. Pereira and D.H.D. Warren. Parsing as deduction. In Proc. of the 21st Annual-Metting of the ACL, pages 137-144, Cambrid-ge,Massachusetts, U.S.A., 1983.

99. Boves,Lou,Jan Languageand Speech Technology. Programme CLS Technology', 1995.

100. Carroll. J.A . Practicalunification-basedparsing of natural language .Technical Report 314,University ofCambridge,ComputerLaboratory,England.PhD thesis, 1993.

101. R. Scha. 1990. Language theory and language technology; competence and performance. In Q.A.M. de Kort and G.L.J. Leerdam, Almere. In Dutch, 1990.

102. СЛОВАРЬ ПРЕДМЕТНОЙ ОБЛАСТИ192