Методы искусственного интеллекта для машинного перевода текстов. Роганов В.Р - 15 стр.

множество τ(a), то получим регулярное множество (являющееся конечным объ-
единением множеств, каждое из которых есть произведение регулярных мно-
жеств). Так как в результате применения операций ∪, ⋅ и * к регулярным мно-
жествам мы вновь получаем регулярные множества, множество τ(a) является
регулярным. Таким образом, получаем следующую теорему:
      Теорема. Пусть R — регулярное множество, τ — определенное выше ото-
бражение и множество τ (a) регулярно для каждого a ∈ Σ. Тогда множество
τ (R) также регулярно.
      Конечный автомат — устройство по существу детерминированное. Это
означает, что для каждого входного символа следующее состояние определяет-
ся однозначно. Теперь мы снимем это ограничение — предоставим автомату
возможность выбора одного из нескольких следующих состояний и, кроме то-
го, позволим ему иметь более одного начального состояния. Цепочка допуска-
ется таким устройством, если при некотором выборе следующих состояний это
устройство, работая с данной цепочкой, переходит из некоторого начального
состояния в некоторое заключительное. Функционирование такого автомата
можно сравнить с блужданием по лабиринту, в котором в различных местах
имеется возможность выбирать различные пути. При этом некоторые из этих
путей приводят к смертельному исходу, другие — к выходу, третьи — к успеху.
Понятие недетерминированности будет важно не только для устройства, ис-
пользуемого при изучении регулярных множеств, но и для устройств, связан-
ных с рассмотрением КС–языков.
      Определение. Недетерминированным конечным автоматом называется
упорядоченная пятерка А = (K, Σ, δ, S0, F).
      1. K — непустое конечное множество (множество состояний).
      2. Σ — алфавит (множество входных символов).
      3. δ — отображение множества K × Σ во множество 2K (δ(q, x) есть мно-
жество следующих состояний).


                                                                         15