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

                        Рис.3 Дерево грамматического разбора


        Предложение в действительном залоге получается из дерева разбора сра-
зу же. Предложение в страдательном залоге требует правил типа
        <группа существительного1> <глагол> <группа существительного2> →
 <группа существительного2> <глагол в страдательном залоге> <предлог>
                         <группа существительного1>
для замещения активной формы пассивной. Приведенное правило — транс-
формационное, подобное правилу AB → BA.
        Для применения исследований, выполненных в теории искусственному
интеллекту здесь важно, что любая программа вычисления функции, область
определения которой образована предложениями на каком–то естественном
языке, должна быть программой, моделируемой автоматом, не менее мощным,
чем машина Тьюринга. Поэтому программе будет нужен неограниченный дос-
туп к динамической памяти, который в принципе все же можно рассчитать и
соответственно создать условия для практической реализации. Одним из шагов
в решении этой задачи являются Линейно ограниченные автоматы и языки ти-
па 1.




        1.4 Линейно ограниченные автоматы и языки типа 1


        Для начала будем считать, что имеем длинную ленту, по которой может
перемещаться читающая головка (аналог обычного бытового магнитофона).
Линейно ограниченным автоматом (ЛО–автоматом) называют машину Тью-
ринга, которой запрещено передвигать читающую головку за пределы участка
входной ленты, занятого входной цепочкой. Это можно достичь, добавив к
входному языку два специальных символа (обычно & и $). Их помещают в на-
чале и в конце входной цепочки, которая после этого превращается в &s$.


                                                                           27