• скачать файл

Решение системы регулярных уравнений цель выполнения лабораторной

с. 1
Лабораторная работа № 3
Решение системы регулярных уравнений — цель выполнения лабораторной работы № 3.

Входные данные


Во входном файле (с именем INPUT.TXT) задается размерность системы регулярных уравнений n (1 ≤ n ≤ 8) а затем — ее коэффициенты:

α10 α11 α12α1n

α20 α21 α22α2n

…………………


αn0 αn1 αn2αnn

Максимальная длина регулярного выражения для каждого коэффициента равна 3.


Краткая теория


Рассмотрим краткую теорию решения уравнений с регулярными коэффициентами. Более подробные данные можно получить в [1] (раздел 3.5).

Определение. Регулярные выражения в алфавите Σ и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом:

1)  — регулярное выражение, обозначающее регулярное множество ;

2) e — регулярное выражение, обозначающее регулярное множество {e};

3) если aΣ, то a — регулярное выражение, обозначающее регулярное множество {a};

4) если p и q — регулярные выражения, обозначающие регулярные множества P и Q, то

а) (p+q) — регулярное выражение, обозначающее PQ;

б) pq — регулярное выражение, обозначающее PQ;

в) p* — регулярное выражение, обозначающее P*;

5) ничто другое не является регулярным выражением.

Принято обозначать p+ для сокращенного обозначения рр*. Расстановка приоритетов:



* (итерация) — наивысший приоритет;

конкатенация;

+ (объединение).

Например, 0 + 10* = (0 + (1 (0*))).

Таким образом, для каждого регулярного множества можно найти регулярное выражение, его обозначающее, и наоборот.

Введем леммы, обозначающие основные алгебраические свойства регулярных выражений. Пусть α, β и γ регулярные выражения, тогда:

1) α + β = β + α

2) * = e

3) α + (β + γ) = (α + β) + γ

4) α(βγ) = (αβ)γ

5) α(β + γ) = αβ + αγ

6) (α + β)γ = αγ + βγ

7) αe = eα = α

8) α = α =

9) α* = α+α*

10) (α*)* = α*

11) α+α = α

12) α+ = α

При работе с языками часто удобно пользоваться уравнениями, коэффициентами и неизвестными которых служат множества. Такие уравнения будем называть уравнениями с регулярными коэффициентами

X = aX + b,

где a и b — регулярные выражения. Можно проверить прямой подстановкой, что решением этого уравнения будет a*b:



aa*b + b = (aa* + e)b = a*b,

т.е. получаем одно и то же множество. Таким же образом можно установить и решение системы уравнений.



Определение. Систему уравнений с регулярными коэффициентами назовем стандартной системой с множеством неизвестных Δ = {X1, X2, …, Xn}, если она имеет вид:
X1 = α10 + α11X1 + α12X2 + … + α1nXn

X2 = α20 + α21X1 + α22X2 + … + α2nXn

………………………………………



Xn = αn0 + αn1X1 + αn2X2 + … + αnnXn

где αij — регулярные выражения в алфавите, не пересекающемся с Δ. Коэффициентами уравнения являются выражения αij.

Если αij = , то в уравнении для Xi нет числа, содержащего Xj. Аналогично, если αij = e, то в уравнении для Xi член, содержащий Xj, — это просто Xj. Иными словами,  играет роль коэффициента 0, а e — роль коэффициента 1 в обычных системах линейных уравнений.

Алгоритм решения.

Вход. Стандартная система Q уравнений с регулярными коэффициентами в алфавите Σ и множеством неизвестных Δ = = {X1, X2, …, Xn}.

Выход. Решение системы Q.

Метод: Аналог метода решения системы линейных уравнений методом исключения Гаусса.

Шаг 1. Положить i = 1.

Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы записать уравнения для Xi в виде

Xi = αXi + β,

где α — регулярное выражение в алфавите Σ, а β — регулярное выражение вида

