Регулярные выражения

Некоторые операции над языками

Пусть и языки.

1. Объединение двух языков и это множество строк, которые содержатся либо в , либо в , либо в обоих языках:
.

Пример.

.

2. Конкатенация двух языков и это множество строк, которые можно образовать путем дописывания к любой цепочке из любой цепочки из :
.

Пример.

.

3. Итерация языка (замыкание Клини) – это множество всех строк, которые можно образовать путем конкатенации любого количества строк из .

Пример. Если язык из двух односимвольных строк, то это все строки, состоящие из нулей и единиц. Более формально:

.

Примеры.

Пусть множество , множество . Мы можем рассматривать множества и двояко. С одной стороны, представляет собой алфавит, состоящий из прописных и строчных букв, а алфавит, состоящий из цифр. С другой стороны, поскольку символ можно рассматривать как строку единичной длины, множества и представляют собой языки, состоящие из строк единичной длины.

множество односимвольных строк из букв и цифр.

множество строк, состоящих из буквы, за которой следует цифра.

множество всех четырехсимвольных строк из букв.

множество всех строк из букв, включая пустую строку .

множество всех строк из букв и цифр, начинающихся с буквы.

множество всех строк из одной или нескольких цифр.

Регулярное выражение – это способ описания некоторых подмножеств строк, т.е. – способ определения некоторых языков.

Регулярное выражение можно рассматривать как шаблон, которому должны удовлетворять строки, принадлежащие некоторому языку. Если строка попадает под шаблон, определяемый регулярным выражением, то она принадлежит языку, который определен с помощью этого регулярного выражения.

Регулярные выражения строятся из более простых регулярных выражений с использованием набора правил. Каждое регулярное выражение обозначает (задает) язык . Правила определяют, каким образом из языков, заданными подвыражениями выражения , формируется язык .

Дата добавления: 2013-12-14