Page 23 - 4625

За аналогією до класичної алгебри розглянемо лінійне
рівняння в алгебрі регулярних виразів: X = aX + b, де a, b –
регулярні вирази. Взагалі таке рівняння залежно від a та b може
мати безліч розв’язків, наприклад: X = a*(b + ), за умови, що
a позначає -ланцюжок. Тоді  може бути навіть і нерегулярним
виразом. Серед всіляких розв’язків рівняння з регулярними
коефіцієнтами виберемо найменший розв’язок X = a*b, який
назвемо найменша нерухома точка. Щоб перевірити, що a*b
розв’язок рівняння в алгебрі регулярних виразів, підставимо
його в початкове рівняння та перевіримо тотожність виразів
на основі системи тотожних перетворень:
a*b = aa*b+b = (aa*+)b = (a ( + a +aa+…) + )b = ( + a +
aa +…)b = a*b.
В алгебрі регулярних виразів також розглядають і
системи лінійних рівнянь з регулярними коефіцієнтами:
X = a X + a X + … + a X + b
1
1n n
11 1
12 2
1
X = a X + a X + … + a X + b
21 1
2
2n n
22 2
2
………………..
n
1n 1
X = a X + a X + … + a X + b n
2n 2
nn n
де: a , b , i, j = 1..n.
ij
i
Метод розв’язку системи лінійних рівнянь з регуляр-
ними коефіцієнтами нагадує метод виключення
П1. Покласти i = 1.
П2. Якщо i рівне n, то перейти на П4. Інакше і–е
рівняння, використавши систему тотожних перетворень, запи-
сати у вигляді: = a +b,

де: a - регулярний вираз в алфавіті ;
b – регулярний вираз виду:
 + , ,  + …  , де  (k=0, i+1, ... n) -
0 +1 +1 +2 +2 +2
регулярні коефіцієнти. Далі, в правих частинах рівнянь зі
змінними +1 , +2 , … у лівій частині рівняння підставити

замість значення b.
∗

П3. Збільшити i на 1 та перейти на П2.
22