Б2В1 Управление с регулярными коэффицентами и их системы.

 

Х=аХ+b, где а и b - регулярные выражени. Прямой подстановкой можно проверит, что Х=а*b

а*b=aa*b+b

Можно рассмотривать системы уравнений, определяющие языки.

 

 

Систему уравнений с регулярными коэффицентами называют стандартной системой, с множеством неизвестных дельта={x1,x2,...xn}, если она имеет вид

Система

Х1=АЛФА10+АЛФА11Х1+АЛФА12Х2+АЛФА1nХn

Х2=АЛФА10+АЛФА21Х1+АЛФА22Х2+АЛФА2nХn

Хn=АЛФАn0+АЛФАn1Х1+АЛФАn2Х2+АЛФАnnХn

 

Алгоритм решения стандартной системы уравнений с регулярными коэффицентами.

ВХОД: Стандартная система Q уравнений с регулярными коэффицентами в алфавите E и множеством неизвестных дельта={x1,x2....Xn}

ВЫХОД: Решение системы Q в виде x1=АЛФА1, Х2=АЛФА2....Хn=АЛФАn, где АЛФАi регулярное выражение в алфавите E.

ШАГ1: i:=1

шАГ2: Если i=n то перейти к шагу 4 иначе с помощью тождеств леммы записать уравнение Хi в виде Хi=АЛФАX1+БЕТА, где АЛФА-регулярное выражение в алфавите Е

а БЕТА-регулярное выражение вида БЕТА=БЕТА0+БЕТАiХi+1...+БЕТАnХn причем все БЕТА регулярные выражения в алфавите Е.

 Затем в правых частях уравнения для Xi+1...Xn заменить Хi регулярным выражением АЛФА*БЕТА

ШАГ3: i:=i+1

       вернуться к шагу 2

ШАГ4: Записать уравнения для Xn  в виде Xn=АЛФАXn+БЕТА, где АЛФА и БЕТА регулярные выражения в алфавите Е. Перейти к шагу 5

ШАГ5: Уравнение для Хi имеет вид Xi=АЛФАXi+БЕТА, где АЛФА и БЕТА регулярные выражения в алфавите Е. ЗАписать на выходе Хi=АЛФА*БЕТА

и в уравнения для Хi-1...X1 подставить АЛФА*БЕТА вместо Хi.

ШАГ6: Если i=1, то остановиться, иначе i:=i-1 вернуться к шагу 5.