Cтраница 4
Определим еще понятие циклической глубины регулярного выражения, подразумевая под ней максимальное число вложенных друг в друга пар итерационных скобок, содержащихся в этом выражении. [46]
Переключатель - г разрешает появление регулярных выражений в строке поиска. [47]
При применении операции расширения из регулярного выражения получается, как нетрудно видеть, снова регулярное выражение; при этом, однако, минимальный ранг входящих в него комплексов повышается посравне-нению с исходным выражением не менее, чем на единицу. [48]
Операция расширения может применяться к любому регулярному выражению ( и даже к произвольной формуле) над алфавитом, содержащим все буквы входного алфавита автомата и символы всех его комплексов. Крг) - произвольная формула указанного вида, то операция расширения состоит, во-первых, в замене всех символов комплексов их явными выражениями через пути, а, во-вторых, в подстановке вместо символов внутренних состояний а, в каждом из возникших таким образом путей символов комплексов высших рангов в соответствии со сформулиро-панным выше правилом замены. [49]
Для такого автомата существует всего одно регулярное выражение. [50]
Следующее утверждение показывает, что почти всегда регулярное выражение, построенное при помощи алгоритма А, не минимально. [51]