03, 05 сентября: Регулярные выражения

Ðåãóëÿðíûå âûðàæåíèÿ.
Çàäàéòå ðåãóëÿðíûìè âûðàæåíèÿìè ñëåäóþùèå ìíîæåñòâà ñëîâ:
ñëîâà â àëôàâèòå {a, b}, òàêèå ÷òî íà òðåòüåì ìåñòå îò íà÷àëà ñëîâà ñòîèò áóêâà a, à íà ÷åòâ¼ðòîì ìåñòå îò
êîíöà áóêâà b;
á) ñëîâà â àëôàâèòå {a, b}, â êîòîðûõ ÷èñëî áóêâ a ÷¼òíî;
â) ñëîâà â àëôàâèòå {a, b}, íå ñîäåðæàùèå ïîäñòðîêè ab;
ã) ñëîâà â àëôàâèòå {a, b}, íå ñîäåðæàùèå ïîäñòðîêè abb;
ä) ñëîâà â àëôàâèòå {a, b}, â êîòîðûõ ÷èñëî áóêâ a ÷¼òíî, à ÷èñëî áóêâ b íå÷¼òíî;
å) ñëîâà â àëôàâèòå {a, b, c}, â êîòîðûõ íåò äâóõ ñîñåäíèõ áóêâ b;
¼) ñëîâà â àëôàâèòå {a, b, c}, ñîäåðæàùèå ïîäñëîâî âèäà bxa, ãäå x ïðîèçâîëüíàÿ áóêâà àëôàâèòà;
æ) ñëîâà â àëôàâèòå {a, b, c}, â êîòîðûõ çà áóêâîé a îáÿçàòåëüíî ñëåäóåò áóêâà c;
ç) ñëîâà â àëôàâèòå {a, b, c}, â êîòîðûõ çà áóêâîé a íå ìîæåò èäòè áóêâà b;
è) êîíñòàíòû òèïà double ÿçûêà Ñè (íàïðèìåð, 1, 9.86, .6, 6.2e-23).
Çàäà÷à 2. Íàïèøèòå ðåãóëÿðíûå âûðàæåíèÿ, çàäàþùèå ñëåäóþùèå ÿçûêè íàä àëôàâèòîì {a, b}:
à) {w | |w| 6 3};
á) {w | |w| > 4};
â) {w | |w|b > 2};
ã) {w | |w| = 2 èëè |w|a = 3};
ä) {w | |w| = 3 èëè |w|a > 5}.
Çàäà÷à 3. Îïèøèòå ìíîæåñòâà ñëîâ, çàäàâàåìûå ñëåäóþùèìè ðåãóëÿðíûìè âûðàæåíèÿìè: à) (a + c)∗ ;
á) (a + b)∗ a;
â) b(b + c)∗ ;
ã) a(a + b)∗ a;
ä) a∗ ba∗ ba∗ ba∗ ;
å) (a + b)∗ b(a + b)(a + b);
¼) b∗ (a + (ab+ )∗ ).
Çàäà÷à 4. ßâëÿåòñÿ ëè ÿçûê {an | ñóùåñòâóåò òàêîå p > n, ÷òî p ïðîñòîå è p + 2 ïðîñòîå} ðåãóëÿðíûì?
Çàäà÷à 5. Äîêàæèòå ñëåäóþùèå ðàâåíñòâà: à) (1 + e + ee + . . . + en−1 )(en )∗ = e∗ äëÿ ëþáîãî n > 1;
á) (e∗ f )∗ e∗ = (e + f )∗ ;
â) 1 + e(f e)∗ f = (ef )∗ .
Çàäà÷à 6. Óïðîñòèòå ðåãóëÿðíûå âûðàæåíèÿ: à) (a + b + ab)∗ ;
á) (a∗ b)∗ + (b∗ a)∗ ;
â) (abbaab + abbaaba)∗ ;
ã) (a + b)∗ ab(a + b)∗ + (a + b)∗ a + b∗ ;
ä) 1 + aa∗ + bb∗ ;
å) (a + b)∗ (ab + ba)(a + b)∗ + a∗ + b∗ .
Çàäà÷à 7. Äîêàæèòå, ÷òî åñëè ðåãóëÿðíûå âûðàæåíèÿ e, f è g òàêîâû, ÷òî e = ef + g è ε ∈
/ L(f ), òî e = gf ∗ .
R
R
Çàäà÷à 8. à) Äîêàæèòå, ÷òî äëÿ ëþáûõ äâóõ ÿçûêîâ L1 è L2 âûïîëíåíî ðàâåíñòâî (L1 ·L2 )R = LR
2 ·L1 (ÿçûê L
R ∗
∗ R
ñîñòîèò èç ñëîâ ÿçûêà L, íàïèñàííûõ çàäîì íàïåð¼ä). á) Ñóùåñòâóåò ëè òàêîé ÿçûê L, ÷òî (L ) 6= (L ) ?
Çàäà÷à 9. Äîêàæèòå, ÷òî åñëè ÿçûê L çàäàåòñÿ ðåãóëÿðíûì âûðàæåíèåì, òî è ÿçûê LR òîæå çàäàåòñÿ ðåãóëÿðíûì âûðàæåíèåì.
Çàäà÷à 1.
à)