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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

22
Очевидно, что порождающая грамматика G типа 0 является недетермини-
рованным алгоритмом (исчислением), множеством результатов которой являет-
ся L(G). Поэтому язык L(G) — рекурсивно перечислимое множество.
Класс языков типа 0 совпадает с классом рекурсивно перечислимых язы-
ков. Поэтому достаточно доказать, что множество L-выходов любой машины
Тьюринга является языком, порождаемым некоторой грамматикой типа 0.
Пусть
задано машина Тьюринга M = (S,Q,P,q
0
,q
f
). Построим грамматику
G = (N,T,P',S), у которой N = {S, X,Y,Z,W}И Q, T = {[,]}И S.
P' определяется по P следующим образом:
• для S включается правило S ® [q
0
L], создающее начальную конфигура-
цию машины с пустой лентой, ограниченную прямыми скобками; пользу-
ясь этими скобками, правила для q имитируют работу машины,
• для правила машины (q,a) ® (q',a',N) - правило грамматики qa ® q'a',
для правила (q,a) ® (q',a',L) - правила грамматики bqa ® q'ba' для всех b
из S и правило [qa ® [q'La', для правила (q,a) ® (q',a',R) - правила грамма-
тики qab ® q'ba' для всех b
из S и правило qa] ® a'q'L],
• для q
f
включаются правила грамматики, обеспечивающие сдвиг q
f
к ле-
вой границе конфигурации: aq
f
® q
f
a для всех a из S,
[q
f
® [X,
• для X, Y, Z и W включаются правила грамматики: XL ® X (X уничтожает
все L, примыкающие к левой границе), Xa ® Ya для всех a из T, не равных
L и [,Ya ® aY для всех a из S (Y перемещается к правой скобке и уничто-
жает её),Y] ® Z, LZ ® Z (Z уничтожает все L,
примыкающие к правой гра-
нице), aZ ® W для всех a из S, не равных L и ],
aW ® Wa для всех a из S (W перемещается к левой скобке и уничтожает
её и себя), [W ® e .
Так как в каждой цепочке вывода из S содержится не более одного нетерми-
нального символа, правила для q
в точности имитируют поведение машины, а
правила для X, Y, Z и W применяются однозначно и оставляют точно L-выход
машины. 
       Очевидно, что порождающая грамматика G типа 0 является недетермини-
рованным алгоритмом (исчислением), множеством результатов которой являет-
ся L(G). Поэтому язык L(G) — рекурсивно перечислимое множество.
       Класс языков типа 0 совпадает с классом рекурсивно перечислимых язы-
ков. Поэтому достаточно доказать, что множество L-выходов любой машины
Тьюринга является языком, порождаемым некоторой грамматикой типа 0.
Пусть задано машина Тьюринга M = (S,Q,P,q0,qf). Построим грамматику
G = (N,T,P',S), у которой N = {S, X,Y,Z,W}И Q, T = {[,]}И S.
   P' определяется по P следующим образом:
   •   для S включается правило S ® [q0L], создающее начальную конфигура-
       цию машины с пустой лентой, ограниченную прямыми скобками; пользу-
       ясь этими скобками, правила для q имитируют работу машины,
   •   для правила машины (q,a) ® (q',a',N) - правило грамматики qa ® q'a',
       для правила (q,a) ® (q',a',L) - правила грамматики bqa ® q'ba' для всех b
       из S и правило [qa ® [q'La', для правила (q,a) ® (q',a',R) - правила грамма-
       тики qab ® q'ba' для всех b из S и правило qa] ® a'q'L],
   •   для qf включаются правила грамматики, обеспечивающие сдвиг qf к ле-
       вой      границе       конфигурации:     aqf   ®   qf a        для   всех   a   из S,
       [qf ® [X,
   •   для X, Y, Z и W включаются правила грамматики: XL ® X (X уничтожает
       все L, примыкающие к левой границе), Xa ® Ya для всех a из T, не равных
       L и [,Ya ® aY для всех a из S (Y перемещается к правой скобке и уничто-
       жает её),Y] ® Z, LZ ® Z (Z уничтожает все L, примыкающие к правой гра-
       нице),      aZ     ®    W   для   всех     a   из S,      не    равных      L   и   ],
       aW ® Wa для всех a из S (W перемещается к левой скобке и уничтожает
       её и себя), [W ® e .
   Так как в каждой цепочке вывода из S содержится не более одного нетерми-
нального символа, правила для q в точности имитируют поведение машины, а
правила для X, Y, Z и W применяются однозначно и оставляют точно L-выход
машины.

                                                                                           22

Страницы