Лекция 3
Регулярные множества,
регулярные выражения
Определение 3.1
• Пусть - некоторый алфавит. Регулярное множество
в алфавите определяется рекурсивно следующим
образом:
• 1. пустое множество является регулярным в
алфавите ;
• 2. {} – регулярное множество в алфавите ;
• 3. если а , то {а} – регулярное множество в
алфавите ;
• 4. R является регулярным множеством, если R
представимо в виде 5. PQ, или PQ, или P*, где P и
Q – регулярные множества в алфавите ;
• 6. других регулярных множеств в алфавите нет.
• Таким образом, множество в алфавите является
регулярным тогда и только тогда, когда оно либо
пусто, либо содержит единственную пустую цепочку,
либо содержит некоторый символ этого алфавита,
либо получено из регулярных множеств в данном
алфавите посредством операций объединения,
конкатенации или итерации, примененных к
регулярным множествам.
• Заметим, что из определения регулярного множества
следует, что:
• 1. любое конечное множество является регулярным
множеством;
• 2. объединение любого числа конечных множеств
является также регулярным множеством;
•
3. некоторое бесконечное множество является
регулярным тогда и только тогда, когда оно
составлено из символов некоторого алфавита с
использованием операции итерации (т.е. оно
содержит все возможные цепочки, которые можно
построить из символов этого алфавита), либо когда
это множество является объединением любого
числа так построенных бесконечных множеств и
любого числа конечных множеств (см также
свойства регулярных выражений).
• Пример 3.1.
• 1. {1} – регулярное множество,
• {1,2} – регулярное множество, полученное
посредством выполнения операции объединения
над регулярными множествами {1} и {2},
• {12} – регулярное множество, полученное
посредством выполнения операции конкатенации
над регулярными множествами {1} и {2},
• {1,2,12} – регулярное множество, полученное
посредством выполнения операций конкатенации
(над регулярными множествами {1} и {2}) и двух
операций объединения
• По определению язык – это множество цепочек.
Таким образом, любое регулярное множество
цепочек также есть язык. Задать такой язык
(некоторое регулярное множество) можно задав
регулярное выражение, обозначающее это
регулярное множество.
Определение 3.2
• Регулярные выражения в алфавите и регулярные
множества, которые они обозначают, определяются
рекурсивно следующим образом:
• 1. - регулярное выражение, обозначающее
регулярное множество ,
• 2. – регулярное выражение, обозначающее
множество {},
• 3. если а , то а – регулярное выражение,
обозначающее регулярное множество { а },
• 4. если p и q – регулярные выражения,
обозначающие регулярные множества P и Q
соответственно, то:
• а) (p + q) – регулярное выражение, обозначающее
регулярное множество PQ,
• б) (pq) – регулярное выражение, обозначающее
регулярное множество PQ,
• в) (p)* - регулярное выражение, обозначающее P*;
• 5. ничто другое не является регулярным
выражением.
• Пример 3.2. Приведем несколько примеров
регулярных выражений и обозначаемых ими
множеств:
• 1) 01 обозначает множество {01}
• 2) 0* обозначает множество {0}*
• 3) (0+1)* обозначает множество {0,1}*
• 4) (0+1)*011 обозначает множество всех цепочек,
составленных из нулей и единиц и оканчивающихся
цепочкой 011.
• 5) (a+b)(a+b+0+1)* обозначает множество всех
цепочек из {0,1,a,b}*, начинающихся с а или b
• 6) (00+11)*((01+10)(00+11)*(01+10)(00+11)*)*
обозначает множество всех цепочек нулей и
единиц, содержащих четное число нулей и четное
число единиц.
• Для каждого регулярного множества можно найти, по
крайней мере, одно регулярное выражение,
обозначающее это множество, и для каждого
регулярного выражения можно построить регулярное
множество, обозначаемое этим выражением. Для
каждого регулярного множества существует
бесконечно много обозначающих его регулярных
выражений.
Определение 3.3
• Будем говорить, что два регулярных выражения
равны (=), если они обозначают одно и тоже
множество.
Основные алгебраические свойства
регулярных выражений
•
•
•
•
•
•
1. + = , + =
2. + = +
3. + ( + ) = ( + ) + = + +
4. () = () =
5. = = и = =
6. ( + ) = +
•
•
•
•
•
•
•
•
•
•
7. ( + ) = +
8. ** = *
9. (*)* = *
10. * = * *
11. * = + *
12. * = и * =
13. (* + *)* = (**)* = ( + )*
14. ()* = ()*
15. (*)** = (+)*
16. (*)* = (+)* + и (*)* = (+)* +
• Доказательство:
• Пусть и обозначают множества L1 и L2
соответственно. Тогда + обозначает L1 L2, а +
обозначает L2 L1. Но L1 L2 = L2 L1 по
определению объединения. Следовательно, + =
+ (Доказать отдельные равенства самостоятельно).
Задание 4
• Описать свойства цепочек, принадлежащих языку,
заданному указанным регулярным выражением.
Привести примеры четырех цепочек, принадлежащих
данному языку.
1. 0(0+1)*(a+b)
2. 1(0+1+2)*(a+b)(1+2)*
3. (0+1+2)*(a+b)* 21
4. (1+2)+(a+b+с)(1+2)*22
5. (0+2)*(a+b)(1+2)*11
6. 33(3+4+5)*(1+2)*7
7. 7(6+7+8)*(a+b)(1+2)*6
8. (a+b)(1+2)*(6+7+8)*1
9. (1+2+3)*(1+2)5
10. (4+5)(4+5+6)*(7+8)*9
11. (6+7)*(8+9)(1+2)*8
12. (1+2+3)*(4+5+6)*(1+2)
13. (0+1)(a+b)*(3+4+5)*7
14. (3+4)*5(6+7)*9
15. 1(2+3+4)*7(5+6)*8
16. 3(4+5)*(6+7)(8+9)*1
17. (a+b)(1+2+4)*(6+7)
18. (a+b)*2(3+4)*6
•
•
•
•
•
•
•
•
•
•
19. (1+2)*(4+5)(3+6)*7 •
20. (4+5)*(1+2)(6+7)*81 •
21. (3+4)*5(6+7)*
•
22. (5+6+7)*(a+b)(1+2)* •
23. (0+2)(a+b)*(1+2)*1 •
24. (3+4)*(a+b)(1+2)
•
25. (2)*(a+b)(1+2)*3
•
26. 1(0)*(1+2)*12
•
27. 3(2)*(a+b)(4+5)*
•
28. 1(3+2)*4(1+2)*
•
29. (0+2)(a+b)*(1+2)*
30. (1+2)*2(1+2)*1
31. (8+7)(6+9)*(1+2)90
32. (3+2+4)*(1+5+2)*(6+7)+
33. (1+5)(3+4)*(6+7+8)*1
34. (4+5+6)*567(76+77)*9
35. 121(21+32+41)*7(52+62)*8
36. 123(34+25)*(63+71)(18+92)*1
37. (1a+2b)(12+21+43)*(6+7)
38. (a2+b3)*2121(113+421)*611
•
•
•
•
•
•
•
•
•
•
•
•
39. (121+211)*(4234+5546)(563+656)*7
40. (34+45)*(541+222)(226+347)*81
41. (13+64)*57(68+79)*
42. (52+62+74)*(a1+b1)(12+23)*
43. (012+221)(a+b)*(13343+24444)*14
44. (30+48)*(a+b)(111+232)+
45. (23)*(1qqa+b322)(231+4e2)*3
46. 134(02)*(11+22)*132
47. 332(221)*(111a+2222b)(4ww+322)*
48. 1221(23+s2)*42(12+22)*
49. (0kd+2)(dsaa+bss)+(saz1+ddw2)*
50. (32q1+2xsw)*2222(1sd+2df)*12