β0 + βi+1Xi+1 + … + βnXn,

причем все βi — регулярные выражения в алфавите Σ. Затем в правых частях для уравнений Xi+1, …, Xn заменим Xi регулярным выражением α*β.

Шаг 3. Увеличить i на 1 и вернуться к шагу 2.

Шаг 4. Записать уравнение для Xn в виде Xn = αXn + β, где α и β — регулярные выражения в алфавите Σ. Перейти к шагу 5 (при этом i = n).

Шаг 5. Уравнение для Xi имеет вид Xi = αXi + β, где α и β — регулярные выражения в алфавите Σ. Записать на выходе Xi = = α*β, в уравнениях для Xi–1, …, X1 подставляя α*β вместо Xi.

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


ТЕКСТ ПРОГРАММЫ:
program TVPS3;

{Подключаем дополнительные модули}

uses crt;
{Создаем новый тип - запись}

type


tsrv1 =^srv1;

srv1 =record

value: string;

link: tsrv1;

end;
{Создаем новый тип - запись}

type


tsrv2 =^srv2;

srv2 =record

value: string;

linkSRV: tsrv1;

link: tsrv2;

end;
{Описываем переменные}

var

n, k: integer;



rv, con: string;

psrv1, nsrv1: tsrv1;

psrv2, nsrv2: tsrv2;
result : text;

input : text;

Put_res : string;

Put_inp : string;


{Процедура анализа введенного регулярного выражения}

procedure analysis_line;

var

s: char;


t1, t2: string;

i, j: integer;

tmp1: tsrv1;

tmp2: tsrv2;

begin

i :=1;


t1 :='';

t2 :='';


psrv1 :=nil;

s :=rv[i];

s :=upcase(s);

while s <>'=' do

begin

t1 :=t1+s;



inc(i);

s :=rv[i];

s :=upcase(s);

end;


delete(rv,1,pos('=',rv));

i :=1;


for j :=1 to n do

begin


str(j,t2);

if (pos('X'+t2,rv) =0) and (pos('x'+t2,rv) =0) then

rv :=rv+'+0'+'X'+t2;

end;


s :=rv[i];

s :=upcase(s);

while i <=length(rv) do

begin


t2 :='';

repeat


t2 :=t2+s;

inc(i);


s :=rv[i];

s :=upcase(s);

until (s ='+') or (i >length(rv));

inc(i);


s :=rv[i];

s :=upcase(s);

if t2[1] ='X' then t2 :='1'+t2;

new(tmp1);

tmp1^.value :=t2;

tmp1^.link :=nil;

if psrv1 =nil then

begin


psrv1 :=tmp1;

nsrv1 :=tmp1;

end

else


begin

nsrv1^.link :=tmp1;

nsrv1 :=tmp1;

end;


end;

new(tmp2);

tmp2^.value :=t1;

tmp2^.linkSRV :=psrv1;

tmp2^.link :=nil;

if psrv2 =nil then

begin

psrv2 :=tmp2;



nsrv2 :=tmp2;

end


else

begin


nsrv2^.link :=tmp2;

nsrv2 :=tmp2;

end;

end;
procedure change(t,i: integer);



var

tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7: tsrv1;

tx1, tx2: string;

begin


nsrv2 :=psrv2;

while i >1 do

begin

dec(i);


nsrv2 :=nsrv2^.link;

end;


case t of

0: begin


tmp1 :=nil;

tx1 :=nsrv2^.value;

tmp2 :=nsrv2^.linkSRV;

nsrv1 :=tmp2;

while nsrv1 <>nil do

begin


if pos(tx1,nsrv1^.value) >0 then

begin


tx2 :=nsrv1^.value;

delete(tx2,length(tx2)-1,2);

tmp3 :=tmp2;

while tmp3 <>nil do

begin

if pos(tx1,tmp3^.value) =0 then



begin

new(tmp4);

tmp4^.value :=tx2+'*'+tmp3^.value;

tmp4^.link :=nil;

