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

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

Прежде чем дать определение РВ, рассмотрим 3 операции над языками, соответствующие операторам РВ.

Пример

Дан язык L={0, 11}. Определить язык L^*.

L⁰={e}

L¹={0, 11}

L²={00, 011, 110, 1111}

L³={000, 0011, 0110, 1100, 01111, 11011, 11110, 111111}

…

Для вычисления L^* необходимо вычислить Lⁱ для каждого i и объединить эти языки.