Orshanskiy

?&2.& - ,*+1."1 /*% '&0=*,+ 31:1.+% - 0"3&,1 0 .#F-#.+1? F#/#D+ ,#2/=; 3#F '+0#"$: «P1 F#)="$ ()3#"$ >#;*=» +*+ D"&-.+)(/$ - "#,&? 21 /(A1. 5&?&<#1" &D1.$ 0+*$.& – 31#*$.& ?&21" 0'#0"+ &" "31A-D1"=31A *+:.+A '&'="&, F# ,&."10".

P1 0?&"3+"1, ,#, -#:+ "&-#3+M+ '& ,&?#./1 '&0=*#C" '3&<3#??( - 2C3+, ,#, &.+ .#2+?#C" ,.&',+ - ,*+1."1 + ". /. E"& &".+?#1" -#:1 -31?% + -.+?#.+1, # &.+ .13-.+D#C", D"& -= .1 <&"&-+"10$ + .1 &)/(?=-#1"1 /3(<(C F#/#D(. H'3&D1?, 10*+ (2 -= .#)*C/#1"1 F# .+?+, '3&,&."3&*+3(;"1, D"&)= &.+ -=)3#*+ .(2.=; >#;*, .(2.=; %F=, '3&<3#??+3&-#.+% + .(2.(C F#/#D(, -,*CD+*+/&",*CD+*+ '3&-13,+ + ". /.

P1 0?&"3+"1 '3&0"& "#, - ?&.+"&3, &2+/#% &"-1"#. !13-13, '3&-13%CM+; 31:1.+% (D#0".+,&-, ?&21" )="$ '131<3(21.. 9. ?&21" )="$ -31?1..& -

.13#)&D1? 0&0"&%.++ – L"& "+'+D.& /*% 0&31-.&-#.+; 0#?&<& 3#F.&<& (3&-.%. V10"+3(;"1 L"( F#/#D(, '+:+"1 /3(<(C, /(?#;"1 .#/ "31"$1; + ". /. H ,&.@1 0&31-.&-#.+; (D#0".+,+ D#0"& -.&0%" «0*(D#;.=1 +F?1.1.+%» + '&0=*#C" '3&<3#??( - 2C3+ 1M1 3#F, -.&0%" + '&0=*#C" + ". /. 9/.#,&, 10*+ &0"#*&0$ A&"% )= '%"$ ?+.(", *(D:1 '3+/(?#;"1 '#3( .1)&*$:+A 0&/132#"1*$.=A "10"&- + '3&-13$"1 '3&<3#??( .# .+A. K0*+ &).#3(2+"0% &:+),# – 0,&.@1."3+3(;"10$ + +0'3#-$"1 11, # .1 '3&0"& /&)1;"10$ -13.&<& &"-1"# .# /#..&? ,&.,31".&? '3+?131. 5&?.+"1, D"& - '3&<3#??1 D#0"& 10"$ '&-"&3%CM+10% ?10"#, '&L"&?( &/.# + "# 21 &:+),# ?&<*# )="$ /&'(M1.# ?.&<&,3#".&.

W&-&*$.& D#0"& &).#3(2+-#1"0% >3#<?1." .#'+0#..&; '3&<3#??=, ,&"&3=; ?&21" )="$ (*(D:1.. 53+1?*1?&0"$ 0(M10"-(CM1; 31#*+F#@++ ?&21" F#-+01"$ &" "3#,"&-,+ (0*&-+% F#/#D+, .1"3+-+#*$.=A 0-&;0"- +0'&*$F&-#..=A #*<&3+"?&-, /#21 &" .1,&"&3&; /&*+ -1F1.+%, '&0,&*$,( +.&</# (D#0".+,+ /&'(0,#C" 0"&*$

.1&)=D.=1 + 31/,& '3&%-*%CM+10% &:+),+, D"& F#<&"&-*1..=1 "10"= L"+ &:+),+

.1 -=%-*%C". H= ?&21"1 (*(D:+"$ L"&" 0&?.+"1*$.=; >3#<?1." + '&0*#"$ '3&<3#??( .# '3&-13,(, &/.#,& '&/&).=1 /1;0"-+% D#0"& .#&)&3&" '3+-&/%" , (-1*+D1.+C ,&*+D10"-# &:+)&, - '3&<3#??1. 5&L"&?( '131/ -.101.+1? +0'3#-*1.+;, - .1&)A&/+?&0"+ ,&"&3=A -= .1 (-131.=, 0/1*#;"1 31F13-.(C ,&'+C -01<& 31:1.+%. 9).#3(2+- -'&0*1/0"-++ /1;0"-+"1*$.& 013$1F.(C &:+),(, -=, -13&%".&, F#A&"+"1 , L"&; ,&'++ -13.("$0%.

3. 6"&)#%#% *"#,('C#%%'? =.#)- "#$#%&8 9 9'%9"#5%'?

/+,+0#

V1'13$ .#0"#*& -31?% '3&/1?&.0"3+3&-#"$ &'+0#..(C 0A1?( .# '3+?131 31:1.+% ,&.,31".&; F#/#D+. 53+-1/1? (0*&-+1 F#/#D+.

D+,+0+ «E#*'1('<+3<&? ,#5#")&%&"'2+%%-? 9'%#0%-? +25')+5».

(Non Absorbing Deterministic Finite Automaton (DFA)).

8-"&3 F#/#D+: 8./31; !"#.,1-+D.

J0"&D.+,: Q1".+1 0)&3= ,&?#./-(D#0".+@ D1?'+&.#"# ?+3# ACM '& '3&<3#??+3&-#.+C. 51"3&F#-&/0,, 2003.

11

I#0'&*&21.+1: F#/#D# 7 201 - #3A+-1 &*+?'+#/.=A F#/#D !#3#"&-0,&<& <&0(/#30"-1..&<& (.+-130+"1"# http://acm.sgu.ru/

G0*&-+1 F#/#D+ 0>&3?(*+3&-#.& .# #.<*+;0,&? %F=,1. 5131-&/ .# 3(00,+; -='&*.1. ?.&C. 8))31-+#"(3# «DFA» '131-&/+"0% ,#, «W68» – /1"13?+.+3&-#..=; ,&.1D.=; #-"&?#".

<>%*")($")6 ) #%$/'4*")6:

•&<3#.+D1.+1 '& -31?1.+: 20;

•&<3#.+D1.+1 '& '#?%"+: 64 4);

•-A&/.=1 /#..=1: 0"#./#3".=; --&/;

•-=A&/.=1 /#..=1: 0"#./#3".=; -=-&/.

