Введение

Сеть расширенного перехода (англ. augmented transition network, ATN) — тип графовой структуры, используемый в операционном определении формальных языков, особенно при разборе относительно сложных естественных языков и имеющий широкое применение в искусственном интеллекте. Теоретически, ATN может анализировать структуру любого предложения, каким бы сложным оно ни было. ATN являются модифицированными переходными сетями и расширением RTN. ATN основываются на идее использования конечных автоматов (модель Маркова) для разбора предложений. У.А. Вудс в книге «Грамматики сетевых переходов для анализа естественного языка» утверждает, что добавление рекурсивного механизма к модели конечного состояния позволяет значительно повысить эффективность разбора. Вместо построения автомата для конкретного предложения создается набор графов переходов. Грамматически правильное предложение разбирается путем достижения конечного состояния в любом из этих графов. Переходы между графами представляют собой просто вызовы подпрограмм из одного состояния в любое начальное состояние на любом графе в сети. Предложение признается грамматически правильным, если конечное состояние достигается последним словом в предложении. Эта модель соответствует многим целям, определяемым природой языка, поскольку она отражает закономерности языка. То есть, если процесс выполняется в различных контекстах, грамматика должна заключать этот процесс в единую структуру. Такая инкапсуляция не только упрощает грамматику, но и повышает эффективность работы. Еще одним преимуществом такой модели является возможность откладывать принятие решений. Многие грамматики прибегают к предположениям при возникновении неоднозначности, что означает, что информации о предложении недостаточно. Используя рекурсию, ATN решают эту проблему неэффективности, откладывая решения до тех пор, пока не станет известно больше о предложении.