Основы конструирования компиляторов



             

Типы грамматик и их свойства - часть 3


Покажем, что существует такое m, что Tm = Tm-1. Поскольку для каждого i

1 справедливо Ti
Ti-1, то если Ti
Ti-1, то число элементов в Ti по крайней мере на 1 больше, чем в Ti-1. Пусть |N
T| = k. Тогда число строк в (N
T)+ длины меньшей или равной

n равно k + k2 + ... + kn

nkn. Только эти строки могут быть в любом Ti. Значит, Tm = Tm-1 для некоторого m
nkn. Таким образом, процедура, вычисляющая Ti для всех i
1 до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм. __




Содержание  Назад  Вперед