Сети с конечным числом состояний

Сети с конечным числом состояний имеют два состояния: начальное и заключительное.

Нетерминальные символы – в узлах, означают синтаксические категории.

Алгоритм нахождения цепочки:

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

Вопрос восприятия цепочки сводится к заключению, могла ли её породить грамматика, определённая заданной сетью (если можем дойти до конца, то да).

Пример. S – начальное предложение, S* - заключительное предложение

The big black cat chased the little gray mouse
S, Det, A, A, N, V, Det, A, A, N, S* Правило: A → s1 A s2

It’s believed that <S>

Сети с расширенными числом состояний

Расширенная сеть переходов может иметь в узле ссылку на другую сеть.

Did Sherlock Holmes expose the evildoer?

• S (предложение)
  • NP (noun phrase)
    • Noun – Sherlock Holmes
  • VP (verbal phrase, группа глагола)
    • Verb
      • Expose (past tense)
      • Aux (did)
    • Det – the
    • N – evildoer

Lady Agathes is believed to have been abducted.

• S
  • Декларативн.
  • NP
    • Некто (A)
  • VP
    • Believe (present tense)
    • Дополнение
      • NP
        • Некто (B)
      • V
        • Abduct (past tense)
      • NP
        • Lady Agathes

Основные недостатки математического подхода – его формальность. Формальная модель — только для ограниченных множеств.