Расширенные сети переходов

Модель расширенных сетей переходов разработал американский лингвист Вудс.

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

Пример. //пример сети переходов (5)

Здесь, предл. – начальное состояние, а заключительные состояния помечены *.

Анализ производится по следующему алгоритму.

A) Изначально находимся в начальном состоянии.

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

C) Если фраза исчерпана и все текущие состояния – конечные, то цепочка принадлежит языку. Причем сам этап порождения фактически задает смысл фразы.

Пример. Два способа порождения фразы «Мать любит дочь».

A) B)

//пример (6)

A)

B)

Алгоритм анализа с помощью расширенных сетей переходов работает по схожему принципу с алгоритмами анализа контекстно-свободных грамматик (подробнее []).

Дата добавления: 2015-09-06