ЗАДАЧИ ГРАММАТИЧЕСКОГО ВЫВОДА

Предположим, что в выборке S_t, представляющей собой последовательность цепочек символов x , …, x_t из множества всех цепочек T^*, некоторые из цепочек порождены неизвестной грамматикой . Обозначим через множество тех цепочек из выборки , которые допускаются , а через тех цепочек, которые отвергаются ею:

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

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

Представим себе гипотетическую машину М, которая способна в некотором фиксированном порядке перечислять (возможно, бесконечно) множества G кандидатов в грамматики. «Всезнающий» экспериментатор в качестве исходной выбирает некоторую грамматику , которая считается правильной, т. е. согласованной с некоторой грамматикой из этого множества.

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

Однако весьма сложно реализовать вычислительную процедуру, способную воспроизвести именно G^*, поскольку может быть бесконечно много грамматик, согласованных с G^*. Используя «информативное» или текстуальное представление,экспериментатор строит постепенно нарастающие выборки S₁, …, S_t, при этом машина находит в своем перечне грамматику G_t, удовлетворительно объясняющую выборку S_t.

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

.

Точно также можно иметь в виду машину, которая последовательно рассматривает множества S₁, …, S_t и формирует после каждого просмотра грамматику

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

.

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

В процессе грамматического вывода машина должна улучшать вывод по мере приобретения информации. На каждом шаге вывода некоторые грамматики могут отвергаться из-за неспособности порождать какое-либо положительное предложение в , либо из-за того, что какое-либо отрицательное предложение в выборке они считают допустимым. Когда машина вывода делает успехи, то множество грамматик (t), оставшихся для исследования на шаге t, постепенно уменьшается, т. е. должно выполняться соотношение

Если процесс вывода приводит к грамматике, согласованной с , то в некоторый момент будет содержать те грамматики G¢, для которых

Для оценки того, насколько грамматика подходит для описания выборки , используется функция адекватногоописания. Функция может изменяться от 0 до ¥, причем 0 интерпретируется как «совершенное описание» а значение указывает на то, что не содержит всех положительных предложений рассматриваемой выборки или содержит одно из отрицательных предложений, т. е. множество грамматик не годится для описания выборки