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

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

18
«Элементарный шаг» работы автомата состоит в том, что он (недетерми-
нированным образом) одновременно переходит в другое состояние, стирает
только что прочитанный входной символ (или
ε
), уничтожает символ Z и запи-
сывает в магазинную память некоторую цепочку (возможно, пустую), начиная с
ячейки, в которой был записан символ Z. Более формально определение выгля-
дит так.
Определение. Автоматом с магазинной памятью называется упорядо-
ченная семерка M = (K, Σ, Γ,
δ
, Z
0
, q
0
, F), где
1. K — непустое конечное множество (множество состояний);
2. Σ — непустое конечное множество (множество входных символов);
3.
Γ
— непустое конечное множество (множество символов магазинной
памяти);
4.
δ
— отображение множества K × (Σ ∪ {
ε
}) ×
Γ
во множество всех ко-
нечных подмножеств множества K ×
Γ
*;
5. q
0
∈ K (начальное состояние);
6. Z
0
∈
Γ
(маркер магазинной памяти);
7. F ⊆ K (множество заключительных состояний).
Функционирование может быть теперь формализовано.
Обозначения. Пусть M есть МП–автомат. Отношение
, или , если
M подразумевается, на множестве K × Σ*
× Γ
* определяется следующим обра-
зом. Для Z ∈
Γ
и x ∈ Σ ∪ {
ε
} полагаем (p,x w,
α
Z) |— (q, w,
αγ
) (переход от ле-
вой части этой записи к правой назовем тактом работы автомата), если
(q,
γ
)∈
δ
(p, x, Z). Для всех p, w и
α
полагаем (p, w,
α
) |— (p, w,
α
). Для всех
α, β
∈Γ* и всех x
i
∈ Σ ∪ {ε}, 1 ≤ i ≤ k, полагаем (p, x
1
... x
k
w,
α
) (q, w,
β
), если
существует последовательность состояний p
1
= p, ..., p
k +1
= q и последова-
тельность цепочек
α
1
=
α
, ...,
α
k+1
=
β
из множества
Γ
*, такие, что
(p
i
, x
i
... x
k
w,
α
i
)|—(p
i +1
, x
i+1
... x
k
w,
α
i+1
) для всех i, 1≤ i ≤ k. Если имеет место 
      «Элементарный шаг» работы автомата состоит в том, что он (недетерми-
нированным образом) одновременно переходит в другое состояние, стирает
только что прочитанный входной символ (или ε), уничтожает символ Z и запи-
сывает в магазинную память некоторую цепочку (возможно, пустую), начиная с
ячейки, в которой был записан символ Z. Более формально определение выгля-
дит так.
      Определение. Автоматом с магазинной памятью называется упорядо-
ченная семерка M = (K, Σ, Γ, δ, Z0, q0, F), где
      1. K — непустое конечное множество (множество состояний);
      2. Σ — непустое конечное множество (множество входных символов);
      3. Γ — непустое конечное множество (множество символов магазинной
памяти);
      4. δ — отображение множества K × (Σ ∪ {ε}) × Γ во множество всех ко-
нечных подмножеств множества K × Γ*;
      5. q0 ∈ K (начальное состояние);
      6. Z0 ∈ Γ (маркер магазинной памяти);
      7. F ⊆ K (множество заключительных состояний).
      Функционирование может быть теперь формализовано.

      Обозначения. Пусть M есть МП–автомат. Отношение                      , или      , если
M подразумевается, на множестве K × Σ* × Γ* определяется следующим обра-
зом. Для Z ∈ Γ и x ∈ Σ ∪ {ε} полагаем (p,x w, αZ) |— (q, w, αγ) (переход от ле-
вой части этой записи к правой назовем тактом работы автомата), если
(q, γ)∈δ (p, x, Z). Для всех p, w и α полагаем (p, w, α) |— (p, w, α). Для всех

α, β ∈Γ* и всех xi ∈ Σ ∪ {ε}, 1 ≤ i ≤ k, полагаем (p, x1 ... xkw, α)         (q, w, β), если
существует      последовательность        состояний p1 = p, ..., pk +1 = q и последова-
тельность       цепочек      α1 = α, ..., αk+1 = β     из множества Γ*, такие, что
(pi, xi ... xkw, αi)|—(pi +1, xi+1 ... xk w, αi+1) для всех i, 1≤ i ≤ k. Если имеет место

                                                                                            18

Страницы