if tmp1 =nil then

begin


tmp1 :=tmp4;

tmp5 :=tmp4;

end

else


begin

tmp5^.link :=tmp4;

tmp5 :=tmp5^.link;

end;


end;

tmp3 :=tmp3^.link;

end;

end;


nsrv1 :=nsrv1^.link;

end;


nsrv2^.linkSRV :=tmp1;

end;


1: begin

tmp1 :=nsrv2^.linkSRV;

tx1 :=nsrv2^.value;

nsrv2 :=psrv2;

while nsrv2 <>nil do

begin


nsrv1 :=nsrv2^.linkSRV;

tmp2 :=nsrv1;

while nsrv1 <>nil do

begin


if pos(tx1,nsrv1^.value) >0 then

begin


tmp3 :=nsrv1^.link;

delete(nsrv1^.value,length(nsrv1^.value)-1,2);

tx2 :=nsrv1^.value;

tmp4 :=tmp1;

tmp5 :=nil;

while tmp4 <>nil do

begin

new(tmp6);



tmp6^.value :=tx2+tmp4^.value;

tmp6^.link :=nil;

if tmp5 =nil then

begin


tmp5 :=tmp6;

tmp7 :=tmp6;

end

else


begin

tmp7^.link :=tmp6;

tmp7 :=tmp7^.link;

end;


tmp4 :=tmp4^.link;

end;


tmp7^.link :=tmp3;

if nsrv1 =tmp2 then

nsrv2^.linkSRV :=tmp5

else tmp2^.link :=tmp5;

end;

tmp2 :=nsrv1;



nsrv1 :=nsrv1^.link;

end;


nsrv2 :=nsrv2^.link;

end;


end;

end;


end;
{***** Процедуры упрощения решения при помощи аксиом *****}
procedure p1;

var


tx: string;

begin


nsrv2 :=psrv2;

while nsrv2 <>nil do

begin

nsrv1 :=nsrv2^.linkSRV;



while nsrv1 <>nil do

begin


if pos('X',nsrv1^.value) >0 then

begin


tx :=copy(nsrv1^.value,pos('X',nsrv1^.value),2);

delete(nsrv1^.value,pos('X',nsrv1^.value),2);

nsrv1^.value :=nsrv1^.value+tx;

end;


nsrv1 :=nsrv1^.link;

end;


nsrv2 :=nsrv2^.link;

end;


end;
procedure p2;

begin


nsrv2 :=psrv2;

while nsrv2 <>nil do

begin

nsrv1 :=nsrv2^.linkSRV;



while nsrv1 <>nil do

begin


if nsrv1^.value[1] ='0' then delete(nsrv1^.value,1,1);

nsrv1 :=nsrv1^.link;

end;

nsrv2 :=nsrv2^.link;



end;

end;
procedure p3;

var

i: integer;



begin

nsrv2 :=psrv2;

while nsrv2 <>nil do

begin


nsrv1 :=nsrv2^.linkSRV;

while nsrv1 <>nil do

begin

for i :=1 to length(nsrv1^.value) do



if nsrv1^.value[i] ='1' then delete(nsrv1^.value,i,1);

nsrv1 :=nsrv1^.link;

end;

nsrv2 :=nsrv2^.link;



end;

end;
procedure p4;

begin

nsrv2 :=psrv2;



while nsrv2 <>nil do

begin


nsrv1 :=nsrv2^.linkSRV;

while nsrv1 <>nil do

begin

if pos('0',nsrv1^.value) >1 then nsrv1^.value :='0';



nsrv1 :=nsrv1^.link;

end;


nsrv2 :=nsrv2^.link;

end;


end;
procedure p5;

begin


nsrv2 :=psrv2;

while nsrv2 <>nil do

begin

nsrv1 :=nsrv2^.linkSRV;



while nsrv1 <>nil do

begin


if nsrv1^.value =nsrv1^.link^.value then nsrv1^.value :='0';

