Системне програмування

3. Регулярні множини та регулярні вирази, їх звязок із скінченними автоматами.
Основні тотожності в алгебрі регулярних виразів.

Регулярна множина в алф. S (ск. алфавіт) задається рекурсивно:

1) Æ - рег. множ.;

2) { e } - рег. мн. в алф. S;

3) { a } - рег. мн. " a Î S;

4) якщо P та Q - рег. мн., то P È Q, PQ, P^* - рег. мн.

Регулярний вираз в алф. S та відповідні рег. множ, які вони позначають, задається рекурсивно:

1) Æ - рег. вираз, що позначає рег. множ. Æ;

2) e - рег. вираз, що позначає рег. множ. { e };

3) a - рег. вираз " a Î S, що позначає рег. множ. { a };

4) якщо p та q - рег. вираз, що позначає відп. рег. мн. P та Q, то (p + q) - рег. вираз, що позн. P È Q, (pq) - рег. вираз, що позн. PQ, (p)^* - рег. вираз, що позн. P^*.

Алгебра регулярних виразів: E_R=<B(S^*),{È,×,^*}>. Нехай a,b,g - рег. вирази, тоді

1) a+b=b+a,

2) a+(b+g)=(a+b)+g,

3) a×(b+g)=ab+ag,

4) ae=ea=a,

5) a^*=a+a^*,

6) a+a=a,

7) Æ^*=e,

8) a×(bg)=(ab)g,

9) (a+b)×g=ag+bg,

10) Æa=aÆ=Æ,

11) (a ^* ) ^* =a ^*, 12) a+Æ=a

Теорема. Деяка мова задається скінченим автоматом Û коли мова є регулярною множиною.

Системне програмування

Вивід у граматиці. Дерево виводу. Лівостороння та правостороння стратегії виводу.

Нехай G-граматика. Будемо казати, що послідовність v безпосередньо породжує послідовність w: vÞ w, якщо v=xUy, w=xuy, та існує правило U::= u

Будемо казати, що послідовність v породжує w: vÞ₊ w, якщо існує посліовність v=u₀ Þ u₁Þ … Þ u_n =w

Лівостороння стратегія виводу w в G - це така стратегія безпосереднього виводу де на кожному кроці береться перший з ліва направо нетермінал. Правостороння протилежна лівосторонній.