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

   Таким образом, порождающие грамматики общего вида относятся к рекур-
сивно полным исчислениям.
   Грамматики G и G' называются эквивалентными, если они порождают один
и тот же язык, т.е. L(G) = L(G').
      Сформулируем основной результат, связанный с машинами Тьюринга:
      Можно построить машину Тьюринга, воспринимающую любой язык, по-
рождаемый грамматикой без ограничений.
      Для иллюстрации этого результата посмотрим грамматику G′, определен-
ную в следующих таблицах.




     Абстрактный язык на основе определения простых арифметических
                         выражений в Алголе 60

 Словарь

                       V=N∪T
                       N = S, терм, сл, умн, множитель, переменная, константа
                       T = +, 1, *, /, (,), «любая буква», «любое целое»
Грамматика G

                       P1 S → терм           P7 множитель → переменная

                       P2 S → S сл терм      P8 множитель → константа

                       P3 сл → +             P9 множитель → (S)

                       P4 сл → –             P10> переменная → «любая буква»

                       P5 терм → множи-
                                             P11 константа → «любое целое»
                       тель



                                                                             23