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

UptoLike

20
Определение. Цепочка w допускается МПавтоматом M = (K, Σ,
Γ
,
δ
, Z
0
,
q
0
, F), если (полагаем (q
0
, w, Z
0
) (q,
ε, α
) для некоторых q F,
α
Γ
*. Мно-
жество всех цепочек, допускаемых МПавтоматом M, обозначается T(M). Заме-
тим, что
ε
F.
Формальные грамматики дают естественный способ упорядочения язы-
ков с помощью ограничений, которые можно ввести в продукции (правила пе-
реписывания). Перечислим их в порядке убывания мощности:
Язык типа 0, или язык без ограничений, порождается грамматикой, в ко-
торой все продукции имеют вид x y, где x и yцепочки
в V* (словаре грам-
матики).
Язык типа 1, или контекстно-зависимый язык, порождается граммати-
кой, в которой все продукции имеют вид x y и, кроме того, число | y | симво-
лов в y не меньше числа символов в x. Значимость этого ограничения лучше
всего оценить, анализируя продукцию, нарушающую его. Например, правило
(S
1
+ S
2
) – S
2
S
1
. Можно показать, что язык, порождаемый контекстно-
зависимой грамматикой, может порождаться также грамматикой, в которой все
продукции имеют вид xAy xwy, где w, x и yцепочки в V*, а Aперемен-
ная (нетерминал). Продукцию xAy xwy можно интерпретировать так:
Цепочка w выводима из A, если А появляется в контексте x и y.
Таким образом, правило переписывания xAy xwy дает интуитивно бо-
лее понятное определение контекстно-зависимой грамматики.
Язык типа 2, или контекстно-свободный язык, порождается граммати-
кой, в которой все продукции имеют вид A x, где, как и раньше, Aнетер-
минал, а xцепочка в V*.
Язык типа 3, или
регулярный язык, порождается грамматикой, продукции
которой имеют вид A aB или A a, где aтерминал, а Bнетерминал.
      Определение. Цепочка w допускается МП–автоматом M = (K, Σ, Γ, δ, Z0,

q0, F), если (полагаем (q0, w, Z0)   (q, ε, α) для некоторых q ∈ F, α ∈ Γ*. Мно-
жество всех цепочек, допускаемых МП–автоматом M, обозначается T(M). Заме-
тим, что ε ∈ F.
      Формальные грамматики дают естественный способ упорядочения язы-
ков с помощью ограничений, которые можно ввести в продукции (правила пе-
реписывания). Перечислим их в порядке убывания мощности:
      Язык типа 0, или язык без ограничений, порождается грамматикой, в ко-
торой все продукции имеют вид x → y, где x и y — цепочки в V* (словаре грам-
матики).
      Язык типа 1, или контекстно-зависимый язык, порождается граммати-
кой, в которой все продукции имеют вид x → y и, кроме того, число | y | симво-
лов в y не меньше числа символов в x. Значимость этого ограничения лучше
всего оценить, анализируя продукцию, нарушающую его. Например, правило
(S1 + S2) – S2 → S1 . Можно показать, что язык, порождаемый контекстно-
зависимой грамматикой, может порождаться также грамматикой, в которой все
продукции имеют вид xAy → xwy, где w, x и y — цепочки в V*, а A — перемен-
ная (нетерминал). Продукцию xAy → xwy можно интерпретировать так:
      Цепочка w выводима из A, если А появляется в контексте x и y.
      Таким образом, правило переписывания xAy → xwy дает интуитивно бо-
лее понятное определение контекстно-зависимой грамматики.
      Язык типа 2, или контекстно-свободный язык, порождается граммати-
кой, в которой все продукции имеют вид A → x, где, как и раньше, A — нетер-
минал, а x — цепочка в V*.
      Язык типа 3, или регулярный язык, порождается грамматикой, продукции
которой имеют вид A → aB или A → a, где a — терминал, а B— нетерминал.



                                                                              20