nsrv1 :=nsrv1^.link;

end;

nsrv2 :=nsrv2^.link;



end;

end;
procedure p6;

var

tmp1, tmp2, tmp3: tsrv1;



begin

nsrv2 :=psrv2;

while nsrv2 <>nil do

begin


tmp1 :=nsrv2^.linkSRV;

nsrv1 :=tmp1;

tmp2 :=tmp1;

while nsrv1 <>nil do

begin

if nsrv1^.value ='0' then



begin

if nsrv1 =tmp1 then

begin

tmp1 :=tmp1^.link;



dispose(nsrv1);

nsrv1 :=tmp1;

tmp2 :=tmp1;

nsrv2^.linkSRV :=tmp1;

end

else


begin

tmp2^.link :=nsrv1^.link;

dispose(nsrv1);

nsrv1 :=tmp2^.link;

end;

end


else

begin


tmp2 :=nsrv1;

nsrv1 :=nsrv1^.link;

end;

end;


nsrv2 :=nsrv2^.link;

end;


nsrv2 :=psrv2;

while nsrv2 <>nil do

begin

if nsrv2^.linkSRV =nil then



begin

new(tmp3);

tmp3^.value :='0';

tmp3^.link :=nil;

nsrv2^.linkSRV :=tmp3;

end;


nsrv2 :=nsrv2^.link;

end;


end;
{*********************************************************}
{Основная программа}

begin
Put_res := 'C:\result.txt';

assign(result,Put_res);

rewrite(result);

Put_inp := 'C:\input.txt';

assign(input,Put_inp);

reset(input);

ClrScr;


readln(input,n);

writeln(result,'razmernost = ',n);

writeln('программа читает размерность уравнений');

writeln('и ее коэффициенты во входном файле C:\INPUT.TXT');

writeln('результат сохраняется в файле C:\RESULT.TXT');

writeln;


writeln('размерность системы: ',n);

for k :=1 to n do

begin

readln(input,rv);



writeln(k,'-е регулярное уравнение:');

write(' x',k,'=');

writeln(rv);

writeln(result,'uravnenie ',k,' = ',rv);

str(k,con);

rv :='x'+con+'='+rv;

analysis_line;

end;


for k :=1 to n do

begin


change(0,k);

change(1,k);

end;

p1;


p2;

p3;


p4;

p5;


p6;

writeln;


writeln('Решение системы регулярных уравнений:');

writeln(result,' ');

writeln(result,'reshenie system uravnenie : ');

writeln;


nsrv2 :=psrv2;

while nsrv2 <>nil do

begin

write(nsrv2^.value,'=');



write(result,nsrv2^.value,'=');

nsrv1 :=nsrv2^.linkSRV;

while nsrv1 <>nil do

begin


for k :=1 to length(nsrv1^.value)-1 do

if (nsrv1^.value[k] ='*') and (nsrv1^.value[k+1] ='*') then

delete(nsrv1^.value,k,1);

if nsrv1^.value[1] ='*' then delete(nsrv1^.value,1,1);

if nsrv1^.value[length(nsrv1^.value)] ='*' then

delete(nsrv1^.value,length(nsrv1^.value),1);

if nsrv1^.link =nil then

begin


write(nsrv1^.value);

write(result,nsrv1^.value);

end

else


begin

write(nsrv1^.value,'+');

write(result,nsrv1^.value,'+');

end;


nsrv1 :=nsrv1^.link;
end;

writeln;


writeln(result,'');

nsrv2 :=nsrv2^.link;

end;

writeln;


write('Для выхода нажмите любую клавишу...');

readkey;


close(input);

close(result);

end.

Пояснение

Во входном файле (с именем INPUT.TXT) задается размерность системы регулярных уравнений n,

а затем —каждый коэффициент с новой строки.

Запускаете программу, в результате программа выполняется и выводит данные на экран. Потом данные сами записываются в файле result.txt на диске C:\



Результаты работы :
с. 1