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

принципу «последним пришел — первым вышел». Эта лента предоставляет ог-
раниченный доступ к бесконечной памяти, так как в каждый момент времени
для обработки доступен только элемент, называемый вершиной стека (элемент,
размещенный в очереди последним). Это означает, что если j–й символ должен
быть прочитан, j–1 символов до него должны быть удалены из очереди.
     МП–автомат начинает работу в состоянии S0, имея цепочку s на входной
ленте и пустой магазин. Последующие конфигурации определяются именем
прочитанного символа, внутренним состоянием МП–автомата и именем симво-
ла над читающей головкой магазина. Правила перехода машины можно запи-
сать в виде (α, Σι, βρ) → (Sj, bq), допускающем следующую интуитивную интер-
претацию:
     Если в состоянии Si символ br находится наверху магазина и считан
входной символ α, то надо затолкнуть магазин и написать на нем символ bq.
     Для алфавита магазина необходим специальный «символ выталкивания»
b0. Команда «записать b0» интерпретируется как «вытолкнуть магазин».
     Язык воспринимается МП–автоматом тогда и только тогда, когда это
язык типа 2.
     Искусственный интеллект включает в себя ряд задач, которые, хотя на
первый взгляд и не имеют отношения к лингвистике, допускают формулировку
в виде задач вычисления функций, область определения которых — язык типа
2. Как только проблема сформулирована в терминах распознавания языка типа
2, появляется возможность использования обширных знаний, накопленных вы-
числительными науками для работы с такими языками. Поэтому стоит проана-
лизировать соотношение между исследуемой задачей и языками типа 2, прежде
чем выбрать структуру нужной программы.
     Существует интересная взаимосвязь между типом 2 и более ограничен-
ным типом 3. Каждая продукция грамматики типа 2 развертывает переменную
                                                          ∗
в цепочку. Если продукции грамматики G таковы, что A ⎯
                                                     ⎯→ xAy для неко-
торой переменной A (т.е. если цепочка, содержащая A, выводима из A), то


                                                                            30