. . ѻ
________ ..
18 2012 .
21
230102 " "
____________ ..
()
______________2012_ . ______________
____________ __________________________
() (, )
____________ __________________________
() (, )
____________ __________________________
() (, )
. --
2012.
. . ѻ
________ ..
18 2012.
,
21
: -
: Pascal, ,
____________ ..
()
____________ ..
()
2012 .
,
, , .
Program MT; {Mashina Tiuringa}
uses crt;
Type
M= array [1..100] of integer;
Var
f,q:M; { (f) (q)}
fi:integer;
Procedure PreObr(var s:string; i:integer);
Begin
write(q[f[fi]]);
fi:=f[fi];
end;
Var
s:string;
l:integer; { (- )}
{MaxState} Ms:integer; {- }
{MaxInSymbol} Mis:integer; {- , }
|
|
{MaxOutSymbol} Mos:integer; {- , }
{ (f) (q)}
i,j:integer;
x,y:shortint;
Begin
write(' - : ');
x:=whereX;
y:=whereY;
repeat { - , >0}
readln(Ms);
if Ms > 0 then break;
gotoXY(x,y);
until false;
write(' : ');
readln(s);
l:=length(s); // - - .
Writeln(' f q: ');
Writeln('{f}');
{ ,
, }
for i:=1 to Ms do
write('---');
writeln;
write('Ms: ');
for i:=1 to Ms do
write('| ',i);
writeln('|');
for i:=1 to Ms do
write('---');
writeln;
write('fi: '); { }
{ ,
( ) .}
for i:=1 to Ms do
Begin
write('|');
x:=whereX;
y:=whereY;
readln(f[i]);
gotoXY((x+2),y);
end;
writeln('|');
Writeln('{q}');
for i:=1 to Ms do
write('---');
writeln;
write('Ms: ');
for i:=1 to Ms do
write('| ',i);
writeln('|');
for i:=1 to Ms do
write('---');
writeln;
write('qO: '); {qO qOut}
for i:=1 to Ms do
Begin
write('|');
x:=whereX;
y:=whereY;
readln(q[i]);
gotoXY((x+2),y);
end;
writeln('|');
Write(' , : ');
readln(fi);
{ , .}
Write(' : ');
for i:=1 to l do
PreObr(s,i);
Writeln;
Writeln(' Press Enter...');
readln;
end.
PreObr:
l:=length(s) | C1 | |
for i:=1 to l do | C2 | N |
begin | ||
write(q[f[fi]])); | C3 | N |
fi:=f[fi]; | C4 | N |
end; | C5 |
T( )=c1*1+c2*N+c3*N+c4*N+c5*1= (1+c5) +N*(c2+c3+c4)= N, , , N = Q(n).
1. .
2. - .
3. F Q.
4. .
5. .
1, 5, q , 0, 5 q.
5 f 2, , ( ) , 2, q, , ,
4 6 0 1 f q.
|
|
.
- . , , , . , , . : , .
, . , , , .
, .
1. , , 8. // , = Introduction to Automata Theory, Languages, and Computation. .: , 2002. . 528.
2. http://ru.wikipedia.org/wiki/_
3. 2008 .
4. . , . , . . : . , , 2001