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

     Язык L воспринимается ЛО–автоматом тогда и только тогда, когда
это язык типа 1.
     Этот результат не находит широких приложений, поскольку ЛО–
автоматы моделируют сложные программы. В то же время доказательство того,
что областью определения функции f является контекстно–зависимый язык,
может оказаться полезным, так как оно выявляет возможности управления па-
мятью и хранения записей, необходимые программе для вычисления f. Чаще
используется другой результат.
     Все контекстно–зависимые языки рекурсивны.
     Здесь утверждается, что если областью определения L функции f является
язык типа 1, то можно написать программу (возможно, сложную), которая с га-
рантией воспринимает все цепочки σ ∈ Ι∗ (входного алфавита) и дает либо зна-
чение f (s), либо надежное указание на то, что для s функция f не определена. С
другой стороны, неудачная попытка доказать, что L — язык типа 1 или даже
типа 0, не гарантирует, что язык L не рекурсивен. Существуют рекурсивные
языки, которые не могут порождаться грамматикой типа 1.




               1.5 Автомат с магазинной памятью и языки типа 2


     Автомат с магазинной памятью (МП–автомат) — это автомат с огра-
ниченным доступом к принципиально бесконечной ленте памяти. МП–автомат
может передвигать свою читающую головку только вправо, т.е. он может вос-
принимать входные символы только в определенном порядке. Далее МП–
автомат имеет ленту памяти (магазин), которая может двигаться «вверх» и
«вниз». Если в результате движения ленты памяти символ помещается «над» ее
читающей головкой, то этот символ теряется. По аналогии с движением таре-
лок в стопке посуды в кафетерии операции движения символов «вверх» и
«вниз» иногда называют «выталкивание» и «заталкивание». На языке исследо-
вания операций лента памяти работает как стек, т.е. очередь, организованная по

                                                                             29