H "1&3++ ,&?'+*%"&3&- + %F=,&- :+3&,& +0'&*$F(C"0% ,&.1D.=1 #-"&?#"=. W1"13?+.+3&-#..=; ,&.1D.=; #-"&?#" (W68) – L"& ('&3%/&D1..=; .#)&3 <!, U, s, T, ">, </1 ! – ,&.1D.&1 ?.&210"-&, .#F=-#1?&1 -A&/.=? #*>#-+"&?, U – ,&.1D.=; .#)&3 0&0"&%.+;, s +F U – .#D#*$.&1 0&0"&%.+1, T – ?.&210"-& "13?+.#*$.=A 0&0"&%.+; +F U, +, .#,&.1@, ": U # ! $ U – >(.,@+% '131A&/&-.

HA&/&? #-"&?#"# %-*%1"0% 0"3&,# % .#/ #*>#-+"&? !. 513-&.#D#*$.&

#-"&?#" .#A&/+"0% - 0&0"&%.++ s. P# ,#2/&? :#<1 &. D+"#1" '13-=; 0+?-&* -A&/.&; 0"3&,+ + +F?1.%1" 0-&1 0&0"&%.+1 .# "(u, c), </1 u – "1,(M11 0&0"&%.+1. 5&0*1 L"&<& '13-=; 0+?-&* -A&/.&; 0"3&,+ (/#*%1"0%, + :#< '&-"&3%1"0%. K0*+ , ?&?1."( +0D13'#.+% -A&/.&; 0"3&,+ #-"&?#" )(/1" .#A&/+"$0% - "13?+.#*$.&? 0&0"&%.++, "& <&-&3%", D"& &. /&'(0,#1" +0A&/.(C 0"3&,( %, - '3&"+-.&? 0*(D#1 – &"-13<#1" 11.

J.&</# /*% ('3&M1.+% #-"&?#"# --&/+"0% '&.%"+1 .1'&<*&M#CM+A 31)13. E"& F.#D+", D"& - /&'&*.1.+1 , >(.,@++ '131A&/&- " --&/+"0% "#,21 >(.,@+% & : U # ! $ {0, 1}. V&</# '3+ 0&-13:1.++ '131A&/# +F 0&0"&%.+% u '& 0+?-&*( c, '13-=; 0+?-&* +F -A&/.&; 0"3&,+ (/#*%1"0%, "&*$,& 10*+ &(u, c) = 0. K0*+ 21 &(u, c) = 1, "& -A&/.#% 0"3&,# &0"#1"0% )1F +F?1.1.+;, + 0*1/(CM+; '131A&/ '3&+F-&/+"0% +F .&-&<& 0&0"&%.+%, .& '& "&?( 21 0+?-&*( c. H '13-&? 0*(D#1 <&-&3%", D"& '3&+F&:1* '131A&/ '& '&<*&M#CM1?( 31)3(, -& -"&3&? – '&

.1'&<*&M#CM1?(.

