АВТОМА́ТОВ ТЕО́РИЯ

АВТОМА́ТОВ ТЕО́РИЯ, раз­дел дис­крет­ной ма­те­ма­ти­ки, изу­чаю­щий ма­те­ма­тич. мо­де­ли пре­об­ра­зо­ва­те­лей дис­крет­ной ин­фор­ма­ции, на­зы­вае­мых ав­то­ма­та­ми. При­ме­ра­ми та­ких пре­об­ра­зо­ва­те­лей яв­ля­ют­ся как ре­аль­ные сис­те­мы (вы­чис­лит. ма­ши­ны, тех­нич. ав­то­ма­ты, жи­вые ор­га­низ­мы), так и аб­ст­ракт­ные сис­те­мы (аб­ст­ракт­ные вы­чис­лит. ма­ши­ны, ак­сио­ма­тич. тео­рии). А. т. воз­ник­ла в сер. 20 в. в свя­зи с изу­че­ни­ем ав­то­ма­тов как ма­те­ма­тич. мо­де­лей био­ло­гич. сис­тем и вы­чис­лит. ма­шин. В даль­ней­шем про­бле­ма­ти­ка А. т. су­ще­ст­вен­но рас­ши­ри­лась. А. т. тес­но свя­за­на с тео­ри­ей ал­го­рит­мов, в ча­ст­но­сти с тео­ри­ей аб­ст­ракт­ных вы­чис­ли­т. ма­шин, по­сколь­ку ав­то­ма­ты мож­но рас­смат­ри­вать как слу­чай их ап­прок­си­ма­ции.

Ав­то­мат мож­но оха­рак­те­ри­зо­вать как уст­рой­ст­во, имею­щее вход­ной и вы­ход­ной ка­на­лы и на­хо­дя­щее­ся в ка­ж­дый дис­крет­ный мо­мент вре­ме­ни в од­ном из внутр. со­стоя­ний. По вход­но­му ка­на­лу в та­кой мо­мент по­сту­па­ют сиг­на­лы-воз­дей­ст­вия. В те же мо­мен­ты по вы­ход­но­му ка­на­лу уст­рой­ст­во вы­да­ёт сиг­на­лы-ре­ак­ции. Со­стоя­ния ав­то­ма­та, сиг­на­лы-воз­дей­ст­вия и сиг­на­лы-ре­ак­ции за­да­ют­ся бу­к­ва­ми со­от­вет­ст­вую­щих ал­фа­ви­тов: ал­фа­ви­та со­стоя­ний, а так­же ал­фа­ви­тов вход­ных и вы­ход­ных сиг­на­лов. За­ко­ны взаи­мо­дей­ст­вия букв этих ал­фа­ви­тов за­да­ют­ся дву­мя функциями – функ­ци­ей пе­ре­хо­дов и функ­ци­ей вы­хо­дов, ото­бра­жаю­щи­ми па­ры (состояние – вход­ная бу­к­ва), в со­стоя­ния и вы­ход­ные бук­вы со­от­вет­ст­вен­но. Вход­ной сре­дой для ав­то­ма­та яв­ля­ет­ся мно­же­ст­во слов во вход­ном ал­фа­ви­те, а внут­рен­ней и вы­ход­ной его сре­да­ми яв­ля­ют­ся мно­же­ст­ва слов в ал­фа­ви­те со­стоя­ний и вы­ход­ном ал­фа­ви­те. Ав­то­мат по­бу­к­вен­но пе­ре­ра­ба­ты­ва­ет сло­ва из вход­ной сре­ды в сло­ва двух дру­гих сред. Этот про­цесс на­зы­ва­ет­ся по­ве­де­ни­ем ав­то­ма­та. Свой­ст­ва ал­фа­ви­тов и функ­ций оп­ре­де­ля­ют разл. ти­пы ав­то­ма­тов. В слу­чае ко­гда все ал­фа­ви­ты ко­неч­ны, по­лу­ча­ют ко­неч­ный ав­то­мат, в про­тив­ном слу­чае ав­то­мат на­зы­ва­ют бес­ко­неч­ным. За­ме­на функ­ций на от­но­ше­ния при­во­дит к час­тич­ным и не­де­терми­ни­ро­ван­ным ав­то­ма­там; ис­поль­зо­ва­ние слу­чай­ных функ­ций при­во­дит к ве­ро­ят­но­ст­но­му ав­то­ма­ту. При ин­тер­пре­та­ции вход­ной сре­ды тер­ма­ми или гра­фа­ми при­хо­дят к ав­то­ма­там над тер­ма­ми и ав­то­ма­там в ла­би­рин­тах.

