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

                   Рис. 4. Определение регулярного языка в виде графа
        В графе есть дуги, входящие и выходящие из одного и того же узла, и ду-
ги, соединяющие различные узлы. На рисунке 4 показаны три возможных ком-
бинации узел — дуга: дуга, соответствующая A → x, и две возможные дуги
для A → xB, одна для случая, когда A и B — различные символы, другая — ко-
гда A и B одинаковы. Это иллюстрирует простой путь от определения регуляр-
ного языка к графу, который определяет автомат, воспринимающий этот язык,
и далее к представлению графа как массива. Нетрудно записать программу, ав-
томатизирующую этот процесс. Такая программа получала бы на вход опреде-
ление языка типа 3 и выдавала бы на выходе программу, распознающую этот
язык.
        На практике часто важным бывает следующий результат:
        Если L — конечное множество цепочек в I*, то L может порождаться
регулярной грамматикой.
        Практически это означает, что любую функцию, область определения ко-
торой — конечное множество цепочек, можно вычислить с помощью достаточ-
но большой программы, не имеющей доступа к динамической памяти.
        Таким образом, определены четыре типа языков, от относительно не-
структурированного языка типа 0 до сильно структурированного языка типа 3.
Каждый из языков более высокого порядка представляет собой собственное
подмножество всех языков более низкого порядка. Этой последовательности
языков соответствует последовательность все более ограниченных автоматов:
машина Тьюринга, ЛО–автоматы, МП–автоматы, конечные автоматы. Эти че-
тыре класса автоматов различаются по степени доступа к принципиально неог-
раниченной ленте памяти. Каждый из них можно рассматривать как основной


                                                                             32