5& &'31/1*1.+C "#,&; #-"&?#" /&'(0,#1" 0"3&,( %, 10*+ '&0*1 .1,&"&3&<& D+0*# :#<&- &. '&'#/#1" - "13?+.#*$.&1 0&0"&%.+1, # 0"3&,# &,#F=-#1"0% '(0"&;.

O#/#D#: '& /#..&?( W68 0 .1'&<*&M#CM+?+ 31)3#?+ .#;"+ ,&*+D10"-& 0"3&, /#..&; /*+.= N, ,&"&3=1 &. /&'(0,#1".

F'")+5 2.',%-. ,+%%-.

513-#% 0"3&,# -A&/.&<& >#;*# 0&/132+" ! – '&/?.&210"-& #.<*+;0,&<& #*>#-+"# (.10,&*$,& ?#*1.$,+A *#"+.0,+A )(,-).

H"&3#% 0"3&,# 0&/132+" K = |U| – ,&*+D10"-& 0&0"&%.+; #-"&?#"# (1 ' K ' 1000). !&0"&%.+% .(?13(C"0% &" 1 /& K.

V31"$% 0"3&,# 0&/132+" S (1 ' S ' K) – .#D#*$.&1 0&0"&%.+1 + L=|T|

– ,&*+D10"-& "13?+.#*$.=A 0&0"&%.+;, # F#"1? L 3#F*+D.=A @1*=A D+01* 0& F.#D1.+%?+ &" 1 /& K ,#2/&1 – .&?13# "13?+.#*$.=A 0&0"&%.+;.

!*1/(CM+1 K 0"3&, 0&/132#" '& |!| @1*=A D+01* ,#2/#% + &'31/1*%C" >(.,@+C ".

12

O#"1? 3#0'&*#<#C"0% K 0"3&, &'31/1*%C" >(.,@+C & "1? 21 0'&0&)&?. 5&0*1/.%% 0"3&,# -A&/.&<& >#;*# 0&/132+" N (1 ' N ' 60).

F'")+5 2-.',%-. ,+%%-.

H=-1/+"1 1/+.0"-1..&1 D+0*& – ,&*+D10"-& 0"3&, /*+.= N .#/ #*>#-+"&? !, /&'(0,#1?=A /#..=? W68.

53+-1/1..#% .+21 "#)*+@# 0&/132+" &'+0#.+1 '3+?13#.

()*+,) -./012. 03112.			()*+,) -2./012. 03112.
ab			2
2
1	1	2
2	1
1	2
0	1
0	0
3

HL"&? '3+?131 #-"&?#" /&'(0,#1" /-1 0"3&,+: “aaa” + “abb”.

3.1.>5#% ;=('2&8

G0*&-+1 L"&; F#/#D+ /&0"#"&D.& '3&0"& /*% '3&D"1.+%. H&-'13-=A, &.&

.#'+0#.& .# 3(00,&? %F=,1. H&--"&3=A, &.& '3#,"+D10,+ '&*.&0"$C >&3?#*+F&-#.&, + *+"13#"(3.&1 --1/1.+1 0&0"&+" +F &/.&; >3#F=: «H "1&3++ ,&?'+*%"&3&- + %F=,&- :+3&,& +0'&*$F(C"0% ,&.1D.=1 #-"&?#"=». H01. X&*$:1 -#0 .+D1<& .1 &"-*1,#1". 4&21"1 0,#F#"$ 0'#0+)& #-"&3( F#/#D+, +F)#-+-:1?( -#0 &" .1.(2.=A /1"#*1;, ,&"&3=1, -'3&D1?, ?&<*+ )= .10,&*$,& &2+-+"$ L"& 0(A&1 + >&3?#*$.&1 (0*&-+1 F#/#D+, +F*&21..&1 '&0*1/&-#"1*$.&, 0-%F.& + )1F '&/-&A&-. 5&.%"+1 W68, ,&"&3&1 ?&21" )="$ .1+F-10".& D+"#"1*C, &'31/1*1.& - "1,0"1.

9/.#,& H=, /&3&<&; D+"#"1*$, -13&%".&, '3&D+"#*+ L"& (0*&-+1 «.#+0,&0&,»,

.1-.+?#"1*$.& + .1)312.&, &'(0"+- .1,&"&3=1 /1"#*+. !,&311 -01<&, -= '&.%*+, D"& 10"$ ,#,#%-"& ?&/+>+,#@+% ,&.1D.&<& #-"&?#"#, + 0*1/(1" '&0D+"#"$ ,&*+D10"-& 0"3&,, ,&"&3&1 &.# /&'(0,#1". K0*+ -= .1 F.#1"1, D"& "#,&1 «,&.1D.=;

#-"&?#"» + «/&'(0,#1"», "& "&</# ( -#0, -13&%".&, 0*&2+*&0$ 1M1 )&*11 0?(".&1 '31/0"#-*1.+1 &) (0*&-++ /#..&; F#/#D+.

H= ?&21"1 -&F3#F+"$, D"& '3&D+"#*+ (0*&-+1 .1-.+?#"1*$.& '&"&?(, D"& D+"#1"1 L"&" "1,0", # -&-01 .1 31:#1"1 F#/#D(. 9D1.$ F3%. H= /(?#1"1, .# 0&31-.&-#.++, 31:#% 31#*$.=1 F#/#D+, -= 0?&21"1 D+"#"$ (0*&-+1 +.#D1, .1 "#,, ,#, 01;D#0?

V1'13$, '&2#*(;0"#, -13.+"10$ , (0*&-+C + '3&D+"#;"1 1<& 1M1 3#F, &D1.$ -.+?#"1*$.&.

3.2. 6'=5"'#% )+5#)+5&0#=9'? )',#(&

E"&" L"#' %-*%1"0% 10"10"-1..=? '3&/&*21.+1? '31/=/(M1<&. H= (21 '3&D+"#*+ (0*&-+1? !,&311 -01<&, -= '&.%*+ - *(D:1? 0*(D#1 '&*&-+.(.

13

5131D+"#;"1 (0*&-+1 1M1 3#F: ?1/*1..&, '& &/.&?( '31/*&21.+C, '3+

.1&)A&/+?&0"+ +0'&*$F(% 3(D,( + )(?#<(. P1 *1.+"10$, 3#F)13+"10$, D"& "31)(1"0% - F#/#D1.

6&."3&*$.=; -&'3&0: '3+-1/+"1 '3+?13 -A&/.=A /#..=A, &"-1" /*% ,&"&3&<& – 1/+.+@#. P1 .# (3&-.1 +/1+, # - D+0*#A. K0*+ &. 0(M10"-(1", F#'+:+"1 1<& -?10"1 0 &"-1"&?. E"&" '3+?13 1M1 '3+<&/+"0% -#? '3+ "10"+3&-#.++. H0"31"+- 3#00?#"3+-#1?(C F#/#D( .# .#0"&%M+A 0&31-.&-#.+%A, .1?.&<+1 (D#0".+,+ /1;0"-+"1*$.& )(/(" '3+/(?=-#"$ ,#,&;-*+)& .#)&3 -A&/.=A /#..=A 03#F( '&0*1 '3&D"1.+% (0*&-+%, D"&)= .1 .#'3%<#"$0%. 5&L"&?( 0&)="+% D#0"& 3#F-+-#C"0% '& 0*1/(CM1?( 0@1.#3+C. 9/+. (D#0".+, 0'3#:+-#1" /3(<&<&: «V= D+"#* F#/#D( F?” W3(<&; &"-1D#1": «W#, "#? ,#,+1-"& ,&.1D.=1 #-"&?#"=, ,#,+1-"& /&'(0,#1?=1 0"3&,+. B"&-"& .1'&.%".&1 +, .#-13.&1, .(/.&1. Q(D:1 '&D+"#1? /3(<+1 F#/#D+» – + &.+ &",*#/=-#C" L"( F#/#D( - 0"&3&.(, /#21 '3+)*+F+"1*$.& .1 '&.%- 11 (0*&-+%. 53+ L"&? &/+. +F (D#0".+,&- '&"3#"+* -31?% .# D"1.+1 L"&; F#/#D+, + &)#

– .# &)0(2/1.+1.

J"#,, 0"3&+? ?#"1?#"+D10,(C ?&/1*$. !.#D#*# .1&)A&/+?& '&.%"$, D"& "#,&1 «/1"13?+.+3&-#..=; ,&.1D.=; #-"&?#"».

3.2.1. G'%#0%-# +25')+5-

W*% 31:1.+% 3#00?#"3+-#1?&; F#/#D+ .1 "31)(1"0% .+,#,+A '31/-#3+"1*$.=A F.#.+; & ,&.1D.=A #-"&?#"#A. 9/.#,& ( )&*$:+.0"-# (D#0".+,&- 0"(/1.D10,+A &*+?'+#/ '& +.>&3?#"+,1 .#-13.%,# 10"$ +."(+"+-.&1 '31/0"#-*1.+1 & ,&.1D.=A #-"&?#"#A. 531/0"#-*1.+1 L"&, ,#, '3#-+*&, &)3=-&D.&1, 0+."1"+D10,&1 +, , "&?( 21, +0,#21..&1, D"& F#D#0"(C &,#F=-#1"0% A(21, D1? &"0("0"-+1 ,#,+A )= "& .+ )=*& F.#.+; - 3#00?#"3+-#1?&; &)*#0"+.

53&)*1?= '3&+0"1,#C" +F "&<&, D"& /1"13?+.+3&-#..=; ,&.1D.=; #-"&?#"

– L"& ?#"1?#"+D10,+; &)T1,", 3#00?#"3+-#1?=; -?10"1 0 31<(*%3.=?+ %F=,#?+ + 0&&"-1"0"-(CM+?+ +? <3#??#"+,+. !#?& 21 0*&-&0&D1"#.+1 «,&.1D.=; #-"&?#"» '3+?1.%1"0% F.#D+"1*$.& )&*11 :+3&,&, --&/% (D#0".+,# 0&31-.&-#.+; - F#)*(2/1.+1, D"& &. -0"31"+* F.#,&?&1 '&.%"+1. V#,21 (D"+"1, D"& ( #-"&3&- F#/#D+ ?&21" )="$ /3(<&1 '31/0"#-*1.+1 & "&?, D"& "#,&1 W68, /#21 .1-13.&1 + &"*+D#CM110% &" &'31/1*1.+% - ,*#00+D10,&; ,.+<1 [18]. !1;D#0 -= /&*2.= '&.+?#"$, D"& "#,&1 W68, +.#D1 -#? 0*1/(1" -13.("$0% , D"1.+C (0*&-+%.

W*% 0&F/#.+% %0.&<&, A&3&:& 0>&3?+3&-#..&<& '31/0"#-*1.+% & ,&.1D.=A

#-"&?#"#A 0*1/(1" '&31,&?1./&-#"$ (D1).+, /*% HGO&- [19]. H .1? -.%".& '3&-1/1.& 3#F*+D+1 ?12/( ,&.1D.=? #-"&?#"&? ,#, "1A.+D10,+? L*1?1."&? + ?#"1?#"+D10,+? &)T1,"&?, 3#0'&F.#CM+? +*+ '31&)3#F(CM+? .1,&"&3=; %F=,. Y&"% L"& 3#F*+D+1 &".&0+"0% 0,&311 , "13?+.&*&<++ + '31/?1".&; &)*#0"+, D1? , ?#"1?#"+D10,&; 0(M.&0"+ #-"&?#"&-, &.& &)=D.& '&3&2/#1" ?.&<& '("#.+@= +

.1'&.+?#.+%.

6*#00+D10,#% ,.+<# [18] '&0-%M1.# "1&3++ #-"&?#"&- + 0&&"-1"0"-(CM+A >&3?#*$.=A %F=,&- + <3#??#"+,. H D#0".&0"+, - .1; &'+0#.& '&.%"+1

2$#$%,)")%'4*""03 ='"$("03 *4#',*#, & ,&"&3&? + +/1" 31D$ - F#/#D1. !*1/(1" '&.+?#"$, D"& F/10$ '&.%"+% «-A&/.&1 -&F/1;0"-+1» + «-A&/.&; 0+?-&*» L,-+-#*1.".= – -A&/.&1 -&F/1;0"-+1 )131"0% +F ?.&210"-# -&F?&2.=A -A&/.=A -&F/1;0"-+;, -A&/.&; 0+?-&* – +F -A&/.&<& #*>#-+"#.

14

6&.1D.=; #-"&?#" ?&2.& 3#00?#"3+-#"$ ,#, &3+1."+3&-#..=; <3#>. 8*<&3+"?=, '3+?1.%1?=1 , F#/#D#? .# <3#>#A, D#0"& '&*1F.= + /*% ,&.1D.=A

#-"&?#"&-. U&-&3% &) &*+?'+#/.=A F#/#D#A, - (0*&-++ .1 &)%F#"1*$.& /&*21.

.1'&031/0"-1..& >+<(3+3&-#"$ ,&.1D.=; #-"&?#" – &. ?&21" *1<,& '3&0*12+-#"$0%, # ?&21" /#21 "31)&-#"$ 0'1@+#*$.&<& '&0"3&1.+%.

3.2.2. !9'%0+5#(H%'# *'%&)+% ;=('2&8

J?11"0% W68 0 .1'&<*&M#CM+?+ 31)3#?+ – 31)3#?+, '3+ 0&-13:1.++ '131A&/# '& ,&"&3=? .1 0D+"=-#1"0% 0+?-&*. H L"&? 0*(D#1 0*1/(CM+; '131A&/ '3&+0A&/+" +F .&-&<& 0&0"&%.+%, .& '& "&?( 21 0+?-&*(. E"& )(/1" '3&/&*2#"$0% /& "1A '&3, '&,# .1 '3&+F&;/1" '131A&/ '& '&<*&M#CM1?( 31)3(, *+)& '&,# '3&@100 .1 F#@+,*+"0%. H#2.&, #.#*+F+3(% (0*&-+1 F#/#D+, .1 ('(0"+"$ +F -+/( -&F?&2.&0"$ 0(M10"-&-#.+% @+,*&- +F .1'&<*&M#CM+A 31)13.

W68 0 .1'&<*&M#CM+?+ 31)3#?+ 0-&/+"0% , W68 )1F .+A. JF ,#2/&<& 0&0"&%.+% '& ,#2/&?( 0+?-&*( '3&+0A&/+" '131A&/ - .1,&"&3&1 /3(<&1 0&0"&%.+1, -&F?&2.&, '&0*1 '3&A&2/1.+% #-"&?#"&? '& @1'&D,1 .1'&<*&M#CM+A 31)13. J0,*CD1.+1? %-*%1"0% '&'#/#.+1? - @+,*. B"&)= (D10"$ L"( -&F?&2.&0"$, /&)#-+? 1M1 &/.& 0&0"&%.+1 «P1/&'(0,», .1 %-*%CM110% "13?+.#*$.=?. 5&0,&*$,( '&0*1 '&'#/#.+% - @+,* +F .1'&<*&M#CM+A 31)13 &D131/.&; 0+?-&* -A&/.&; 0"3&,+ .+,&</# .1 )(/1" (/#*1., "& #-"&?#" '& &'31/1*1.+C .1 /&'(0,#1" +0A&/.(C 0"3&,(. !&&"-1"0"-1..&, -?10"& '131A&/# '& .1'&<*&M#CM1?( 31)3(, '3+-&/%M1?( - @+,*, #-"&?#" ?&21" 0&-13:+"$ '131A&/ '& '&<*&M#CM1?( 31)3( - 0&0"&%.+1 «P1/&'(0,», + +0A&/.#% 0"3&,# .1 )(/1" /&'(M1.#. H01 31)3# +F 0&0"&%.+% «P1/&'(0,» -1/(" - .1<& 21.

B"&)= .#;"+ ,&*+D10"-& 0"3&, /#..&; /*+.=, /&'(0,#1?=A /#..=? W68, /&0"#"&D.& '131)3#"$ -01 0"3&,+ (,#F#..&; /*+.= + '&0*1/&-#"1*$.& '&/#"$ +A .# -A&/ #-"&?#"(.

9)3#"+?0% , '3+?13( -A&/.=A /#..=A. W68, &'+0#..=; - .1?, +?11" /-# 0&0"&%.+%. 513-&1 0&0"&%.+1 – .#D#*$.&1, -"&3&1 – "13?+.#*$.&1. P1&)A&/+?& '&0D+"#"$ ,&*+D10"-& /&'(0,#1?=A 0"3&, +F "31A 0+?-&*&-.

P# 3+0.1 +F&)3#21. /#..=; W68 0 .1'&<*&M#CM+? 31)3&?, -=/1*1..=? '(.,"+3&?. P# L"&? 3+0(.,1 .#D#*$.&1 0&0"&%.+1 '&/D13,.("&, # "13?+.#*$.&1 -=/1*1.& /-&;.=? ,&."(3&?.

a

b																			b
	1											2

a

I+0.1. W68 0 .1'&<*&M#CM+?+ 31)3#?+

531&)3#F(1? #-"&?#" /*% "&<&, D"&)= +F)#-+"$0% &" .1'&<*&M#CM+A 31)13. P# 3+0. 2 +F&)3#21. W68, L,-+-#*1.".=; +0A&/.&?(. !&0"&%.+1 «P1/&'(0,» '&?1D1.& )(,-&; «P», # F#'%"#% '&F-&*%1" .1 +F&)3#2#"$ ,3#".=1 31)3#.

15

a

a,b

b

b

_

1

2

a

I+0.2. W68 '&0*1 (/#*1.+% .1'&<*&M#CM+A 31)13

JF 3#00?&"31.+% 3+0(.,&- 0*1/(1", D"& - '13-&? 0&0"&%.++ .# -A&/ .1 /&*21. '&/#-#"$0% 0+?-&* “b”, +.#D1 L"& '3+-1/1" , F#@+,*+-#.+C. !&&"-1"0"-1..&, '13-=; 0+?-&* /&*21. )="$ “a”. GD+"=-#%, D"& "13?+.#*$.&1 0&0"&%.+1 &/.& – -"&3&1, ?&2.& ("-132/#"$, D"& #-"&?#" /&'(0,#1" /-1 0"3&,+: “aaa” + “abb”. W1;0"-+"1*$.&, &"-1" – /-#.

3.3. 6'=5"'#% ':<#? =.#)- "#$#%&8

I#00?#"3+-#1?#% F#/#D# – /&0"#"&D.& 0"#./#3".#, + 11 31:1.+1 A&3&:& '&//#1"0% 0&)+3#.+C +F «,+3'+D+,&-», &'+0#..&?( - 3#F/. 2.3. 53&/1?&.0"3+3(1? A&/ ?=0*1; '3+ '&+0,1 31:1.+%.

H '3&@1001 &0&F.#.+% F#/#D+ )=*& -=%-*1.&, D"& W68 0 .1'&<*&M#CM+?+ 31)3#?+ ?&2.& '31&)3#F&-#"$ - W68 )1F "#,+A 31)13. 5&,# .1%0.&, .#0,&*$,& L>>1,"+-.& ?&2.& -='&*.+"$ L"& '31&)3#F&-#.+1. V1'13$ 10"$ W68 "& *+ 0

.1'&<*&M#CM+?+ 31)3#?+ (10*+ .1 (/#0"0% '3+/(?#"$ L>>1,"+-.=; #*<&3+"?), "& *+ )1F .+A. 90"#1"0%, 0&)0"-1..&, .#;"+ &"-1" .# F#/#D( – ,&*+D10"-& /&'(0,#1?=A 0"3&,. S0.&, D"& L"& .1*$F% /1*#"$ '131)&3&? + '3&-13,&; -01A 0"3&, F#/#..&; /*+.=, "#, ,#, +A ?&21" &,#F#"$0% .1/&'(0"+?& ?.&<&.

6#, -&&)M1 ?&2.& '&0D+"#"$ ,&*+D10"-& 0"3&,, (/&-*1"-&3%CM+A ,#,+?-"& 0-&;0"-#?? 513-=; 0(M10"-(CM+; '&/A&/ – +0'&*$F&-#.+1 A+"3=A ,&?)+.#"&3.=A 0&&)3#21.+; + '&/0D1" L"+A >&3?(* .# ,&?'$C"131. H"&3&; '&/A&/ (+.&</# &)# '&/A&/# 0&D1"#C"0%): 10*+ 0+0"1?# 0*+:,&? 0*&2.#,

.1&)A&/+?& .#;"+ .1,(C 31,(331.".(C >&3?(*(, -=-10"+ ,&*+D10"-& 0"3&, /#..&; /*+.= 0 ,#,+?+-"& 0-&;0"-#?+ D131F ,&*+D10"-& 0"3&, /3(<&; /*+.= 0 /3(<+?+ 0-&;0"-#?+. O#"1? '3+?1.+"$ /+.#?+D10,&1 '3&<3#??+3&-#.+1 /*% '&0*1/&-#"1*$.&<& -=D+0*1.+% -01A L"+A F.#D1.+;. V#,+? &)3#F&?, &'=" '&/0,#F=-#1", D"& /*% '&/0D1"# ,&*+D10"-# 0"3&,, /&'(0,#1?=A /#..=? W68, 0*1/(1" +0'&*$F&-#"$ /+.#?+D10,&1 '3&<3#??+3&-#.+1. W*% '&/<&"&-*1..&<& (D#0".+,# +/1% '&/0D1"# ,&*+D10"-# 0"3&,, &)*#/#CM+A .1,&"&3=? 0-&;0"-&?, 0 '&?&M$C /+.#?+D10,&<& '3&<3#??+3&-#.+% 0#?# '& 01)1 %-*%1"0% «,+3'+D+,&?».

53#,"+D10,&1 0&&)3#21.+1: #*>#-+" ?&21" 0&0"&%"$ +F 26 0+?-&*&- (|A| = 26). !"3&,# ?&21" )="$ +F 60 0+?-&*&-. 4#*& L"&<&, &)M11 '31/0"#-*1.+1 & ,&.1D.=A #-"&?#"#A 0-+/1"1*$0"-(1" & "&?, D"& -01 0"3&,+ ?&<(" /&'(0,#"$0%. V&</# &"-1" )(/1" 2660, D"& -10$?# ?.&<&. P#0,&*$,& ?.&<&? 53+ .#*+D++ ,&?'$C"13# +*+ A&3&:1<& ,#*$,(*%"&3#, .# L"&" -&'3&0 &"-1"+"$ *1<,&. 9'31/1*+? log10(2660) = 60log10(26) = 60(ln(26) / ln(10)) ! 60 * 1.415 !

84.9. !*1/&-#"1*$.&, - &"-1"1 ?&21" )="$ 85 @+>3 - /10%"+D.&? '31/0"#-*1.++. V#,&1 ,&*+D10"-& 0"3&, .1 '&?10"+"0% - 0"#./#3".=; "+' (-+/# Integer). 5&L"&?( '3+ .#'+0#.++ 31:1.+% .# %F=,1 Pascal '3+/1"0% -3(D.(C 31#*+F&-#"$ #3+>?1"+,( '&-=:1..&; "&D.&0"+. !&&"-1"0"-(CM+1 >(.,@++ "#,21 &".&0%"0% , 3#F3%/( «,+3'+D+,&-», -A&/%M+A - &)%F#"1*$.(C '&/<&"&-,(.

16

J."(+"+-.&1 '31/0"#-*1.+1 & "&?, D"& ,&*+D10"-& 0"3&,, /&'(0,#1?=A /#..=? W68, ?&2.& &'31/1*+"$ 0 '&?&M$C /+.#?+D10,&<& '3&<3#??+3&-#.+%,

.1&)A&/+?& 3#F-+"$. !3#F( F#?1"+?: .1'&A&21, D"&)= L"( 0+0"1?( ?&2.& )=*& 31:+"$ D+0"& ,&?)+.#"&3.&; >&3?(*&;. 63&?1 L"&<& F#?1D#.+%, '3&+0"1,#CM1<& +F &'="#, , 0&2#*1.+C, .+D1<& )&*11 ,&.,31".&<& 03#F( 0,#F#"$ .1*$F%. Y+"3=1 0&D1"#.+% >&3?(*, &0.&-#..=1 .# >(.,@++ '131A&/&-, "#,21, 0,&311 -01<&, &,#2("0% 0&&".&:1.+%?+ /+.#?+D10,&<& '3&<3#??+3&-#.+%. 5&-13+? - L"& &M(M1.+1, '3&+0"1,#CM11 +F &'="#, + -=/1*+? '&/F#/#D+ + 31,(331.".=1 0&&".&:1.+%.

6*CD1-#% +/1%: '31+?(M10"-& ?&/1*+ ,&.1D.&<& #-"&?#"# - "&?, D"& -0% +0"&3+% -=3#2#1"0% &/.+? D+0*&? – .&?13&? 0&0"&%.+%, + L"+A 0&0"&%.+; ,&.1D.&1 ,&*+D10"-&. ! "&D,+ F31.+% -&'3&0#, /&'(0,#1"0% *+ ,&.,31".#% 0"3&,#, +?11" F.#D1.+1 .1 "&*$,& 0&0"&%.+1 #-"&?#"#, .& + ,&*+D10"-& '&<*&M1..=A 0+?-&*&- 0"3&,+. 6&*+D10"-& '&<*&M1..=A 0+?-&*&- 0&-'#/#1" 0 ,&*+D10"-&? '3&:1/:+A :#<&-, "#,"&- 3#)&"= #-"&?#"# – 3#00?#"3+-#1"0% (21 W68 )1F

.1'&<*&M#CM+A 31)13. I#00?&"3+? '#3( (state, k) – "1,(M11 0&0"&%.+1 – state, + '3&:*& k :#<&-.

I#00?&"3+? 0"3&,+ /*+.= k, &)*#/#CM+1 0*1/(CM+? 0-&;0"-&?: '&*(D+-

.# -A&/ "#,(C 0"3&,(, W68 '3+A&/+" +F .#D#*$.&<& 0&0"&%.+% - 0&0"&%.+1 state. 9)&F.#D+? D+0*& L"+A 0"3&, D131F f(state, k). H=D+0*1.+1 L"&<& F.#D1.+% /*% 3#F*+D.=A '#3 (state, k) + %-*%1"0% '&/F#/#D1;. W*% (0'1:.&<& '3+?1.1.+% /+.#?+D10,&<& '3&<3#??+3&-#.+% .1&)A&/+?= 31,(331.".=1 0&&".&:1.+%, ,&"&3=1 *1<,& '&*(D#C"0%, (D+"=-#% ('&?%.("=1 0-&;0"-# ,&.1D.&<& #-"&?#"#. 53+-1/1? L"+ 0&&".&:1.+%:

#1, state = initial f (state,0) =

!0, state initial

f (state,k) =	! f (st,k #1)	,
	st U ,c A
	(st,c)=state

</1 initial – .#D#*$.&1 0&0"&%.+1 W68. !>&3?(*+3(1? 0A1?( 31:1.+%, 0&0"&%M1<& +F /-(A L"#'&-.

1.531-3#M#1? W68 0 .1'&<*&M#CM+?+ 31)3#?+ - W68 )1F "#,&-=A. P#*+D+1 31:1.+% 0 '&?&M$C /+.#?+D10,&<& '3&<3#??+3&-#.+% /*% W68 )1F

.1'&<*&M#CM+A 31)13 (,31'*%1" (-131..&0"$ - "&?, D"& L>>1,"+-.&1 (0"3#.1.+1 .1'&<*&M#CM+A 31)13 "#,21 -&F?&2.&.

2.53+?1.%1? /+.#?+D10,&1 '3&<3#??+3&-#.+1, +0'&*$F(% -=:1'3+-1/1..&1 31,(331.".&1 0&&".&:1.+1. N1*10&&)3#F.&, A&"% + .1 &)%F#"1*$.&, +0'&*$F&-#"$ /+.#?+D10,&1 '3&<3#??+3&-#.+1 «0.+F( --13A». W*%

.#A&2/1.+% &"-1"# .1&)A&/+?& )(/1" '3&0(??+3&-#"$ ! f (t,n) f(terminal_state, n) '& -01? "13?+.#*$.=? 0&0"&%.+%? t.

t T

H F#,*CD1.+1 3#F/1*# &"?1"+?, D"& '3+?1.1.+1 /+.#?+D10,&<& '3&<3#??+3&-#.+% .# ,&.1D.&? #-"&?#"1, ,#, + -&&)M1 .# <3#>1, %-*%1"0% &D1.$ L>>1,"+-.=?. 5131,3=-#CM+10% '&/F#/#D+ #-"&?#"+D10,+ -=/1*%C"0%:

.1&)A&/+?& *+:$ &"0*12+-#"$ @1*1-(C >(.,@+C -& -01A 0&0"&%.+%A #-"&?#"#. H ,#D10"-1 '3+?13# ?&2.& '3+-10"+ F#/#D(, '3+ 31:1.++ ,&"&3&; +0'&*$F(1"0%

17

"1A.+,#, '&*.&0"$C #.#*&<+D.#% -"&3&; D#0"+ 31:1.+% .#0"&%M1; F#/#D+: F#/#D# «Currency Exchange» («9)?1. -#*C"=»). 8-"&3: P+,&*#; W(3&-. J0"&D.+,: B1"-13"$>+.#* NEERC-2001, 01-13.=; '&/31<+&.. O#/#D# 3#F?1M1.# .# 0#;"1 http://acm.timus.ru/ '&/ .&?13&? 1162. Z#,"+D10,+ ?#"1?#"+D10,#% ?&/1*$ L"&; F#/#D+ %-*%1"0% ,&.1D.=? #-"&?#"&?, </1 0&0"&%.+%?+ %-*%C"0% -#*C"=, # '131A&/#?+ ?12/( .+?+ – &)?1..=1 '(.,"=.

!*1/(1" (,#F#"$ 1M1 &/.( +F-10".(C F#/#D(: «Censored!» («N1.F(3#!»). 8-"&3: P+,&*#; W(3&-. J0"&D.+,: B1"-13"$>+.#* NEERC-2001, 01-13.=; '&/31<+&.. O#/#D# 3#F?1M1.# .# 0#;"1 http://acm.timus.ru/ '&/ .&?13&? 1158. I#0'3&0"3#.1..=; 0'&0&) 11 31:1.+% 0&0"&+" +F /-(A L"#'&-: '&0"3&1.+1 ,&.1D.&<& #-"&?#"#, 3#0'&F.#CM1<& .#)&3 0"3&, (#*<&3+"? '&0"3&1.+% .#F=-#C" #*<&3+"?&? 8A&-6&3#0+,#), + +0'&*$F&-#.+1 /+.#?+D10,&<& '3&<3#??+3&-#.+% .# '&*(D1..&? ,&.1D.&? #-"&?#"1. 5&A&2#% F#/#D# )1F /+.#?+D10,&<& '3&<3#??+3&-#.+% – F#/#D# «Obscene words filter» («Z+*$"3 <3()=A 0*&-»). 8-"&3: 5#-1* 8".#:1-. J0"&D.+,: D1?'+&.#" G3UG 25.10.2003. O#/#D# 3#F?1M1.# .# 0#;"1 http://acm.timus.ru/ '&/ .&?13&? 1269.

4.&C )=*+ '3.#*+F+3&-#.= -01 F#/#D+ - #3A+-#A &*+?'+#/.=A F#/#D http://acm.sgu.ru/ + http://acm.timus.ru/ .# '13-&1 +C.% 2005 <&/#. 63&?1 F#/#D+,

3#00?#"3+-#1?&; - .#0"&%M1; 0"#"$1, + "31A "&*$,& D"& ('&?%.("=A F#/#D, - &0"#*$.=A F#/#D#A +0'&*$F&-#.+1 ,&.1D.=A #-"&?#"&- &<3#.+D+-#1"0% #*<&3+"?&? 6.("#-4&33+0#-53#""#.

3.4. 75-9'29+

I#00?&"3+? '13-=; L"#'. 6#, 1<& -='&*.+"$?

H 3#F/. 3.2 («5&0"3&1.+1 ?#"1?#"+D10,&; ?&/1*+») )=*# (0"#.&-*1.# "1&31"+D10,#% -&F?&2.&0"$ -='&*.1.+% /#..&<& L"#'#. 6#, &)0(2/#*&0$ -=:1, 31F(*$"#"&? '&0"3&1.+% ?#"1?#"+D10,&; ?&/1*+ &)=D.& %-*%1"0% .1,+; '3+?+"+-.=; + .1L>>1,"+-.=; #*<&3+"? 31:1.+% – >&3?#*$.& F#'+0#..&1 '&.+?#.+1 "&<&, ,#, +F -A&/.=A /#..=A '&*(D#C"0% -=A&/.=1. 5&'3&)(1? '3+?1.+"$ 1<& .# '3#,"+,1.

5&0*1/&-#"1*$.& '131)131? -01 '#3= (0&0"&%.+1, 0+?-&*). 531/'&*&2+?, D"& W68 .#A&/+"0% - 3#00?#"3+-#1?&? 0&0"&%.++, # -=)3#..=; 0+?-&* %-*%1"0% &D131/.=? .# -A&/.&; *1."1. !&-13:#1? '131A&/ '& /#..&?( 0+?-&*(. K0*+ '131A&/ '3&+F&:1* '& .1'&<*&M#CM1?( 31)3(, 0&-13:#1? 0*1/(CM+; '131A&/ '& "&?( 21 0+?-&*(. K0*+ '131A&/ 0.&-# '3&+F&:1* '& .1'&<*&M#CM1?( 31)3(, '&-"&3%1? "&" 21 ?#.1-3. H 31F(*$"#"1 *+)& 0+?-&* )(/1" '&<*&M1., *+)& #-"&?#" -&;/1" - @+,*. H '13-&? 0*(D#1 ?&2.& +F?1.+"$ '131A&/ +F +0A&/.&<& 0&0"&%.+%, +F ,&"&3&<& #-"&?#" '3&:1* '& @1'&D,1 .1'&<*&M#CM+A 31)13, 03#F( '&0"#-+- '131A&/ - ,&.1D.&1 0&0"&%.+1. H& -"&3&? – ?&2.& '&0"#-+"$ 31)3& - .1,&"&3&1 >+,"+-.&1 0&0"&%.+1 – «P1/&'(0,», ,&"&3&1 .1 %-*%1"0% "13?+.#*$.=?. 9.& F#?,.("& .# 01)% '3+ '131A&/1 '& -01? 0+?-&*#?. 5&'#/#.+1 - L"& 0&0"&%.+1 )(/1" 0&&"-1"0"-&-#"$ -A&/( - @+,* +F .1'&<*&M#CM+A 31)13 - +0A&/.&? #-"&?#"1.

P1'&031/0"-1..&1 «'3&<&-#3+-#.+1» 31:1.+% '3+-1*& , .1'*&A&?( 31F(*$"#"(. 9@1.+? L>>1,"+-.&0"$ 31:1.+%. 6#, &'31/1*+"$, D"& '3&+F&:*& '&'#/#.+1 - @+,*? K0*+ F# |U| :#<&- #-"&?#" .1 '131;/1" '& .1'&<*&M#CM1?( 31)3(, "& L"& )(/1" &F.#D#"$, D"& &. -&:1* - @+,* (|U| – D+0*& 0&0"&%.+;

#-"&?#"#). H13A.%% &@1.,# -31?1.+ 3#)&"=: |U|*|U|*|A| – '&3%/,# 26 * 106.

18

4.&<& L"& +*+ ?#*&? 5& ?13,#? 2003 <&/#, - ,&"&3&? )=*# '31/*&21.# F#/#D#, F# 01,(./( ?&2.& )=*& -='&*.+"$ 107 0&-01? '3&0"=A &'13#@+; .# %F=,1 -=0&,&<& (3&-.%, "#,&?, ,#, %F=,+ Pascal +*+ C++. !&&"-1"0"-1..&, "#,&; 0'&0&) (0"3#.1.+% .1'&<*&M#CM+A 31)13 /&*21. "31)&-#"$ .1 )&*11 01,(./=, D"& - '13-&? '3+)*+21.++ '31/0"#-*%1"0% /&'(0"+?=? – &/+. +F /-(A L"#'&- "31)(1" '&*&-+.( -31?1.+, -1/$ &<3#.+D1.+1 .# &/+. "10" 0&0"#-*%1" /-1 01,(./=, ,#, 0,#F#.& - (0*&-++.

53+-1/1? '01-/&,&/ /*% (0"3#.1.+% .1'&<*&M#CM+A 31)13. H '01-/&,&/1 ?.&210"-& -01A 0&0"&%.+; &)&F.#D1.& D131F State.

for	c	in	Alpha do		// (/		-4,+	4*+-/53+ 3563-*73
for		i in		State do	// (/		-4,+	4/47/81*8+ 3-7/+373
begin
cur		:=	i		//	9,:;<,,		4/47/81*,
z	:= n				//	=/5*>,47-/ 4/47/81*?

//(/:3 ),@)/-A,),./0 *B 4/47/81*8 k A/ 4*+-/5; j –

//A/C5/<3D<,,, * ,<, 40,531/ 1, />,1E +1/C/ A,),./0/- while ( [cur,c] = 1) and (z > 0) do

begin

cur := #[cur][c] // (,),?7*

z := z – 1 // F+,1EG*7E 4>,7>*: end

// H45* -4, ,<, />,),01/, ),@)/ – 1,A/C5/<3D<,, if ( [cur][c] = 1) then

#[i][c] := 0 // I13>*7 – J*:5 else

#[i][c] := #[cur][c] // K13>, A,),473-58,+ ),@)/ // K 7,A,)E 41*+3,+ A/+,7:; «1,A/C5/<3D<,, ),@)/»

[i][j] := 0 end

63&?1 3#00?&"31..&<&, 0(M10"-(1" "#,21 31:1.+1, ,&"&3&1 (0"3#.%1"

.1'&<*&M#CM+1 31)3# F# O(|U|*A) 0 '&?&M$C '&+0,# - <*()+.(. P1 0*1/(1" +0,#"$ 1<& .# L"&? L"#'1 – + - '3#,"+D10,&? '3&<3#??+3&-#.++, + - &*+?'+#/.&?. P1&)A&/+?& 3#00?&"31"$ 31:1.+1 -"&3&; D#0"+, # '&"&? (21 31:#"$, .1&)A&/+?& *+ )&*11 L>>1,"+-.& (0"3#.%"$ .1'&<*&M#CM+1 31)3#, +*+ '31/*&21..=; -#3+#." '3+1?*1?. H /#..&; 3#)&"1 &<3#.+D+?0% .1L>>1,"+-.=? 0'&0&)&? (0"3#.1.+%

.1'&<*&M#CM+A 31)13.

5131;/1? , 3#00?&"31.+C -"&3&<& L"#'#. 6#, 1<& -='&*.+"$?

V1'13$ ?&2.& ("-132/#"$, D"& '&0"3&+*+ W68 )1F '&<*&M#CM+A 31)13 – ,#, )(/"& (21 /132+? 1<& - 3(,#A.

J0'&*$F(1? /+.#?+D10,&1 '3&<3#??+3&-#.+1 «0.+F( --13A» /*% '&+0,# &"-1"#. H 0&&"-1"0"-++ 0 "1&3+1;, -=3#2#1? &"-1" '&/F#/#D+ D131F &"-1"=, 3#.11

.#;/1..=1 /*% /3(<+A '&/F#/#D. E"& &0(M10"-*%1"0% 0*1/(CM+? &)3#F&?. I1,(331.".=1 0&&".&:1.+%, '3+-1/1..=1 - 3#F/. 3.3, -=3#2#C" F.#D1.+1 >(.,@++ f(state, k) D131F F.#D1.+% >(.,@++ f(st, k-1) /*% 3#F*+D.=A 0&0"&%.+; st U. 9/.#,& /*% /#..&<& 0&0"&%.+% state .1(/&).& &'31/1*%"$, +F ,#,&<& 0&0"&%.+% st ?&< '3&+F&;"+ '131A&/ - L"& 0&0"&%.+1 .# '31/=/(M1? :#<1. 5&L"&?( (/&).11 F#>+,0+3&-#"$ '#3( (state, k) +, '131)+3#% -01 0+?-&*=

19

#*>#-+"#, &'31/1*%"$, - ,#,+1 0&0"&%.+% s (- F#-+0+?&0"+ &" &D131/.&<& 0+?-&*#) )(/1" '3&+0A&/+"$ '131A&/ .# 0*1/(CM1? :#<1. 53+ L"&? ,#2/=; 3#F .1&)A&/+?& (-1*+D+-#"$ F.#D1.+1 >(.,@++ f(s, k+1) .# -1*+D+.( f(state, k).

O#-1/1? /*% F.#D1.+; >(.,@++ f &/.&+?1..=; ?#00+- f[state, k]. O#'+:1? .# '01-/&,&/1 31:1.+1 /*% -"&3&<& L"#'# 0 '&?&M$C /+.#?+D10,&<& '3&<3#??+3&-#.+%, &0.&-#..&1 .# 31,(331.".=A 0&&".&:1.+;, '3+-1/1..=A - 3#F/. 3.3. GD"+"1, D"& @+,* '& -01? 0&0"&%.+%? -,*CD#1" >+,"+-.&1 0&0"&%.+1 «P1/&'(0,» '&/ .&?13&? .&*$, /&)#-*1..&1 '&0*1 (/#*1.+% .1'&<*&M#CM+A 31)13. 5&L"&?( -?10"& ?.&210"-# 0&0"&%.+; State )(/1" -0"31D#"$0% ?.&210"-& State0, -,*CD#CM11 1M1 + 0&0"&%.+1 «P1/&'(0,».

//L0*1 4A/4/@ /:3B37E48 - 13>35E1/+ 4/47/81** f[init, 0] := 1

//K 1/5E – -/ -4,. /4735E12. 4/47/81*8.

for i in State0 do
if (i <>	init) then
f[i,0]	:=	0
// M>*73,+	:/5*>,47-/ 0/A;4:3,+2. n-4*+-/5E12. 47)/:
for k := 1	to	n do

for	st in State0 do // (/ -4,+ 4/47/81*8+
for	c in Alpha do	// (/ -4,+	4*+-/53+ 3563-*73
	f[#[st,c],k] := f[#[st,c],k]		+ f[st,k-1]

ans := 0

// M;++*);,+ A/ -4,+ 7,)+*135E12+ 4/47/81*8+ for st in TerminalState do ans := ans + f[st,n]

O#D1? F#-&/+"$ /-(?13.=; ?#00+-? H1/$ - ,#2/=; ?&?1." +0'&*$F(1"0% "&*$,& '31/=/(M11 F.#D1.+1. W&0"#"&D.& &/.&?13.&<& ?#00+-# sum[state] – ,&*+D10"-& 0'&0&)&- &,#F#"$0% - /#..&? 0&0"&%.++, ,&*+D10"-& '3&:1/:+A :#<&- +*+, D"& "& 21, '3&'(M1..=A 0+?-&*&-, F#>+,0+3&-#.&.

JF?1.+? '01-/&,&/, D"&)= -?10"& /-(?13.&<& ?#00+-# +0'&*$F&-#*0% &/.&?13.=;.

//L0*1 4A/4/@ /:3B37E48 - 13>35E1/+ 4/47/81** sum[init] := 1

//K 1/5E – -/ -4,. /4735E12. 4/47/81*8.

for i in State0 do

if (i <> init) then sum[i] := 0

// M>*73,+ :/5*>,47-/ 0/A;4:3,+2. n-4*+-/5E12. 47)/: for k := 1 to n do

begin

sum2 := sum

for i in State0 do sum[i] := 0 for i in State do

for c in Alpha do

sum[#[i][c]] := sum[#[i][c]] + sum2[i]

end

20