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

      4. S0 — непустое подмножество множества K (множество начальных со-
стояний).
      5. F — подмножество множества K (множество заключительных со-
стояний).
      Для недетерминированного конечного автомата δ доопределяется сле-
дующим образом: δ (q, ε) ={q} для всех q.
      Определение. Пусть А = (K, Σ , δ , S0, F) — недетерминированный конеч-
ный автомат. Цепочка w принадлежит множеству T (A) (или допускается авто-
матом A), если либо w = ε и S0 ∩ F ≠ ∅ , либо w = x1 ... xn, где для каждого i
xi∈Σ , и существует последовательность s0, ..., sn элементов множества K, такая,
что
      1. s0 ∈ S0,
      2. si ∈ δ (si–1, xi) для 1 ≤ i ≤ n,
      3. sn ∈ F.
      Следующий результат является основным в теории недетерминирован-
ных конечных автоматов.
      Теорема. Для каждого недетерминированного конечного автомата A
множество T (A) регулярно.
      Таким образом, конечные автоматы и недетерминированные конечные
автоматы имеют одинаковую порождающую силу, а именно, они распознают
одни и те же множества цепочек.
      Введем гипотезу, что перевод должен выполняться в виде линейного
процесса. Тогда определим линейные правила
      Определение. Правило называется линейным, если оно имеет вид ξ → u
или ξ → uν v, где u, v ∈ Σ*, ν ∈ V — Σ. КС–грамматика называется линейной,
если каждое ее правило линейно. КС–язык называется линейным, если он поро-
ждается некоторой линейной КС–грамматикой.




                                                                              16