Боль­шин­ст­во за­дач А. т. яв­ля­ют­ся об­щи­ми для осн. ви­дов управ­ляю­щих сис­тем, к ним от­но­сят­ся за­да­чи ана­ли­за и син­те­за ав­то­ма­тов, за­да­чи о пол­но­те, ми­ни­ми­за­ции, а так­же за­да­чи, свя­зан­ные с эк­ви­ва­лент­ны­ми пре­об­ра­зо­ва­ния­ми ав­то­ма­тов. За­да­ча ана­ли­за со­сто­ит в том, что­бы по за­дан­но­му ав­то­ма­ту опи­сать его по­ве­де­ние или по не­пол­ным дан­ным об ав­то­ма­те и его функ­цио­ни­ро­ва­нию ус­та­но­вить те или иные его свой­ст­ва. За­да­ча син­те­за со­сто­ит в по­строе­нии ав­то­ма­та с за­дан­ным по­ве­де­ни­ем, или функ­цио­ни­ро­ва­ни­ем. К этой за­да­че при­мы­ка­ют про­бле­мы, свя­зан­ные с оцен­кой слож­но­сти ав­то­ма­тов, об­ла­даю­щих за­дан­ным по­ве­де­ни­ем, а так­же с по­строе­ни­ем оп­ти­маль­ных в оп­ре­де­лён­ном смыс­ле ав­то­ма­тов. За­да­ча о пол­но­те со­сто­ит в том, что­бы вы­яс­нить, мож­но ли дан­ное мно­же­ст­во ав­то­ма­тов по­лу­чить из мень­ше­го мно­же­ст­ва с по­мо­щью не­ко­то­рых опе­ра­ций над ав­то­ма­та­ми. За­да­ча ми­ни­ми­за­ции ав­то­ма­тов со­сто­ит в ми­ни­ми­за­ции зна­че­ний па­ра­мет­ров ав­то­ма­тов (напр., чис­ла со­стоя­ний), при ко­то­рой по­лу­ча­ет­ся ав­то­мат, эк­ви­ва­лент­ный в том или ином смыс­ле ис­ход­но­му. По­ми­мо за­дач, об­щих для осн. ви­дов управ­ляю­щих сис­тем, в А. т. рас­смат­ри­ва­ют­ся спе­ци­фич. про­бле­мы, ха­рак­тер­ные для ав­то­ма­тов. Так, в за­ви­си­мо­сти от ус­ло­вий за­да­чи по­ве­де­ние ав­то­ма­тов удоб­но за­да­вать на раз­ных язы­ках (ре­гу­ляр­ные вы­ра­же­ния, ка­но­нич. урав­не­ния, язык ло­ги­ки пре­ди­ка­тов и т. п.), в свя­зи с чем важ­ны­ми за­да­ча­ми яв­ля­ют­ся вы­бор дос­та­точ­но удоб­но­го аде­к­ват­но­го язы­ка и пе­ре­вод с од­но­го язы­ка на дру­гой. С за­да­ча­ми син­те­за и эк­ви­ва­лент­ных пре­об­ра­зо­ва­ний свя­за­на за­да­ча ми­ни­ми­за­ции чис­ла со­стоя­ний ав­то­ма­та. В свя­зи с мо­де­ли­ро­ва­ни­ем по­ве­де­ния ав­то­ма­тов од­но­го клас­са ав­то­ма­та­ми др. клас­са воз­ни­ка­ют за­да­чи ми­ни­ми­за­ции мо­де­ли­рую­щих ав­то­ма­тов и оцен­ки их слож­но­сти. Спец. раз­дел А. т. свя­зан с т. н. экс­пе­ри­мен­та­ми с ав­то­ма­та­ми. Осн. за­да­ча это­го раз­де­ла со­сто­ит в том, что­бы по­лу­чить оп­ре­де­лён­ные све­де­ния о строе­нии ав­то­ма­та пу­тём на­блю­де­ния его ре­ак­ции на те или иные внеш­ние воз­дей­ст­вия. При этом воз­ни­ка­ют за­да­чи, свя­зан­ные с клас­си­фи­ка­ци­ей экс­пе­ри­мен­тов и с во­про­са­ми раз­ре­ши­мо­сти за­дач оп­ре­де­лён­ны­ми ви­да­ми экс­пе­ри­мен­тов, а так­же с оцен­ка­ми длин ми­ним. экс­пе­ри­мен­тов, дос­та­точ­ных для ре­ше­ния тех или иных за­дач. По­ня­тие экс­пе­ри­мен­та с ав­то­ма­та­ми ис­поль­зу­ет­ся так­же в за­да­чах кон­тро­ля ав­то­ма­тов. Спец. раз­де­ла­ми А. т. яв­ля­ют­ся иг­ры ав­то­ма­тов и по­ве­де­ние ав­то­ма­тов в слу­чай­ной сре­де, в ко­то­рых рас­смат­ри­ва­ют­ся во­про­сы взаи­мо­дей­ст­вия ав­то­ма­тов друг с дру­гом и с оп­ре­де­лён­ны­ми внеш­ни­ми сре­да­ми. Мно­гие из пе­ре­чис­лен­ных вы­ше за­дач мо­гут рас­смат­ри­вать­ся как мас­со­вые про­бле­мы (см. Ал­го­рит­ми­че­ская про­бле­ма). Для ко­неч­ных ав­то­ма­тов боль­шин­ст­во из них име­ет по­ло­жи­тель­ное ре­ше­ние.

А. т. на­хо­дит при­ме­не­ние во мно­гих об­лас­тях. Напр., сред­ст­ва­ми А. т. до­ка­зы­ва­ет­ся раз­ре­ши­мость не­ко­то­рых фор­маль­ных ис­чис­ле­ний. Ме­то­ды и по­ня­тия А. т. су­ще­ст­вен­но ис­поль­зу­ют­ся в ма­те­ма­ти­че­ской лин­гвис­ти­ке. По­ня­тие ав­то­ма­та мо­жет слу­жить мо­дель­ным объ­ек­том в раз­но­об­раз­ных за­да­чах, бла­го­да­ря че­му воз­мож­но при­ме­не­ние А. т. в раз­лич­ных при­клад­ных ис­сле­до­ва­ни­ях.