Регулярні множини. (Тема 3) презентация

Тема 3: Регулярні множини   1. Регулярні множини і регулярні вирази 2. Побудова регулярного виразу по праволінійній граматиці 3. Алгоритм побудови праволінійної граматики по регулярному виразу

1. Регулярні множини і регулярні вирази Нехай V - скінченний алфавіт. Рекурсивно регулярна множина в алфавіті визначається так: 1)     –регулярна множина в алфавіті V; 2)   {e} –регулярна множина в алфавіті V; 3)    {a}–регулярна множина в алфавіті V для всіх a є V; 4)  якщо – P,Q регулярні множини в V, то P U Q, PQ, P*– регулярні множини в алфавіті V ; 5)    Ніщо інше не є регулярною множиною в V.

Регулярний вираз в алфавіті V визначається рекурсивно: 1)  - регулярний вираз, що позначає регулярну множину ; 2) e - регулярний вираз, що позначає регулярну множину {e}; 3) якщо аV, то а - регулярний вираз, що позначає регулярну множину {a}; 4) якщо p,q - регулярні вирази, що позначають регулярні множини P,Q, то  (p+q) регулярний вираз, що позначає регулярну множину PQ;  (pq) регулярний вираз, що позначає регулярну множину PQ;  (p)* регулярний вираз, що позначає регулярну множину P*; 5)    ніщо інше не є регулярним виразом.

Приклади регулярних виразів. 1)    01 позначає множину {01}; 2)    0* позначає множину {0}*; 3)    (0+1)* позначає множину {0,1}*; 4) (0+1)*011 позначає множину усіх ланцюжків, що складаються з нулів і одиниць і закінчуються ланцюжком 011; 5)    (a+b)(a+b+0+1)* позначає множину усіх ланцюжків з множини {a,b,0,1}*, що починаються з а або b; 6)    (11+00)*(01+10)(11+00)*

Тотожності над регулярними виразами Доведення. 1) Нехай ,  позначають множини A, B. Тоді + позначає A B, + позначає BA. Оскільки A B =BA, то + =+.

2. Побудова регулярного виразу по праволінійній граматиці

X= X+ X= *

Завдання додому: Розв’язати систему рівнянь із регулярними коефіцієнтами:

3. Алгоритм побудови праволінійної граматики по регулярному виразу

Програмна реалізація