Модель расширенных сетей переходов разработал американский лингвист Вудс.
Сетью переходов называется ориентированный граф с помеченными вершинами и ребрами. Среди множества вершин выделяется начальная вершина и множество заключительных вершин. Часто вершины называют состояниями. На ребрах могут быть, как терминальные, так и нетерминальные пометки.
Пример расширенной сети переходов представлен на рис. 6.2.
Здесь, предл. – начальное состояние, а заключительные состояния помечены *.
Анализ производится по следующему алгоритму.
- Изначально находимся в начальном состоянии.
- Пытаемся перейти в другие состояния. При этом если на ребре перехода содержатся нетерминальные пометки, то их раскрываем с помощью вершины, соответствующей этой нетерминальной пометке.
- Если фраза исчерпана и все текущие состояния – конечные, то цепочка принадлежит языку. Причем сам этап порождения фактически задает смысл фразы
Пример. Два способа порождения фразы «Мать любит дочь» (рис. 6.3, 6.4).
Алгоритм анализа с помощью расширенных сетей переходов работает по схожему принципу с алгоритмами анализа контекстно-свободных грамматик.
Рис. 6.2. Расширенная сеть переходов.
A)
Рис. 6.3. Построение фразы «мать любит дочь» с подлежащим «мать»В)
Рис. 6.4. Построение фразы «мать любит дочь» с подлежащим «дочь»
