Page 24 - 4625

П4. Записати рівняння = a +b, де a, b – регулярні

вирази в алфавіті . Це можливо, оскільки на кожному кроці
виконання П2 для кожного i < n у правій частині рівняння
для не буде невідомих , , …, +1 . Перейти на П5,
2
1
при цьому і буде рівень n.
П5. Для рівняння з , котре має вигляд = a + b, де

∗
a, b - регулярні вирази в алфавіті , записати = b. У

рівняння для , , …, −1 підставити замість регулярний

2
1
∗
вираз b.
П6. Якщо і рівне 1, то зупинитися, інакше i зменшити на
1 та перейти на П5.
Приклад 4. Розв'язати систему лінійних рівнянь:
X = X + Y +
1
2
3
X = X + Y +
1
3
2
з першого рівня: X = *( Y + ).
1
2
3
Підставимо значення X в друге рівняння та затвердимо
подібні члени:
Y= *( Y+ )+ Y+ = * Y+ * + Y+
1 1
3
2
3
2
2
1 1
3
1 1
2
3
= ( * + )Y+( * + ),
3
3
1 1
1 1
2
2
таким чином:
Y= ( * + )* ( * + ).
3
1 1
3
2
1 1
2
Підставимо Y в перше рівняння:
X = X + ( * + )* ( * + )+
3
1
3
1 1
3
2
2
2
1 1
звідси:
X = *( ( * + )* ( * + )+ ).
3
3
3
1 1
2
1
2
2
1 1

2.5 Польський інверсний запис для регулярних
виразів
Польський інверсний запис (ПОЛІЗ) для регулярних
виразів будується на основі початкового регулярного виразу на
основі наступних правил:
1. Порядок операндів у початковому виразі і в перетво-
реному виразі співпадають.
23