Система основных событий
В эти системы мы включим те из наиболее часто встречающихся событий, которые используются при записи регулярных выражений на практических занятиях и курсовой работе.
Пусть дан алфавит X{x1, x2, …, xm}.
1. Событие, состоящее из всех слов входного алфавита (всеобщее событие). F = {x1 v x2 v …v xm}
2. Событие, содержащее все слова, оканчивающиеся буквой xi.
S = {x1 v x2 v …v xi v …v xm}xi = Fxi.
3. Событие, содержащее все слова, оканчивающиеся отрезком слова l1
S = F l1
4. Событие, содержащее все слова, начинающиеся с отрезка слова l1и оканчивающиеся на l2: S = l1 F l2
5. Событие, содержащее только однобуквенные слова входного алфавита S = x1 v x2 v …v xm
6. Событие, содержащее только двухбуквенные слова входного алфавита S = (x1 v x2 v …v xm)( x1 v x2 v …v xm)
7. Событие, содержащее все слова длиной r
S = (x1 v x2 v …v xm)( x1 v x2 v …v xm)… (x1 v x2 v …v xm)
Всего r членов
8. Событие, содержащее все слова, длина которых кратна r
S = {(x1 v x2 v …v xm)( x1 v x2 v …v xm)… (x1 v x2 v …v xm)}
r членов
9. Событие, состоящее из всех слов алфавита X{x1, x2}, не содержащих комбинации букв x1x1 и оканчивающихся буквой x2
S = {x2 v x1x2}
10. Событие, состоящее из всех слов алфавита X{x1, x2}, не содержащих серии из двух букв x1 и оканчивающихся буквой x2
S = {x2 v x1x2 v x1x1x2 v … v x1x1…x1x2}
r-1 членов.
Рассмотрим пример составления регулярного выражения, определяющего закон функционирования конечного автомата.
Пример. Записать в виде регулярного выражения алгоритм работы автомата, сравнивающего два двоичных числа, представленных в последовательном коде. Количество разрядов числа – произвольно.
предыдущая темаследующая