Теория обобщенных линейных автоматов
Визначено лінійні та афінні автомати у загальному вигляді. Введено поняття розмірності для скінчених автоматів і доведено, що існують автомати максимальної розмірності. Доведено, що проблема досяжності станів у мономіальній формі не є алгоритмічно-розв’язною для двовимірних афінних автоматів. Доведе...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/44301 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Теория обобщенных линейных автоматов / И.К. Рысцов // Кибернетика и системный анализ. — 2009. — № 1. — С. 10-21. — Бібліогр.: 18 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-44301 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-443012013-05-29T03:08:24Z Теория обобщенных линейных автоматов Рысцов, И.К. Кибернетика Визначено лінійні та афінні автомати у загальному вигляді. Введено поняття розмірності для скінчених автоматів і доведено, що існують автомати максимальної розмірності. Доведено, що проблема досяжності станів у мономіальній формі не є алгоритмічно-розв’язною для двовимірних афінних автоматів. Доведено також аналог теореми Мура про еквівалентні стани, а також лінійні аналоги теорем про установочні та діагностичні слова. Розглянуто застосування лінійних автоматів у математичній економіці. Linear and affine automata are considered in their general form. The concept of the dimension of a finite automaton is introduced and finite automata of maximal dimensions are shown to be possible. The state reachability problem in monomial form is proved to be undecidable for two-dimensional affine automata. An analogue of Moore’s theorem and theorems on homogenous and diagnostic words are also proved. An application of linear automata to mathematical economics is considered. 2009 Article Теория обобщенных линейных автоматов / И.К. Рысцов // Кибернетика и системный анализ. — 2009. — № 1. — С. 10-21. — Бібліогр.: 18 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/44301 519.713.4 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Рысцов, И.К. Теория обобщенных линейных автоматов Кибернетика и системный анализ |
| description |
Визначено лінійні та афінні автомати у загальному вигляді. Введено поняття розмірності для скінчених автоматів і доведено, що існують автомати максимальної розмірності. Доведено, що проблема досяжності станів у мономіальній формі не є алгоритмічно-розв’язною для двовимірних афінних автоматів. Доведено також аналог теореми Мура про еквівалентні стани, а також лінійні аналоги теорем про установочні та діагностичні слова. Розглянуто застосування лінійних автоматів у математичній економіці. |
| format |
Article |
| author |
Рысцов, И.К. |
| author_facet |
Рысцов, И.К. |
| author_sort |
Рысцов, И.К. |
| title |
Теория обобщенных линейных автоматов |
| title_short |
Теория обобщенных линейных автоматов |
| title_full |
Теория обобщенных линейных автоматов |
| title_fullStr |
Теория обобщенных линейных автоматов |
| title_full_unstemmed |
Теория обобщенных линейных автоматов |
| title_sort |
теория обобщенных линейных автоматов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2009 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/44301 |
| citation_txt |
Теория обобщенных линейных автоматов / И.К. Рысцов // Кибернетика и системный анализ. — 2009. — № 1. — С. 10-21. — Бібліогр.: 18 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT ryscovik teoriâobobŝennyhlinejnyhavtomatov |
| first_indexed |
2025-07-04T02:44:09Z |
| last_indexed |
2025-07-04T02:44:09Z |
| _version_ |
1836682628196990976 |
| fulltext |
ÓÄÊ 519.713.4
È.Ê. ÐÛÑÖÎÂ
ÒÅÎÐÈß ÎÁÎÁÙÅÍÍÛÕ ËÈÍÅÉÍÛÕ ÀÂÒÎÌÀÒÎÂ
Êëþ÷åâûå ñëîâà: ëèíåéíûå àâòîìàòû, àôôèííûå àâòîìàòû, ëèíåéíûå äèñê-
ðåòíûå ñèñòåìû.
ÂÂÅÄÅÍÈÅ
Ïî÷òè 40 ëåò íàçàä À.À. Ìó÷íèê îïóáëèêîâàë ïèîíåðñêóþ ðàáîòó îá îáùèõ
ëèíåéíûõ àâòîìàòàõ [1]. Îñíîâíàÿ öåëü äàííîé ñòàòüè — ñèñòåìàòèçàöèÿ ðå-
çóëüòàòîâ â ýòîé îáëàñòè, ïîëó÷åííûõ ê íàñòîÿùåìó âðåìåíè.  ðàáîòå îïðåäå-
ëÿþòñÿ ëèíåéíûå è àôôèííûå àâòîìàòû è ââîäèòñÿ ïîíÿòèå ðàçìåðíîñòè äëÿ
êîíå÷íîãî àâòîìàòà. Ðàññìàòðèâàåòñÿ ïðîáëåìà äîñòèæèìîñòè ñîñòîÿíèé â àâòî-
ìàòàõ è äîêàçûâàåòñÿ, ÷òî îíà àëãîðèòìè÷åñêè íåðàçðåøèìà äëÿ äâóìåðíûõ àô-
ôèííûõ àâòîìàòîâ. Äàëåå ðàññìàòðèâàþòñÿ ëèíåéíûå àâòîìàòû ñ âûõîäîì è äî-
êàçûâàåòñÿ àíàëîã òåîðåìû Ìóðà îá ýêâèâàëåíòíûõ ñîñòîÿíèÿõ, à òàêæå ëèíåé-
íûå àíàëîãè òåîðåì äëÿ óñòàíîâî÷íûõ è äèàãíîñòè÷åñêèõ ñëîâ, ðàññìîòðåíû
ïðèëîæåíèÿ ëèíåéíûõ àâòîìàòîâ â ìàòåìàòè÷åñêîé ýêîíîìèêå.
1. ËÈÍÅÉÍÛÅ ÀÂÒÎÌÀÒÛ
(Ïîëíûì) ëèíåéíûì n-ìåðíûì àâòîìàòîì (áåç âûõîäà) A íàä ïîëåì K íàçûâàåò-
ñÿ òðîéêà A V X f� ( , , ), ãäå V K n� — ëèíåéíîå n-ìåðíîå ïðîñòðàíñòâî ñîñòîÿ-
íèé (âåêòîðîâ äëèíû n) íàä ïîëåì K , X a ak�{ , , }1 � — êîíå÷íûé âõîäíîé àë-
ôàâèò, f — îòîáðàæåíèå âèäà f X n K: ( , )�Mat , êîòîðîå êàæäîìó ñèìâîëó èç
x X� ñòàâèò â ñîîòâåòñòâèèå êâàäðàòíóþ ìàòðèöó n-ãî ïîðÿäêà f x( ) ñ ýëåìåíòà-
ìè èç K . ×èñëî n íàçûâàåòñÿ ðàçìåðíîñòüþ ëèíåéíîãî àâòîìàòà.
Îòîáðàæåíèå f îïðåäåëÿåò ôóíêöèþ ïåðåõîäîâ F x f x( , ) ( )� �� � , ãäå ñïðàâà
ñòîèò ïðîèçâåäåíèå âåêòîðà-ñòðîêè � � ( , , )k kn1 � íà n n� ìàòðèöó f x( ). Â ýòîì
ñëó÷àå ôóíêöèÿ ïåðåõîäîâ áóäåò ëèíåéíîé òîëüêî ïî ïåðâîìó àðãóìåíòó, ïîýòîìó
A. Ìó÷íèê íàçâàë ýòè àâòîìàòû «îáùèìè» ëèíåéíûìè àâòîìàòàìè [1], ÷òîáû ïîä-
÷åðêíóòü èõ îòëè÷èå îò êëàññè÷åñêèõ ëèíåéíûõ àâòîìàòîâ. Ïîäðîáíåå íà ýòîì îò-
ëè÷èè îñòàíîâèìñÿ íèæå.
Ïîñêîëüêó ìíîæåñòâî ìàòðèö Mat( , )n K ÿâëÿåòñÿ ìóëüòèïëèêàòèâíûì ìîíîè-
äîì, òî îòîáðàæåíèå f ìîæíî ïðîäîëæèòü äî ãîìîìîðôèçìà, îïðåäåëåííîãî íà
ñâîáîäíîì ìîíîèäå X �, êîòîðûé êàæäîìó âõîäíîìó ñëîâó (ìîíîìó), w x xm� 1� ,
x Xi � , 1� �i m, ñîïîñòàâëÿåò ïðîèçâåäåíèå áàçîâûõ ìàòðèö:
f w f x f x f xm( ) ( ) ( ) ( )� � � �1 2 � . (1)
Çàìåòèì, ÷òî f e I( ) � , ãäå e — ïóñòîå ñëîâî, I — åäèíè÷íàÿ ìàòðèöà. Òîãäà
ôóíêöèÿ ïåðåõîäîâ îïðåäåëÿåòñÿ äëÿ ëþáûõ âõîäíûõ ñëîâ ïî ôîðìóëå F w( , )� �
� �� f w( ), ãäå ïðàâàÿ ÷àñòü ïî-ïðåæíåìó ïîíèìàåòñÿ êàê ïðîèçâåäåíèå âåêòîðà
íà ìàòðèöó.
 òåîðèè ëèíåéíûõ ñèñòåì êðîìå îáû÷íûõ âõîäíûõ ñèìâîëîâ ïðèíÿòî ðàñ-
ñìàòðèâàòü «îáîáùåííûå» âõîäû (âõîäíûå âåêòîðû), êîòîðûå ÿâëÿþòñÿ ëèíåéíû-
ìè êîìáèíàöèÿìè ýëåìåíòîâ èç X ñ êîýôôèöèåíòàìè èç ïîëÿ K , ò.å. ýëåìåíòàìè
ëèíåéíîãî ïðîñòðàíñòâà K X( ). Äëÿ âõîäíîãî âåêòîðà u c a c ak k� 1 1 � ìàòðèöà
ïåðåõîäîâ f u( ) îïðåäåëÿåòñÿ ëèíåéíûì îáðàçîì f u c f a c f ak k( ) ( ) ( )� 1 1 � .
Èòàê, ëèíåéíûé àâòîìàò ìîæíî ðàññìàòðèâàòü êàê òðîéêó A V X f� ( , , ), ãäå
f K X n K: ( ) ( , )�Mat — ëèíåéíîå îòîáðàæåíèå âåêòîðíûõ ïðîñòðàíñòâ.
Çàòåì ôóíêöèÿ f ïðîäîëæàåòñÿ íà «îáîáùåííûå» ñëîâà p u um� 1� ,
u K Xi � ( ), 1� �i m, ïî àíàëîãèè ñ ôîðìóëîé (1). Íî ïîñêîëüêó ìíîæåñòâî ìàòðèö
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
© È.Ê. Ðûñöîâ, 2009
Mat ( , )n K ÿâëÿåòñÿ àëãåáðîé, òî ãîìîìîðôèçì (1) ìîæíî ïðîäîëæèòü äî ãîìîìîð-
ôèçìà àëãåáð ñëåäóþùèì îáðàçîì. Ñâîáîäíûé ìîíîèä X � åñòåñòâåííî âêëàäûâàåò-
ñÿ â ñâîáîäíóþ àññîöèàòèâíóþ àëãåáðó K X( )� , êîòîðàÿ ñîñòîèò èç ïîëèíîìîâ îò íå
êîììóòèðóþùèõ ïåðåìåííûõ èç X ñ êîýôôèöèåíòàìè èç ïîëÿ K . Òîãäà ôóíêöèþ
ïåðåõîäîâ ìîæíî äîîïðåäåëèòü äëÿ ëþáîãî ïîëèíîìà p c w c wm m� 1 1 � ëèíåé-
íûì îáðàçîì:
f p c f w c f wm m( ) ( ) ( )� 1 1 � , F p f p( , ) ( )� �� � . (2)
Õîòÿ àâòîìàòíûé ñìûñë èìåþò òîëüêî îáîáùåííûå ñëîâà, êîòîðûå ìîæíî ðàñ-
ñìàòðèâàòü êàê ïðîèçâåäåíèÿ ïîëèíîìîâ ïåðâîé ñòåïåíè, îäíàêî îáùèé ïîäõîä
îáëàäàåò ðÿäîì ïðåèìóùåñòâ. Ôóíêöèÿ ïåðåõîäîâ F V K X V: ( )*� � ñòàíîâèòñÿ
ëèíåéíîé ïî îáîèì àðãóìåíòàì è, ñëåäîâàòåëüíî, ëèíåéíûé àâòîìàò ìîæíî ðàññìàò-
ðèâàòü êàê ìîäóëü íàä êîëüöîì è ïîëüçîâàòüñÿ ñòàíäàðòíûìè àëãåáðàè÷åñêèìè êîí-
ñòðóêöèÿìè èç òåîðèè ìîäóëåé [2]. Ýòî ïîçâîëÿåò îáîáùèòü ïîäõîä Êàëìàíà ê äèñ-
êðåòíûì ëèíåéíûì ñèñòåìàì, êàê ìîäóëÿì íàä êîëüöîì ïîëèíîìîâ [3].
Ðàññìîòðèì íåêîòîðûå ñâîéñòâà ëèíåéíûõ àâòîìàòîâ. Îáîçíà÷èì Kr f p( ) ÿäðî
ìàòðèöû f p( ), ò.å. ïîäïðîñòðàíñòâî ñîñòîÿíèé, ïåðåõîäÿùèõ â íîëü ïîä äåéñòâèåì
ïîëèíîìà p, à Im( )p — ïîäïðîñòðàíñòâî åå çíà÷åíèé (ïîðîæäåííîå ñòðîêàìè
ìàòðèöû). Ðàçìåðíîñòü ïîäïðîñòðàíñòâà U V
îáîçíà÷èì dim( )U . Äåéñòâèå ëè-
íåéíîãî àâòîìàòà ìîæíî ðàñïðîñòðàíèòü íà ïîäìíîæåñòâà ñîñòîÿíèé S V
ïî
ôîðìóëå F S p F s p s S( , ) { ( , ) | }� � . Åñëè U — ïîäïðîñòðàíñòâî, òî åãî îáðàç
F U p( , ) òàêæå áóäåò ïîäïðîñòðàíñòâîì, äëÿ êîòîðîãî âûïîëíÿåòñÿ ñëåäóþùåå
óñëîâèå ìîíîòîííîñòè:
dim dim( ( , )) ( )F U p U� . (3)
Êðîìå òîãî, âûïîëíÿåòñÿ ñëåäóþùåå óñëîâèå, âåðíîå äëÿ ëþáîãî ïîäïðîñòðà-
íñòâà U è ïîëèíîìà p:
dim dim Kr( ( , )) ( ) ( ( )) { }F U p U U f p� �
� 0 . (4)
Ïîäìíîæåñòâî S V
, èíâàðèàíòíîå îòíîñèòåëüíî óìíîæåíèÿ íà âñå âõîäíûå
ñèìâîëû, ò.å. F S x S( , )
äëÿ âñåõ x X� , îïðåäåëÿåò ìóëüòèïëèêàòèâíûé ïîäàâòîìàò
B S V X f� ( , , , ) ëèíåéíîãî àâòîìàòà A V X f� ( , , ). Çàìåòèì, ÷òî ïîäìíîæåñòâî S ìî-
æåò áûòü íå çàìêíóòî îòíîñèòåëüíî ñëîæåíèÿ ñîñòîÿíèé, îäíàêî, âçÿâ åãî ëèíåéíóþ
îáîëî÷êó lin ( )S , ïîëó÷èì ïîäïðîñòðàíñòâî, èíâàðèàíòíîå îòíîñèòåëüíî ñëîæåíèÿ è
óìíîæåíèÿ, ò.å. ëèíåéíûé ïîäàâòîìàò èëè ïîäìîäóëü. Îòìåòèì, ÷òî ïðîöåäóðà ïî-
ñòðîåíèÿ ôàêòîð-àâòîìàòà ïî ëèíåéíîìó ïîäàâòîìàòó ñâîäèòñÿ â ýòîì ñëó÷àå ê ñòàí-
äàðòíîé àëãåáðàè÷åñêîé ïðîöåäóðå ïîñòðîåíèÿ ôàêòîð-ìîäóëÿ ïî ïîäìîäóëþ [2].
2. ÎÁÎÁÙÅÍÍÛÅ ËÈÍÅÉÍÛÅ ÀÂÒÎÌÀÒÛ
Îïðåäåëåíèå ëèíåéíîãî àâòîìàòà, êîòîðîå áûëî äàíî â ïðåäûäóùåì ðàçäåëå äî-
âîëüíî æåñòêîå. Íàïðèìåð, íå êàæäûé êîíå÷íûé àâòîìàò îêàçûâàåòñÿ ïîëíûì
ëèíåéíûì àâòîìàòîì íàä êîíå÷íûì ïîëåì, ïîñêîëüêó ÷èñëî ýëåìåíòîâ â êîíå÷-
íîì ïîëå — ñòåïåíü ïðîñòîãî ÷èñëà. Ïîýòîìó À. Ìó÷íèê äàåò ñëåäóþùåå áîëåå
îáùåå îïðåäåëåíèå [1].
Îïðåäåëåíèå 1. Îáîáùåííûì ëèíåéíûì àâòîìàòîì B S V X f� ( , , , ) íàä ïî-
ëåì K íàçûâàåòñÿ ìóëüòèïëèêàòèâíûé ïîäàâòîìàò ïîëíîãî ëèíåéíîãî àâòîìàòà
A V X f� ( , , ) íàä ýòèì ïîëåì.
 ýòîì ñëó÷àå ïîäìíîæåñòâî S íàçûâàåòñÿ ìíîæåñòâîì ñîñòîÿíèé ïîäàâòîìàòà. Ðàç-
ìåðíîñòü àâòîìàòà B ðàâíà ðàçìåðíîñòè ïîäïðîñòðàíñòâà lin ( )S . ×òîáû âûäåëèòü ëè-
íåéíûå àâòîìàòû, ó êîòîðûõ S V� , ìû íàçâàëè èõ «ïîëíûìè» ëèíåéíûìè àâòîìàòàìè.
Îáîáùåííûå ëèíåéíûå àâòîìàòû êëàññèôèöèðóþòñÿ ïî ñòðóêòóðå èõ ìíî-
æåñòâà ñîñòîÿíèé. Ñíà÷àëà ðàññìîòðèì ñëó÷àé, êîãäà ìíîæåñòâî ñîñòîÿíèé ïîäàâ-
òîìàòà êîíå÷íî.
Ïóñòü A S X� ( , , )� — êîíå÷íûé äåòåðìèíèðîâàííûé àâòîìàò (áåç âûõîäà)
ñ n ñîñòîÿíèÿìè S s sn�{ , , }1 � è K — ïðîèçâîëüíîå ïîëå. Ðàññìîòðèì èçâåñòíîå
ìàòðè÷íîå ïðåäñòàâëåíèå êîíå÷íîãî àâòîìàòà. Äëÿ ýòîãî ñ êàæäûì x X� ñâÿ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 11
æåì äâîè÷íóþ n n� ìàòðèöó f x0 ( ) ñëåäóþùèì îáðàçîì: e xij ( ) �1, åñëè
�( , )s x si j� , è e xij ( ) � 0 â ïðîòèâíîì ñëó÷àå. Ïîãðóçèì ìíîæåñòâî S â ëèíåéíîå
ï ð î ñ ò ð à í ñ ò â î â ñ å õ ô î ð ì à ë ü í û õ ë è í å é í û õ ê î ì á è í à ö è é K S( ) �
� � � � �{ | , }c s c s c K s Sn n i i1 1 � è äîîïðåäåëèì ôóíêöèþ ïåðåõîäîâ äëÿ âñåõ
ëèíåéíûõ êîìáèíàöèé �:
F x f x c s x c s xn n( , ) ( ) ( , ) ( , )� � � �� � � � �0 1 1 � .
Îòìåòèì, ÷òî êîíå÷íûé àâòîìàò A áóäåò äåéñòâîâàòü íà áàçèñå S . Çíà÷èò, A áó-
äåò êîíå÷íûì ìóëüòèïëèêàòèâíûì ïîäàâòîìàòîì ëèíåéíîãî n-ìåðíîãî àâòîìà-
òà K A K S X f( ) ( ( ), , )� 0 , êîòîðûé íàçûâàåòñÿ ñòàíäàðòíûì ëèíåéíûì ðàñøèðå-
íèåì êîíå÷íîãî àâòîìàòà A íàä ïîëåì K . Òàêèì îáðàçîì, èìååì ñëåäóþùåå
óòâåðæäåíèå [1].
Ïðåäëîæåíèå 1. Êàæäûé êîíå÷íûé àâòîìàò ñ n ñîñòîÿíèÿìè ÿâëÿåòñÿ îáîá-
ùåííûì ëèíåéíûì n-ìåðíûì àâòîìàòîì íàä ëþáûì ïîëåì.
Äëÿ äàëüíåéøåãî íàì ïîíàäîáèòñÿ òàêæå ïîäàâòîìàò K A2 ( ) ëèíåéíîãî àâòî-
ìàòà K A( ), êîòîðûé íàçûâàåòñÿ ëèíåéíûì àâòîìàòîì ïàð.
Ñëåäñòâèå 1. Ïîäïðîñòðàíñòâî K S2 ( ), ïîðîæäåííîå ñîñòîÿíèÿìè s si j� ,
1� � �i j n, â ëèíåéíîì ðàñøèðåíèè êîíå÷íîãî àâòîìàòà A , îïðåäåëÿåò ëèíåéíûé
ïîäàâòîìàò K A K S X f2 2 0( ) ( ( ), , )� ðàçìåðíîñòè n �1.
 ñâÿçè ñ ïðåäëîæåíèåì 1 âîçíèêàåò âàæíîå ïîíÿòèå ðàçìåðíîñòè êîíå÷íîãî
àâòîìàòà. Äëÿ ïðîñòîòû îïðåäåëèì åãî òîëüêî äëÿ äâîè÷íîãî ïîëÿ GF ( ) { , }2 0 1� ,
ïîñêîëüêó äëÿ îñòàëüíûõ êîíå÷íûõ ïîëåé îíî îïðåäåëÿåòñÿ àíàëîãè÷íî.
Îïðåäåëåíèå 2. Ðàçìåðíîñòüþ dim ( )2 A êîíå÷íîãî àâòîìàòà A íàçûâàåòñÿ íà-
èìåíüøåå ÷èñëî d òàêîå, ÷òî àâòîìàò A èçîìîðôíî âêëàäûâàåòñÿ â ëèíåéíûé àâòî-
ìàò ðàçìåðíîñòè d íàä äâîè÷íûì ïîëåì.
Èç ýòîãî îïðåäåëåíèÿ è ïðåäëîæåíèÿ 1 ïîëó÷àåì ñëåäóþùèå íåðàâåíñòâà äëÿ
ðàçìåðíîñòè êîíå÷íîãî àâòîìàòà A ñ n ñîñòîÿíèÿìè:
log ( ) dim ( )2 2n A n� � . (5)
Íèæíÿÿ îöåíêà çäåñü äîñòèãàåòñÿ íà ëþáîì ëèíåéíîì àâòîìàòå A ðàçìåðíîñòè
d íàä ïîëåì GF ( )2 , ïîñêîëüêó îí áóäåò èìåòü n d� 2 ñîñòîÿíèé. Âåðõíÿÿ îöåíêà
â (5) äîñòèãàåòñÿ íà àâòîìàòå ×åðíû, êîòîðûé çàäàåòñÿ äâóìÿ ïîäñòàíîâêàìè
�( ) ( ( ) )x n� �12 1 1� è �( ) ( )y n� 23 1� íà ìíîæåñòâå ñîñòîÿíèé S n� [ , ]1 .
Òåîðåìà 1. Ðàçìåðíîñòü àâòîìàòà ×åðíû ñ n ñîñòîÿíèÿìè ðàâíà n.
Äîêàçàòåëüñòâî. Ïóñòü A n x y� ([ , ], { , }, )1 � — àâòîìàò ×åðíû ñ n ñîñòîÿíèÿìè.
Ïðåäïîëîæèì ïðîòèâíîå, òîãäà äîëæåí ñóùåñòâîâàòü âçàèìíî îäíîçíà÷íûé ìîíî-
ìîðôèçì (âëîæåíèå) �: ( ( ) , , )A GF X fd� 2 , ãäå d n� . Íî òîãäà ñîñòîÿíèÿ èç ïîä-
ìíîæåñòâà �([ , ])1 n äîëæíû áûòü ëèíåéíî çàâèñèìû, è, ñëåäîâàòåëüíî, ñóùåñòâóåò
ñîñòîÿíèå �( )i , êîòîðîå ëèíåéíî âûðàæàåòñÿ ÷åðåç ïðåäûäóùèå �( )i �
� � �( ) ( )i im1 � , ãäå 0 � �i ij , 1� �j m. Óìíîæàÿ ýòî ðàâåíñòâî íà ñëîâî yn i� ,
óâåëè÷èâàåì íîìåðà âñåõ ñîñòîÿíèé íà n i� è ïîëó÷àåì � � �( ) ( ) ( )n l lm� 1 � , ãäå
0 � �l nj , 1� �j m. Íàêîíåö, óìíîæàÿ ýòî ðàâåíñòâî íà x, ïîëó÷àåì � �( ) ( )1 � n ,
÷òî ïðîòèâîðå÷èò âçàèìíîé îäíîçíà÷íîñòè � .
Òàêèì îáðàçîì, òåîðåìà äîêàçàíà.
Ñëåäóþùèé âàæíûé ÷àñòíûé ñëó÷àé îáîáùåííûõ ëèíåéíûõ àâòîìàòîâ ñâÿçàí
ñ âåðîÿòíîñòíûìè àâòîìàòàìè, êîãäà ìíîæåñòâî ñîñòîÿíèé — îãðàíè÷åííîå âû-
ïóêëîå ìíîæåñòâî (ñèìïëåêñ). Âåðîÿòíîñòíûì àâòîìàòîì ñ n ñîñòîÿíèÿìè (áåç âû-
õîäà) íàçûâàåòñÿ òðîéêà A S X f� ( , , )1 , ãäå S — êîíå÷íîå ìíîæåñòâî ñîñòîÿíèé,
X — êîíå÷íîå ìíîæåñòâî âõîäíûõ ñèìâîëîâ, à f1 — íàáîð ñòîõàñòè÷åñêèõ ìàòðèö
f X n R1: ( , )� Mat .  ýòîì ñëó÷àå èç áàçèñíûõ ñîñòîÿíèé S áóäóò äîñòèæèìû
òîëüêî ðàñïðåäåëåíèÿ ( , , )r rn1 � , ðàñïîëîæåííûå â åäèíè÷íîì n-ìåðíîì ñèìïëåê-
ñå �n , ò.å. òî÷êè, êîîðäèíàòû êîòîðûõ óäîâëåòâîðÿþò óðàâíåíèþ r rn1 1 �� ,
ãäå 0 1� �ri , 1� �i n. Çíà÷èò, ñèìïëåêñ �n
nR� áóäåò â ýòîì ñëó÷àå ìóëüòèïëèêà-
òèâíûì ïîäàâòîìàòîì ëèíåéíîãî àâòîìàòà R A R X fn( ) ( , , )� 1 , êîòîðûé åñòåñòâåí-
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
íî íàçâàòü ëèíåéíûì ðàñøèðåíèåì âåðîÿòíîñòíîãî àâòîìàòà. Òàêèì îáðàçîì, ïîëó-
÷àåì ñëåäóþùåå óòâåðæäåíèå [1].
Ïðåäëîæåíèå 2. Êàæäûé âåðîÿòíîñòíûé àâòîìàò ñ n ñîñòîÿíèÿìè ÿâëÿåòñÿ îá-
îáùåííûì ëèíåéíûì n-ìåðíûì àâòîìàòîì íàä ïîëåì âåùåñòâåííûõ ÷èñåë.
Äëÿ âåðîÿòíîñòíûõ àâòîìàòîâ ïîäàâòîìàò ïàð òàêæå îêàçûâàåòñÿ ïîëåçíûì,
íî ýòó êîíñòðóêöèþ ìîæíî ðàññìîòðåòü è ñ îáùèõ ïîçèöèé.
Îïðåäåëåíèå 3. Ìóëüòèïëèêàòèâíûé ïîäàâòîìàò B S V X f� ( , , , ) ëèíåéíîãî
àâòîìàòà A V X f� ( , , ) íàä ïîëåì K íàçîâåì àôôèííûì, åñëè ìíîæåñòâî ñîñòîÿíèé
S ÿâëÿåòñÿ àôôèííîé ãèïåðïëîñêîñòüþ â V.
Íàïîìíèì, ÷òî àôôèííîå ïîäïðîñòðàíñòâî S — ýòî ëèíåéíîå ïîäïðîñòðàíñòâî L,
ñäâèíóòîå íà íåêîòîðûé âåêòîð �, ò.å. S L� �.  ýòîì ñëó÷àå ïîäïðîñòðàíñòâî L
íàçûâàåòñÿ íàïðàâëÿþùèì (íåñóùèì) äëÿ S [4]. Äëÿ ãèïåðïëîñêîñòè ðàçìåðíîñòü
íàïðàâëÿþùåãî ïîäïðîñòðàíñòâà ðàâíà n �1. Èç êîíñòðóêöèé ëèíåéíûõ ðàñøèðå-
íèé äëÿ êîíå÷íûõ è âåðîÿòíîñòíûõ àâòîìàòîâ âèäíî, ÷òî ìíîæåñòâà èõ ñîñòîÿíèé
åñòåñòâåííî âêëàäûâàþòñÿ â èíâàðèàíòíóþ àôôèííóþ ãèïåðïëîñêîñòü
k kn1 1 �� . Çíà÷èò, ëþáîé êîíå÷íûé èëè âåðîÿòíîñòíûé àâòîìàò ìîæíî ðàñøè-
ðèòü äî àôôèííîãî ïîäàâòîìàòà. Êðîìå òîãî, èç ìóëüòèïëèêàòèâíîé çàìêíóòîñòè
àôôèííîãî ïîäïðîñòðàíñòâà S ñëåäóåò ìóëüòèïëèêàòèâíàÿ çàìêíóòîñòü åå íàïðàâ-
ëÿþùåãî ïîäïðîñòðàíñòâà L, ñëåäîâàòåëüíî, àâòîìàò ïàð ( , , )L X f ìîæíî îïðåäå-
ëèòü äëÿ ëþáîãî àôôèííîãî ïîäàâòîìàòà B S V X f� ( , , , ) .
Ñëåäñòâèå 2. Äëÿ ëþáîãî àôôèííîãî ïîäàâòîìàòà B S V X f� ( , , , ) ïîäïðîñòðàí-
ñòâî, ïîðîæäåííîå ñîñòîÿíèÿìè s t� , s t S, � , îïðåäåëÿåò ëèíåéíûé ïîäàâòîìàò ïàð
B L X f2 � ( , , ) ðàçìåðíîñòè n �1.
3. ÄÎÑÒÈÆÈÌÎÑÒÜ ÑÎÑÒÎßÍÈÉ Â ËÈÍÅÉÍÛÕ ÀÂÒÎÌÀÒÀÕ
Äîñòèæèìîñòü ñîñòîÿíèé â ëèíåéíûõ àâòîìàòàõ ìîæíî òðàêòîâàòü ñ äâóõ òî÷åê
çðåíèÿ â çàâèñèìîñòè îò òîãî, äîïóñêàþòñÿ ïîëèíîìû íà âõîäå àâòîìàòà èëè
äîñòèæèìîñòü îñóùåñòâëÿåòñÿ òîëüêî ñ ïîìîùüþ ìîíîìîâ. Íî îáùèå ðåçóëüòà-
òû, íå çàâèñÿùèå îò îñíîâíîãî ïîëÿ, óäàåòñÿ ïîëó÷èòü òîëüêî äëÿ îáîáùåííîé
äîñòèæèìîñòè.
Ïóñòü A V X f� ( , , ) — ïîëíûé ëèíåéíûé àâòîìàò, òîãäà ìíîæåñòâîì ìîíîìèàëü-
íî äîñòèæèìûõ ñîñòîÿíèé äëÿ ñîñòîÿíèÿ ��V â àâòîìàòå A íàçûâàåòñÿ ñëåäóþùåå
ìíîæåñòâî: RmA F w w X( ) { ( , ) | }� �� � � . Ïðè îãðàíè÷åíèè íà äëèíó ñëîâ ñîîòâåò-
ñòâóþùåå ìíîæåñòâî äîñòèæèìîñòè îáîçíà÷èì Rmi F w l w i w X( ) { ( , ) | ( ) , }� �� � � � ,
ãäå l w( ) — äëèíà ñëîâà, i � 0. Ñîîòâåòñòâóþùèå ìíîæåñòâà ïîëèíîìèàëüíî äîñòèæè-
ìûõ ñîñòîÿíèé îáîçíà÷èì RpA F p p K X( ) { ( , ) | ( )}*� �� � è Rp i ( )� �
� � � �{ ( , ) | ( ) , ( )}F p d p i p K X� , ãäå d p( ) — ñòåïåíü ïîëèíîìà p.
Íåòðóäíî âèäåòü, ÷òî ìíîæåñòâà Rp i ( )� áóäóò ëèíåéíûìè ïîäïðîñòðàí-
ñòâàìè, ïîñêîëüêó èç ñâîéñòâà (2) âûòåêàåò ðàâåíñòâî äëÿ ëþáîãî ïîëèíîìà
p c w c wm m� 1 1 � :
F p c F w c F wm m( , ) ( , ) ( , )� � �� 1 1 � . (6)
Îòñþäà ñëåäóåò, ÷òî Rp i ( )� — ëèíåéíàÿ îáîëî÷êà äëÿ Rmi ( )� :
Rp lin Rmi i( ) ( ( ))� �� , i � 0. (7)
Äàëåå èç îïðåäåëåíèé î÷åâèäíî, ÷òî ïîäïðîñòðàíñòâà Rp i ( )� îáðàçóþò âîçðàñ-
òàþùóþ (ïî i) ïîñëåäîâàòåëüíîñòü
Rp Rp Rp0 1( ) ( ) ( )� � �
� �n . (8)
Ýòîò ðÿä äîëæåí ñòàáèëèçèðîâàòüñÿ â ñèëó êîíå÷íîìåðíîñòè ïðîñòðàíñòâà ñî-
ñòîÿíèé. Äåéñòâèòåëüíî, äëÿ íåíóëåâîãî ñîñòîÿíèÿ � èìååì dim( ( ))Rp0 1� � , ñëå-
äîâàòåëüíî, ñòðîãèå íåðàâåíñòâà â ðÿäó (8) ìîãóò ïðîäîëæàòüñÿ íå äàëåå n-ãî
ìåñòà, è íàéäåòñÿ òàêîå ÷èñëî i i n, 1� � , ÷òî Rp Rpi i� �1 ( ) ( )� � . Ïîñëå ýòîãî ðÿä
(8) äîëæåí ñòàáèëèçèðîâàòüñÿ, ïîñêîëüêó F xi i( ( ), ) ( )Rp Rp� �
1 1� � äëÿ âñåõ
x X� . Çíà÷èò, â ýòîì ñëó÷àå Rp Rp Rpi n A� �� �1 1( ) ( ) ( )� � � è ìû ïðèõîäèì ê
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 13
ñëåäóþùåìó óòâåðæäåíèþ, êîòîðîå âåðíî äëÿ ëþáîãî ïîëÿ, ëþáîãî n-ìåðíîãî
àâòîìàòà A íàä ýòèì ïîëåì è ëþáîãî ñîñòîÿíèÿ �:
Rp RpA n( ) ( )� �� �1 . (9)
Ýòîìó ðàâåíñòâó ìîæíî ïðèäàòü ôîðìó, àíàëîãè÷íóþ êîíå÷íîìó ñëó÷àþ, íî
âìåñòî êîíå÷íîñòè çäåñü ôèãóðèðóåò êîíå÷íîìåðíîñòü.
Òåîðåìà 2. Åñëè â n-ìåðíîì ëèíåéíîì àâòîìàòå A íàä ïîëåì K âûïîëíÿåòñÿ
óñëîâèå t sA�Rp ( ), òî ñóùåñòâóåò ïîëèíîì p ñòåïåíè, íå áîëüøåé n – 1, òàêîé, ÷òî
F s p t( , ) � .
Îòìåòèì, ÷òî Rpn�1 ( )� áóäåò íàèìåíüøèì ïîäìîäóëåì, ñîäåðæàùèì ñîñòîÿ-
íèå �. Ýòó òåîðåìó ìîæíî äîêàçàòü è äëÿ îáîáùåííûõ ñëîâ p u um� 1� , åñëè ïî-
ëîæèòü L F p l p m p K Xm ( ) { ( , ) | ( ) , ( ) }� �� � � � è ñòðîèòü ïîäïðîñòðàíñòâà Lm ( )�
èíäóêòèâíî ïî ôîðìóëå:
L L F L am m m j
j
k
( ) ( ) ( ( ), )� � �� � �
�
�1 1
1
, 1� �m n.
Îòñþäà ñëåäóåò, ÷òî ñòàáèëèçàöèÿ çäåñü òàêæå íàñòóïèò íå ïîçæå n – 1 øàãà è
áóäåò âûïîëíÿòüñÿ ðàâåíñòâî Ln n� ��1 1( ) ( )� �Rp . Òàêèì îáðàçîì, ýòè äâà âèäà
ïîëèíîìèàëüíîé äîñòèæèìîñòè ïî ñóùåñòâó ñîâïàäàþò ìåæäó ñîáîé.
Ëèíåéíûé àâòîìàò A V X f� ( , , ) íàä ïîëåì K íàçîâåì ñèëüíî-ñâÿçíûì, åñëè
äëÿ ëþáûõ äâóõ íåíóëåâûõ ñîñòîÿíèé s è t èç S íàéäåòñÿ ïîëèíîì p òàêîé, ÷òî
F s p t( , ) � . Îòìåòèì, ÷òî ëèíåéíûé ñèëüíî-ñâÿçíûé àâòîìàò ìîæåò áûòü ìîíîìè-
àëüíî íå ñâÿçíûì êàê àáñòðàêòíûé àâòîìàò [1]. Åñëè ïîëíûé ëèíåéíûé àâòîìàò
ñèëüíî-ñâÿçíûé, òî ñ òî÷êè çðåíèÿ àëãåáðû îí ÿâëÿåòñÿ ïðîñòûì (íåïðèâîäèìûì)
ìîäóëåì, ò.å. ìîäóëåì, íå ñîäåðæàùèì íåíóëåâûõ ïîäìîäóëåé [2].
Ïðîáëåìà ìîíîìèàëüíîé äîñòèæèìîñòè ñîñòîÿíèé â ëèíåéíûõ àâòîìàòàõ ìî-
æåò ðàññìàòðèâàòüñÿ êàê àëãîðèòìè÷åñêîé ïðîáëåìà, â êîòîðîé ïî çàäàííûì A , s è t
òðåáóåòñÿ ïðîâåðèòü ñóùåñòâîâàíèå ñëîâà w X� � òàêîãî, ÷òî F s w t( , ) � . Ê ñîæàëå-
íèþ, íàä áåñêîíå÷íûìè ïîëÿìè ïðîáëåìà ìîíîìèàëüíîé äîñòèæèìîñòè ñîñòîÿíèé
â ëèíåéíûõ àâòîìàòàõ àëãîðèòìè÷åñêè íåðàçðåøèìà, íà÷èíàÿ ñ òðåõìåðíûõ àâòîìà-
òîâ [5]. Êðîìå òîãî, îíà ðàçðåøèìà äëÿ îäíîìåðíûõ ëèíåéíûõ àâòîìàòîâ [6] è îò-
êðûòà â äâóìåðíîì ñëó÷àå.
4. ÀÔÔÈÍÍÛÅ ÀÂÒÎÌÀÒÛ
Àôôèííûå àâòîìàòû â ñèëó èõ âàæíîñòè îïðåäåëèì ÿâíûì îáðàçîì. Àôôèííûì
n-ìåðíûì àâòîìàòîì A íàä ïîëåì K íàçûâàåòñÿ ÷åòâåðêà îáúåêòîâ
A V X f g� ( , , , ) , ãäå V K n� — ëèíåéíîå n-ìåðíîå ïðîñòðàíñòâî ñîñòîÿíèé íàä
ïîëåì K , X a ak�{ , , }1 � — êîíå÷íûé âõîäíîé àëôàâèò, f — îòîáðàæåíèå âèäà
f X n K: ( , )�Mat , à g — îòîáðàæåíèå âèäà g X V: � . Ôóíêöèÿ ïåðåõîäîâ àô-
ôèííîãî àâòîìàòà îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
F x f x g x( , ) ( ) ( )� �� � , ��V, x X� . (10)
Íàïîìíèì, ÷òî àôôèííûì îòîáðàæåíèåì ëèíåéíîãî ïðîñòðàíñòâà íàçûâàåòñÿ ëè-
íåéíîå îòîáðàæåíèå, ñäâèíóòîå íà íåêîòîðûé âåêòîð [4], à àôôèííîå îòîáðàæåíèå ïå-
ðåâîäèò àôôèííûå ïîäïðîñòðàíñòâà ñíîâà â àôôèííûå ïîäïðîñòðàíñòâà. Êðîìå òîãî,
àôôèííîå îòîáðàæåíèå íà ïðîñòðàíñòâåV áóäåò ëèíåéíûì íà àôôèííûõ êîìáèíàöèÿõ
ñîñòîÿíèé c cm m1 1� �� �� , ò.å. êîìáèíàöèÿõ, ó êîòîðûõ c cm1 1 �� . Èç ôîð-
ìóëû (10) âèäíî, ÷òî ôóíêöèÿ ïåðåõîäîâ àôôèííîãî àâòîìàòà ïðè ôèêñèðîâàííîì
x X� áóäåò àôôèííûì îòîáðàæåíèåì ïðîñòðàíñòâàV è, ñëåäîâàòåëüíî, äëÿ àôôèííûõ
êîìáèíàöèé ñîñòîÿíèé âûïîëíÿåòñÿ óñëîâèå
F c c x c F x c F xm m m m( , ) ( , ) ( , )1 1 1 1� � � � �� � � �� � .
Çàìåòèì, ÷òî ëèíåéíûå àâòîìàòû ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì àôôèííûõ, êîãäà
g x( ) � 0 äëÿ âñåõ x X� . Ñ äðóãîé ñòîðîíû, ñëåäóþùåå ïðåäëîæåíèå ïîêàçûâàåò,
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
÷òî ïîíÿòèå àôôèííîãî àâòîìàòà ñîãëàñîâàíî ñ ïîíÿòèåì àôôèííîãî ïîäàâòîìàòà
ëèíåéíîãî àâòîìàòà.
Òåîðåìà 3. Êàæäûé àôôèííûé n-ìåðíûé àâòîìàò èçîìîðôíî âêëàäûâàåòñÿ â
( )n 1 -ìåðíûé ëèíåéíûé àâòîìàò.
Äîêàçàòåëüñòâî. Ïóñòü A V X f g� ( , , , ) — àôôèííûé n-ìåðíûé àâòîìàò íàä
ïîëåì K , òîãäà â ïðîñòðàíñòâå K n 1 âûäåëèì àôôèííóþ ãèïåðïëîñêîñòü S �
� �{( , ) | }� �1 K n è îïðåäåëèì ôóíêöèþ f X n K1 1: ( , )� Mat ñëåäóþùèì îáðàçîì:
f x
f x
g x
n
1
0
1
( )
( )
( )
�
�
�
�
�
�
� ,
ãäå 0n — íóëåâîé âåêòîð-ñòîëáåö äëèíû n. Òîãäà áóäåì èìåòü ( , ) ( )� 1 1� �f x
� ( ( , ), )F x� 1 äëÿ âñåõ x X� , ãäå F x( , )� — ôóíêöèÿ ïåðåõîäîâ àôôèííîãî àâòî-
ìàòà. Ñëåäîâàòåëüíî, àâòîìàò A èçîìîðôåí ìóëüòèïëèêàòèâíîìó ïîäàâòîìàòó
ëèíåéíîãî àâòîìàòà ( , , )K X fn 1
1 .
Òåîðåìà äîêàçàíà.
 íåêîòîðûõ ïðèêëàäíûõ ñèòóàöèÿõ íåîáõîäèìà áîëåå øèðîêàÿ òðàêòîâêà àô-
ôèííîãî àâòîìàòà, êîãäà ôóíêöèè f è g ñìåùàþòñÿ íà íåêîòîðîå ïîñòîÿííîå çíà÷å-
íèå. ×òîáû íå óñëîæíÿòü ôîðìàëüíîå èçëîæåíèå, áóäåì ïðîñòî ñ÷èòàòü, ÷òî â íà-
øåì ðàñïîðÿæåíèè èìååòñÿ äîïîëíèòåëüíûé âõîä a0 , íà êîòîðîì îïðåäåëåíû
ôóíêöèè f è g è êîòîðûé íå âõîäèò âî âõîäíîé àëôàâèò, à èñïîëüçóåòñÿ òîëüêî äëÿ
ñìåùåíèÿ. Òîãäà íàøè àôôèííûå àâòîìàòû áóäóò îáîáùàòü êëàññè÷åñêèå ëèíåé-
íûå àâòîìàòû, â êîòîðûõ ôóíêöèÿ ïåðåõîäîâ èìååò âèä F u F u G( , )� �� � �0 0 , ãäå
u K X� ( ) — âõîäíîé âåêòîð, à F0 è G0 — ïîñòîÿííûå ìàòðèöû ðàçìåðíîñòè n n� è
k n� ñîîòâåòñòâåííî [7, 8]. Äåéñòâèòåëüíî, â íàøåì ñëó÷àå äîñòàòî÷íî ïðîäîëæèòü
ïî ëèíåéíîñòè ôóíêöèè f è g äëÿ âñåõ âåêòîðîâ a u0 , ãäå u K X� ( ), ïîëîæèâ
f a F( )0 0� , g a( )0 0� , f x( ) � 0 äëÿ âñåõ x X� . Òîãäà èç (10) ñëåäóåò, ÷òî
F a u F g u F u G( , ) ( )� � �0 0 0 0 � � � � � , ãäå g u u G( ) � � 0 . Òàêèì îáðàçîì, ïîëó÷àåò-
ñÿ êëàññè÷åñêèé ëèíåéíûé àâòîìàò, êîòîðûé ïðàâèëüíåå áûëî áû íàçâàòü êëàññè-
÷åñêèì àôôèííûì àâòîìàòîì.
Äàëåå ïðîäîëæèì ôóíêöèþ ïåðåõîäîâ àôôèííîãî àâòîìàòà íà âõîäíûå ñëîâà.
Ïóñòü w x x xm� 1 2� — âõîäíîå ñëîâî, x Xi � , 1� �i m, è ïóñòü � i i mw x x( ) � 1�
— i-é ñóôôèêñ ñëîâà w, 0 � �i m. Ïðåäïîëàãàåòñÿ, ÷òî � m w e( ) � , ãäå e — ïóñòîå
ñëîâî. Îïðåäåëèì òåïåðü ôóíêöèþ f íà âõîäíûõ ñëîâàõ ïî ôîðìóëå (1), ïîëîæèâ
f w f x f xm( ) ( ) ( )� � �1 � . Ñëåäóþùàÿ îáîáùàþùàÿ ôîðìóëà, êîòîðàÿ ëåãêî äîêàçû-
âàåòñÿ ïî èíäóêöèè, îïðåäåëÿåò ôóíêöèþ ïåðåõîäîâ äëÿ àôôèííûõ àâòîìàòîâ:
F w f w g x f wi i
i
m
( , ) ( ) ( ) ( ( ))� � �� � �
�
�
1
. (11)
Âåêòîð, ðàâíûé çíà÷åíèþ ñóììû â ïðàâîé ÷àñòè ýòîé ôîðìóëû, îáîçíà÷èì
g w( ), òîãäà ôîðìóëà (11) ïðèìåò áîëåå ëàêîíè÷íûé âèä:
F w f w g w( , ) ( ) ( )� �� � . (12)
Ïðîäîëæèì òåïåðü ôóíêöèþ ïåðåõîäîâ íà ïîëèíîìû. Ïóñòü p c w� � 1 1 �
� �c wm m — âõîäíîé ïîëèíîì, òîãäà ïî îïðåäåëåíèþ ïîëîæèì:
f p c f w c f wm m( ) ( ) ( )� 1 1 � , g p c g w c g wm m( ) ( ) ( )� 1 1 � . (13)
Ôóíêöèÿ ïåðåõîäîâ àôôèííîãî àâòîìàòà ïî-ïðåæíåìó îïðåäåëÿåòñÿ ïî ôîðìóëå
F p f p g p( , ) ( ) ( )� �� � . Òàêèì îáðàçîì, ôóíêöèÿ ïåðåõîäîâ áóäåò àôôèííîé ïî
ïåðâîìó àðãóìåíòó è ëèíåéíîé ïî âòîðîìó.
5. ÄÎÑÒÈÆÈÌÎÑÒÜ ÑÎÑÒÎßÍÈÉ Â ÀÔÔÈÍÍÛÕ ÀÂÒÎÌÀÒÀÕ
Ïóñòü A V X f g� ( , , , ) — n-ìåðíûé àôôèííûé àâòîìàò, òîãäà ìíîæåñòâà ìîíî-
ìèàëüíî äîñòèæèìûõ ñîñòîÿíèé RmA ( )� è Rmi ( )� îïðåäåëÿþòñÿ òàê æå, êàê è
äëÿ ëèíåéíûõ àâòîìàòîâ. Äàëåå, îáîçíà÷èì ÷åðåç Ka ( )X � ìíîæåñòâî àôôèí-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 15
íûõ ïîëèíîìîâ, ò.å. ïîëèíîìîâ, ó êîòîðûõ ñóììà êîýôôèöèåíòîâ ðàâíà åäèíè-
öå. Ìíîæåñòâà ïîëèíîìèàëüíîé äîñòèæèìîñòè îïðåäåëèì òàêæå ïî àíàëîãèè
ñ ëèíåéíûì ñëó÷àåì Rp KaA F p p X( ) { ( , ) | ( ) }� �� � � è Rp i F p d p i( ) { ( , ) | ( ) ,� �� �
p X� �Ka ( )}, i � 0.
Íåòðóäíî âèäåòü, ÷òî ìíîæåñòâà äîñòèæèìîñòè Rp i ( )� — àôôèííûå ïîäïðîñ-
òðàíñòâà, ïîñêîëüêó èç ñâîéñòâà (13) ñëåäóåò, ÷òî äëÿ àôôèííûõ ïîëèíîìîâ âûïîë-
íÿåòñÿ ñâîéñòâî (6). Çíà÷èò, Rp i ( )� — àôôèííàÿ îáîëî÷êà ìíîæåñòâà Rmi ( )� , ò.å.
Rp aff Rmi i( ) ( ( ))� �� . Íàïîìíèì, ÷òî àôôèííàÿ îáîëî÷êà — ýòî çàìûêàíèå ïîä-
ìíîæåñòâà äî íàèìåíüøåãî àôôèííîãî ïîäïðîñòðàíñòâà, ñîäåðæàùåãî ýòî ïîäìíî-
æåñòâî [4]. Òîãäà áóäåì èìåòü ñëåäóþùóþ âîçðàñòàþùóþ ïîñëåäîâàòåëüíîñòü
àôôèííûõ ïîäïðîñòðàíñòâ:
Rp Rp Rp0 1( ) ( ) ( )� � �
� �
� �n . (14)
Äëèíà ýòîãî ðÿäà äî ñòàáèëèçàöèè ìîæåò áûòü íà åäèíèöó áîëüøå, ÷åì äëèíà
ðÿäà (8), ïîñêîëüêó Rp0 ( ) { }� �� — íóëüìåðíîå àôôèííîå ïîäïðîñòðàíñòâî. Íàïîì-
íèì, ÷òî ðàçìåðíîñòü àôôèííîãî ïîäïðîñòðàíñòâà îïðåäåëÿåòñÿ ðàçìåðíîñòüþ ñî-
îòâåòñòâóþùåãî íàïðàâëÿþùåãî ëèíåéíîãî ïîäïðîñòðàíñòâà [4]. Îòñþäà ïîëó÷àåì
àíàëîã òåîðåìû 2.
Òåîðåìà 4. Åñëè â n-ìåðíîì àôôèííîì àâòîìàòå A âûïîëíÿåòñÿ óñëîâèå
t sA�Rp ( ), òî ñóùåñòâóåò àôôèííûé ïîëèíîì p ñòåïåíè, íå áîëüøåé n, òàêîé ÷òî
F s p t( , ) � .
Êàê óæå îãîâàðèâàëîñü, ïðîáëåìà ìîíîìèàëüíîé äîñòèæèìîñòè ñîñòîÿíèé
â ëèíåéíûõ è àôôèííûõ àâòîìàòàõ àëãîðèòìè÷åñêè íåðàçðåøèìà. Ïîêàæåì, íà-
ïðèìåð, àëãîðèòìè÷åñêóþ íåðàçðåøèìîñòü ïðîáëåìû ìîíîìèàëüíîé äîñòèæè-
ìîñòè ñîñòîÿíèé â äâóìåðíûõ àôôèííûõ àâòîìàòàõ íàä ïîëåì ðàöèîíàëüíûõ ÷è-
ñåë, ÷òî áóäåò íåêîòîðûì óñèëåíèåì ðåçóëüòàòà Ïàòåðñîíà [5]. Èçëîæèì ñíà÷àëà
èäåþ äîêàçàòåëüñòâà. Âî-ïåðâûõ, â êà÷åñòâå èçâåñòíîé àëãîðèòìè÷åñêè íåðàç-
ðåøèìîé ïðîáëåìû, ê êîòîðîé áóäåì ñâîäèòü íàøó ïðîáëåìó, âîçüìåì õîðîøî
èçâåñòíóþ ïðîáëåìó ñîîòâåòñòâèÿ Ïîñòà (ÏÑÏ), â êîòîðîé äëÿ äâóõ ñëîâàðíûõ
ãîìîìîðôèçìîâ (ìîðôèçìîâ) h X Y1: � �� è h X Y2 : ,� �� ãäå Y — åùå îäèí êî-
íå÷íûé àëôàâèò, òðåáóåòñÿ îïðåäåëèòü ñóùåñòâîâàíèå íåïóñòîãî ñëîâà w òàêîãî,
÷òî h w h w1 2( ) ( )� [9].
Âî-âòîðûõ, îäíîìåðíûå àôôèííûå àâòîìàòû ìîãóò âû÷èñëÿòü ñëîâàðíûå ìîð-
ôèçìû, åñëè âìåñòî êîíêàòåíàöèè ñòðîê èñïîëüçîâàòü óìíîæåíèå ÷èñåë, êîòîðîå
ôàêòè÷åñêè çàìåíÿåòñÿ ñäâèãàìè. Äåéñòâèòåëüíî, áåç îãðàíè÷åíèÿ îáùíîñòè ìîæ-
íî ñ÷èòàòü, ÷òî Y
{ , , , }1 2 9� , òîãäà ñòðîêè â ýòîì àëôàâèòå áóäåì ðàññìàòðèâàòü
êàê îáû÷íûå äåñÿòè÷íûå ÷èñëà è ñëîâàðíûé ìîðôèçì h X Y: � �� ìîæíî âû÷èñ-
ëèòü ñ ïîìîùüþ ñëåäóþùåãî àôôèííîãî àâòîìàòà: F x h xl h x( , ) ( )( ( ))� �� � 10 . Ïîä
«âû÷èñëåíèåì» çäåñü ïîíèìàåòñÿ òî, ÷òî àâòîìàò, íàõîäÿñü âíà÷àëå â íóëåâîì ñîñòî-
ÿíèè, ïîñëå îáðàáîòêè ñëîâà w îêàæåòñÿ â ñîñòîÿíèè h w( ). Â-òðåòüèõ, äâóìåðíûé
àôôèííûé àâòîìàò, êîòîðûé ÿâëÿåòñÿ ïðÿìûì ïðîèçâåäåíèåì äâóõ îäíîìåðíûõ àâ-
òîìàòîâ, ìîæåò ìîäåëèðîâàòü îäíîâðåìåííóþ ðàáîòó ýòèõ àâòîìàòîâ è îäíîâðåìåí-
íî âû÷èñëÿòü äâà ìîðôèçìà. Ýòîãî â ïðèíöèïå äîñòàòî÷íî äëÿ íåðàçðåøèìîñòè,
à îñòàâøèåñÿ òåõíè÷åñêèå äåòàëè ïðèâîäÿòñÿ â ñëåäóþùåé òåîðåìå.
Òåîðåìà 5. Ïðîáëåìà ìîíîìèàëüíîé äîñòèæèìîñòè ñîñòîÿíèé â äâóìåðíûõ
àôôèííûõ àâòîìàòàõ íàä ïîëåì ðàöèîíàëüíûõ ÷èñåë àëãîðèòìè÷åñêè íåðàçðåøèìà.
Äîêàçàòåëüñòâî. Ïóñòü çàäàíû ìîðôèçìû h X Y1: ,� �� h X Y2 : ,� �� ãäå
Y �{ , }2 3 . Êàê èçâåñòíî, äâóõ áóêâ äîñòàòî÷íî äëÿ íåðàçðåøèìîñòè ïðîáëåìû Ïîñ-
òà, à åäèíèöà íàì ïîíàäîáèòñÿ äëÿ äðóãèõ öåëåé. Äëÿ êàæäîãî âõîäíîãî ñèìâîëà
x X� äîáàâèì âî âõîäíîé àëôàâèò àâòîìàòà «çåðêàëüíûé» ñèìâîë x è, êðîìå òîãî,
åùå îäèí «òåðìèíàëüíûé» ñèìâîë x0 . Ðàññìîòðèì äâóìåðíûé àôôèííûé àâòîìàò
A Q X X x f g� � �( , { }, , )2
0 , ãäå Q — ïîëå ðàöèîíàëüíûõ ÷èñåë, êîòîðûé îïðåäåëÿ-
åòñÿ ïî ìîðôèçìàì h1, h2 ñëåäóþùèì îáðàçîì:
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
f x
l h x
l h x
( )
( ( ))
( ( ))
�
�
�
�
�
�
�
10 0
0 10
1
2
, f x
l h x
l h x
( )
( ( ))
( ( ))
�
�
�
�
�
�
�
10 0
0 10
1
2 1
, f x( ) ,0
1 1
1 1
�
�
�
�
�
�
�
�
� (15)
g x h x h x( ) ( ( ), ( ))� 1 2 , g x h x h x( ) ( ( ), ( ))� 1 21 , g x( ) ( , )0 0 0� .
Íà÷àëüíûì ñîñòîÿíèåì àâòîìàòà áóäåì ñ÷èòàòü âåêòîð ( , )1 0 , à ôèíàëüíûì —
íóëåâîå ñîñòîÿíèå ( , )0 0 . Ïóñòü L a b ac bc c Q( , ) {( , ) | }� � — ïðÿìàÿ, êîòîðàÿ ïðîõî-
äèò ÷åðåç íà÷àëî êîîðäèíàò è òî÷êó ( , )a b . Èç ôîðìóë (15) ÿñíî, ÷òî â íóëåâîå ñî-
ñòîÿíèå ìîæíî ïîïàñòü òîëüêî ñ ïîìîùüþ ñèìâîëà x0 , íàõîäÿñü íà ïðÿìîé L( , )1 1 .
 ëþáîì äðóãîì ñëó÷àå ïîä äåéñòâèåì ñèìâîëà x0 ìû ïîïàäàåì â íåíóëåâóþ òî÷êó
íà ïðÿìîé L( , )1 1� , èç êîòîðîé íóëåâîå ñîñòîÿíèå íåäîñòèæèìî.
Äàëåå, ïåðâûì âõîäíûì ñèìâîëîì äîëæåí áûòü îäèí èç ñèìâîëîâ x X� , ïî-
ñêîëüêó ïåðâàÿ êîìïîíåíòà ñîñòîÿíèÿ âñåãäà íà÷èíàåòñÿ ñ åäèíèöû. Ïîñëå ýòîãî
çåðêàëüíûõ ñèìâîëîâ áîëüøå áûòü íå äîëæíî, ïîñêîëüêó òîãäà âî âòîðîé êîìïî-
íåíòå ïîÿâèòñÿ âòîðàÿ åäèíèöà, â òî âðåìÿ êàê â ïåðâîé êîìïîíåíòå îíà îñòàíåòñÿ
òîëüêî îäíà. Òàêèì îáðàçîì, äëÿ ñëîâà xw, ãäå w X� � , èìååì F xw(( , ), )0 1 �
� ( ( ), ( ))1 11 2h xw h xw . Îòñþäà ïîëó÷àåì ñëåäóþùåå óñëîâèå:
F xwx h xw h xw(( , ), ) ( , ) ( ) ( )0 1 0 00 1 2� � � .
Çíà÷èò, ÏÑÏ ñâîäèòñÿ ê ïðîáëåìå äîñòèæèìîñòè è, ñëåäîâàòåëüíî, ïðîáëåìà äî-
ñòèæèìîñòè òàêæå íåðàçðåøèìà.
Òåîðåìà äîêàçàíà.
Òàêèì îáðàçîì, ñòàòóñ ïðîáëåìû ìîíîìèàëüíîé äîñòèæèìîñòè ñîñòîÿíèé â
àôôèííûõ àâòîìàòàõ îñòàåòñÿ îòêðûòûì òîëüêî äëÿ îäíîìåðíûõ àôôèííûõ àâòî-
ìàòîâ. Ïîïóòíî óïîìÿíåì î ïðîáëåìå ìîðòàëüíîñòè, êîòîðàÿ ñîñòîèò â òîì, ÷òîáû
ïî ëèíåéíîìó àâòîìàòó îïðåäåëèòü ñóùåñòâîâàíèå íóëåâîãî ñëîâà, ò.å. ñëîâà, êîòî-
ðîå ïåðåâîäèò âñå ñîñòîÿíèÿ â íóëåâîå ñîñòîÿíèå. Ñòàòóñ ïðîáëåìû ìîðòàëüíîñòè
îòêðûò òîëüêî äëÿ äâóìåðíûõ ëèíåéíûõ àâòîìàòîâ [6].
6. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ ÑÎÑÒÎßÍÈÉ
Îïðåäåëèì ñíà÷àëà àâòîìàòû ñ âûõîäîì. (Ïîëíûì) ëèíåéíûì àâòîìàòîì ñ âûõî-
äîì íàä ïîëåì K íàçûâàåòñÿ ïÿòåðêà îáúåêòîâ A V X Y f h� ( , , , , ) , ãäå ( , , )V X f —
ëèíåéíûé àâòîìàò áåç âûõîäà, Y b bl�{ , , }1 � — êîíå÷íîå ìíîæåñòâî âûõîäíûõ
ñèìâîëîâ è h — îòîáðàæåíèå, êîòîðîå êàæäîìó âõîäíîìó ñèìâîëó x ñîïîñòàâëÿ-
åò n l� ìàòðèöó ñ ýëåìåíòàìè èç K .
Îòîáðàæåíèå h îïðåäåëÿåò ôóíêöèþ âûõîäîâ H x h x( , ) ( )� �� � . Îòìåòèì, ÷òî
ýòà ôóíêöèÿ ïðèíèìàåò çíà÷åíèÿ â ëèíåéíîì ïðîñòðàíñòâå K Y( ) , ò.å. â ïðîñòðà-
íñòâå ôîðìàëüíûõ ëèíåéíûõ êîìáèíàöèé âûõîäíûõ ñèìâîëîâ ñ êîýôôèöèåíòàìè
èç K . Ôóíêöèÿ âûõîäîâ åñòåñòâåííûì îáðàçîì ïðîäîëæàåòñÿ íà âõîäíûå ñëîâà
(ìîíîìû) w x xm� 1� , à èìåííî:
H w H x H x H xm m( , ) ( , ) ( , ) ( , )� � � �� �1 1 2 1� , (16)
ãäå � �1 1, ,� m� — ñîñòîÿíèÿ, ÷åðåç êîòîðûå ïðîõîäèò àâòîìàò ïîä äåéñòâèåì
ñëîâà w. Ïðàâóþ ÷àñòü ðàâåíñòâà (16) ìîæíî ïîíèìàòü êàê ñëîâî â ïîòåíöèàëü-
íî áåñêîíå÷íîì àëôàâèòå K Y( ). Ôóíêöèþ âûõîäîâ ïðè íåîáõîäèìîñòè ìîæíî ïðî-
äîëæèòü íà âõîäíûå ïîëèíîìû, íî åå áóäåì ðàññìàòðèâàòü êàê ôóíêöèþ âèäà
H V X K Y: ( )� �� � .
Îïðåäåëåíèå 4. Äâà ñîñòîÿíèÿ s è t ëèíåéíîãî àâòîìàòà A íàçûâàþòñÿ ýêâè-
âàëåíòíûìè (íåîòëè÷èìûìè), åñëè H s w H t w( , ) ( , )� äëÿ âñåõ w X� �.
Ýêâèâàëåíòíûå ñîñòîÿíèÿ îáîçíà÷èì s t~ . Çàìåòèì, ÷òî åñëè s t~ , òî
H s t w( – , ) � 0 äëÿ âñåõ w X� �, äðóãèìè ñëîâàìè, ñîñòîÿíèå s t– íåîòëè÷èìî îò íó-
ëåâîãî ñîñòîÿíèÿ. Ýòî î÷åâèäíîå çàìå÷àíèå, êàê íè ñòðàííî, íàìíîãî îáëåã÷àåò âñå
ïîñëåäóþùèå äîêàçàòåëüñòâà.
Ïóñòü A V X Y f h� ( , , , , ) — n-ìåðíûé ëèíåéíûé àâòîìàò, îáîçíà÷èì Kr h w( )
ïîäïðîñòðàíñòâî ñîñòîÿíèé, êîòîðûå íåîòëè÷èìû îò íóëÿ, ñëîâîì w. Çàìåòèì, ÷òî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 17
â ñèëó ëèíåéíîñòè ôóíêöèÿ âûõîäîâ â íóëåâîì ñîñòîÿíèè äîëæíà áûòü òîæäåñ-
òâåííî ðàâíà íóëþ. Äàëåå, ïóñòü Vi — ïîäïðîñòðàíñòâî ñîñòîÿíèé, êîòîðûå íåîò-
ëè÷èìû îò íóëÿ ñëîâàìè (ìîíîìàìè) äëèíû i, òîãäà ïîëó÷àåì ñëåäóþùóþ óáûâàþ-
ùóþ öåïî÷êó âêëþ÷åíèé:
V V V Vn� � � � �0 1 0� { }. (17)
Ñòðîãèå íåðàâåíñòâà â öåïî÷êå (17) ìîãóò ïðîäîëæàòüñÿ íå äàëåå n-ãî ìåñòà,
ñëåäîâàòåëüíî, íàéäåòñÿ òàêîå ÷èñëî i, 0 � �i n, ÷òî V Vi i� 1. Ïîñëå ýòîãî öåïî÷-
êà (17) äîëæíà ñòàáèëèçèðîâàòüñÿ, ïîñêîëüêó F V x Vi i( , )
äëÿ ëþáîãî x X� .
Òàêèì îáðàçîì, ïîäïðîñòðàíñòâî Vn áóäåò ïîäàâòîìàòîì (ïîäìîäóëåì), êîòî-
ðûé îáîçíà÷èì E, òîãäà â E ïîïàäóò ñîñòîÿíèÿ, ýêâèâàëåíòíûå íóëþ. Ëèíåéíûé àâ-
òîìàò áóäåò ïðèâåäåííûì, ò.å. íå áóäåò èìåòü ýêâèâàëåíòíûõ ñîñòîÿíèé, åñëè
E �{ }0 . Åñëè ñ÷èòàòü E ïîäìîäóëåì, òî ïðèâåäåíèå àâòîìàòà ñâîäèòñÿ ê ñòàíäàðò-
íîé ïðîöåäóðå ïîñòðîåíèÿ ôàêòîð-ìîäóëÿ V E/ ïî ïîäìîäóëþ E . Èç (17) ïîëó÷àåì
ñëåäóþùåå ïðåäëîæåíèå [1].
Òåîðåìà 6 (Ìó÷íèê). Åñëè äâà ñîñòîÿíèÿ íåýêâèâàëåíòíû â n-ìåðíîì ëèíåé-
íîì àâòîìàòå, òî èõ ìîæíî ðàçëè÷èòü ñëîâîì äëèíû n.
Èçâåñòíàÿ òåîðåìà Ìóðà äëÿ êîíå÷íûõ àâòîìàòîâ [10] ñëåäóåò èç òåîðåìû 6.
Äåéñòâèòåëüíî, åñëè äîïîëíèòü ñòàíäàðòíîå ëèíåéíîå ðàñøèðåíèå K A( ) êîíå÷íîãî
àâòîìàòà A ôóíêöèåé âûõîäà, òî ïî ñëåäñòâèþ 1 è òåîðåìå 6 äëÿ íåýêâèâàëåíòíûõ
ñîñòîÿíèé s è t ñîñòîÿíèå s t– áóäåò îòëè÷èìûì îò íóëÿ â ïîäàâòîìàòå ïàð ñëîâîì
äëèíû n – 1. Îòñþäà ïîëó÷àåì ñëåäóþùåå óòâåðæäåíèå.
Ñëåäñòâèå 3 (Ìóð). Åñëè äâà ñîñòîÿíèÿ íåýêâèâàëåíòíû â êîíå÷íîì àâòîìàòå
ñ n ñîñòîÿíèÿìè, òî èõ ìîæíî ðàçëè÷èòü ñëîâîì äëèíû n – 1.
Àíàëîãè÷íûì îáðàçîì èç òåîðåìû 6, ïîëüçóÿñü ñëåäñòâèåì 2, ìîæíî âûâåñòè
òåîðåìó Êàðëàéëà äëÿ âåðîÿòíîñòíûõ àâòîìàòîâ [11].
Ñëåäñòâèå 4 (Êàðëàéë). Åñëè äâà ñîñòîÿíèÿ (ðàñïðåäåëåíèÿ âåðîÿòíîñòåé) íå-
ýêâèâàëåíòíû â âåðîÿòíîñòíîì àâòîìàòå ñ n ñîñòîÿíèÿìè, òî èõ ìîæíî ðàçëè÷èòü
ñëîâîì äëèíû n – 1.
Îòìåòèì, ÷òî äî ñòàáèëèçàöèè ðàçìåðíîñòü ïîäïðîñòðàíñòâ ðÿäà (17) äîëæíà
óáûâàòü, îòêóäà ïîëó÷àåì ñëåäóþùèå óòâåðæäåíèÿ.
Ñëåäñòâèå 5. Äëÿ âñåõ ïîäïðîñòðàíñòâ Vi ðÿäà (17) òàêèõ, ÷òî V Ei � , âûïîë-
íÿåòñÿ óñëîâèå dim( )V n ii � � .
Ñëåäñòâèå 6. Åñëè U E� , òî U Vn d� � 1, ãäå d U�dim( ).
Äåéñòâèòåëüíî, åñëè ïðåäïîëîæèòü, ÷òî U Vn d
� 1, òî èç ñëåäñòâèÿ 5 ïîëó÷à-
åì ïðîòèâîðå÷èå d U V dn d� � � �� dim( ) dim( )1 1.
7. ÓÑÒÀÍÎÂÎ×ÍÛÅ È ÄÈÀÃÍÎÑÒÈ×ÅÑÊÈÅ ÑËÎÂÀ
Ðàññìîòðèì óñòàíîâî÷íûå è äèàãíîñòè÷åñêèå ýêñïåðèìåíòû ñ ëèíåéíûìè àâòî-
ìàòàìè. Ïóñòü çàäàí ïîëíûé ëèíåéíûé àâòîìàò A V X Y f h� ( , , , , ) , òîãäà ñëîâî
w X� � íàçûâàåòñÿ óñòàíîâî÷íûì, åñëè îíî ïîçâîëÿåò ñ òî÷íîñòüþ äî ýêâèâà-
ëåíòíîñòè óñòàíîâèòü çàêëþ÷èòåëüíîå ñîñòîÿíèå àâòîìàòà ïî ðåàêöèè íà ýòî
ñëîâî, ò.å. âûïîëíÿåòñÿ ñëåäóþùåå óñëîâèå äëÿ âñåõ ñîñòîÿíèé s è t :
H s w H t w F s w F t w( , ) ( , ) ( , ) ~ ( , )� � .
Äëÿ ëèíåéíûõ àâòîìàòîâ ýòî óñëîâèå çàïèøåì ñëåäóþùèì îáðàçîì:
F h w w E( ( ), )Kr
.
 äàëüíåéøåì íàì ïîíàäîáèòñÿ ðàâåíñòâî, êîòîðîå ìîæíî ïðîâåðèòü íåïîñðå-
äñòâåííî äëÿ ëþáûõ ñëîâ w1 è w2 :
F h w w w w F F h w w h w w( ( ), ) ( ( ( ), ) ( ), )Kr Kr Kr1 2 1 2 1 1 2 2�
. (18)
Òåîðåìà 7 (Ìó÷íèê). Äëÿ âñÿêîãî ëèíåéíîãî n-ìåðíîãî àâòîìàòà ñóùåñòâóåò
óñòàíîâî÷íîå ñëîâî äëèíû, íå áîëüøåé n n( ) / 1 2.
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
Äîêàçàòåëüñòâî. Ïóñòü A V X Y f h� ( , , , , ) — ëèíåéíûé n-ìåðíûé àâòîìàò,
òîãäà ïîëîæèì U V1 � , w e0 � , d U1 1�dim( ), i �1, è áóäåì äåéñòâîâàòü ñëåäóþ-
ùèì îáðàçîì. Åñëè U Ei
, òî ïîñòðîåíèå çàêàí÷èâàåòñÿ è åãî ðåçóëüòàòîì áó-
äåò ñëîâî wi�1.  ïðîòèâíîì ñëó÷àå ñîãëàñíî ñëåäñòâèþ 6 íàõîäèì ñëîâî yi äëè-
íû, íå áîëüøåé n di� 1, òàêîå ÷òî U h yi i� Kr ( ). Ïîëîæèì, w w yi i i� �1 , Ui �1
� F h w wi i( ( ), )Kr , d Ui i �1 1dim( ) è çàìåòèì, ÷òî èç ñâîéñòâ (4) è (18) áóäåì
èìåòü d U h y di i i i �
�1 dim( ( ))Kr . Ïîñëå ýòîãî ïîâòîðÿåì öèêë, óâåëè÷èâàÿ èí-
äåêñ i íà åäèíèöó, è ò.ä.
 ðåçóëüòàòå ïîñòðîåíèÿ ïîëó÷èì óñòàíîâî÷íîå ñëîâî w y ym m� 1� , ãäå
l y n di i( ) � � 1, 1� �i m , è ðàçìåðíîñòè ïîäïðîñòðàíñòâ di îáðàçóþò óáûâàþùóþ
ïîñëåäîâàòåëüíîñòü n d d dm� � � � �1 2 1� . Îòñþäà ïîëó÷àåì ñëåäóþùóþ îöåíêó
íà äëèíó ñëîâà wm :
l w l y y n d n i
n n
m m i
i
m
i
n
( ) ( ) ( ) ( )
( )
� � � � � �
� �
� �1
1 1
1 1
1
2
� .
Òàêèì îáðàçîì, òåîðåìà äîêàçàíà.
Èç ýòîé òåîðåìû íåïîñðåäñòâåííî âûòåêàåò èçâåñòíûé ðåçóëüòàò Õèááàðäà äëÿ êî-
íå÷íûõ àâòîìàòîâ [12], îäíàêî ïðè ýòîì íàäî ó÷èòûâàòü, ÷òî ëèíåéíîå ðàñøèðåíèå ïðè-
âåäåííîãî êîíå÷íîãî àâòîìàòà ìîæåò íå áûòü ïðèâåäåííûì êàê ëèíåéíûé àâòîìàò.
Ñëîâî w X� � íàçûâàåòñÿ äèàãíîñòè÷åñêèì äëÿ ëèíåéíîãî àâòîìàòà A , åñëè ïî
ðåàêöèè íà ýòî ñëîâî ìîæíî îïðåäåëèòü íà÷àëüíîå ñîñòîÿíèå àâòîìàòà, ò.å. âûïîë-
íÿåòñÿ ñëåäóþùåå óñëîâèå äëÿ âñåõ ñîñòîÿíèé s è t :
H s w H t w s t( , ) ( , )� � � .
Äëÿ ëèíåéíûõ àâòîìàòîâ ýòî óñëîâèå ýêâèâàëåíòíî óñëîâèþ Kr h w( ) � 0.
 îòëè÷èå îò óñòàíîâî÷íûõ ñëîâ, â àâòîìàòå ìîæåò íå áûòü äèàãíîñòè÷åñêèõ
ñëîâ, ïîýòîìó àâòîìàò íàçûâàåòñÿ äèàãíîñòèðóåìûì, åñëè ó íåãî åñòü äèàãíîñòè-
÷åñêîå ñëîâî. Âîçìîæíîå îòñóòñòâèå äèàãíîñòè÷åñêèõ ñëîâ â ïðèâåäåííîì êîíå÷-
íîì àâòîìàòå Ìóð íàçâàë äèñêðåòíûì àíàëîãîì ïðèíöèïà íåîïðåäåëåííîñòè Ãåé-
çåíáåðãà [10, 11]. Ñëåäóþùèé ðåçóëüòàò äîêàçàí â [13].
Òåîðåìà 8. Â äèàãíîñòèðóåìîì ëèíåéíîì n-ìåðíîì àâòîìàòå ñóùåñòâóåò äè-
àãíîñòè÷åñêîå ñëîâî äëèíû, íå áîëüøåé n n( ) / 1 2.
Äîêàçàòåëüñòâî ýòîé òåîðåìû ïðîâîäèòñÿ ñòàíäàðòíûì ðåäóêöèîííûì ìåòî-
äîì, êîòîðûé îïèñàí â ïðåäûäóùåé òåîðåìå. Åäèíñòâåííîå îòëè÷èå ñîñòîèò â òîì,
÷òî äëÿ ðåäóêöèè â ýòîé òåîðåìå íóæíî èñïîëüçîâàòü äîïóñòèìûå ñëîâà, ò.å. ñëîâà,
äëÿ êîòîðûõ âûïîëíÿåòñÿ óñëîâèå Kr Krf w h w( ) ( )
� 0.
Ìîæåò ïîêàçàòüñÿ, ÷òî òåîðåìà 8 ïðîòèâîðå÷èò èçâåñòíûì ðåçóëüòàòàì îá ýêñ-
ïîíåíöèàëüíîé äëèíå äèàãíîñòè÷åñêèõ ñëîâ äëÿ êîíå÷íûõ àâòîìàòîâ [14]. Íî äåëî
â òîì, ÷òî ëèíåéíîå ðàñøèðåíèå äèàãíîñòèðóåìîãî êîíå÷íîãî àâòîìàòà ìîæåò íå
áûòü äèàãíîñòèðóåìûì êàê ëèíåéíûé àâòîìàò, ïîýòîìó íàïðÿìóþ òåîðåìó 8 íåëü-
çÿ ïðèìåíÿòü ê êîíå÷íûì àâòîìàòàì.
8. ÏÐÈÌÅÍÅÍÈß Â ÌÀÒÅÌÀÒÈ×ÅÑÊÎÉ ÝÊÎÍÎÌÈÊÅ
Èçâåñòíî, ÷òî â ýêîíîìèêå øèðîêî ïðèìåíÿþòñÿ ëèíåéíûå ìàòåìàòè÷åñêèå ìî-
äåëè. Îäíàêî ìíîãèå èç íèõ íîñÿò ñòàöèîíàðíûé õàðàêòåð, ÷òî, êîíå÷íî, îãðàíè-
÷èâàåò èõ ïðàêòè÷åñêóþ öåííîñòü. Êàê ïðàâèëî, íå óêàçûâàåòñÿ, êàê ñîîòíîñÿòñÿ
ìåæäó ñîáîé ïåðåìåííûå ñîñòîÿíèÿ â ðàçëè÷íûå ìîìåíòû âðåìåíè. Ïîïûòêà æå
ââåñòè «äèíàìèêó» â ýòè ìîäåëè ôàêòè÷åñêè ïðèâîäèò ê ïîÿâëåíèþ äèñêðåòíûõ
ëèíåéíûõ ñèñòåì è ëèíåéíûõ àâòîìàòîâ.
Ïîêàæåì ýòî íà ïðèìåðå èçâåñòíîé òðàíñïîðòíîé çàäà÷è [15]. Ïóñòü èìååòñÿ
m èñòî÷íèêîâ, ïðîèçâîäÿùèõ íåêîòîðóþ ïðîäóêöèþ, êîòîðàÿ ïîòðåáëÿåòñÿ n êëè-
åíòàìè. Îáúåì ïðîèçâîäñòâà â i-ì èñòî÷íèêå â åäèíèöó âðåìåíè ðàâåí ai , 1� �i m,
à îáúåì ïîòðåáëåíèÿ j-ì êëèåíòîì â åäèíèöó âðåìåíè ðàâåí b j , 1� �j n. Èçâåñòíû
ñòîèìîñòè cij ïåðåâîçêè åäèíèöû ïðîäóêöèè èç i-ãî ïóíêòà â j-é, êîòîðûå õàðàê-
òåðèçóþòñÿ ìàòðèöåé C cij�{ }. Òðåáóåòñÿ ñîñòàâèòü ïëàí ïåðåâîçîêU uij� �{ }0 òà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 19
êèì îáðàçîì, ÷òîáû ìèíèìèçèðîâàòü òðàíñïîðòíûå èçäåðæêè ïðè ñëåäóþùèõ
óñëîâèÿõ:
u aij i
j
n
�
�
�
1
, 1� �i m, u bij j
i
m
�
�
�
1
, 1� �j n. (19)
Òðàíñïîðòíûå èçäåðæêè õàðàêòåðèçóþòñÿ âåëè÷èíîé � � ��C U c u
i j
ij ij,
,
.
Ïåðåâåäåì òðàíñïîðòíóþ çàäà÷ó íà ÿçûê àôôèííûõ àâòîìàòîâ. Ïóñòü R —
ïîëå âåùåñòâåííûõ ÷èñåë, òîãäà ïîëîæèì V R m n� è áóäåì ñ÷èòàòü íà÷àëüíûì
ñîñòîÿíèåì àâòîìàòà åäèíè÷íîå ñîñòîÿíèå e � ( , , )1 1� . Ïîëîæèì X �
� � � � �{ | , }e i m j nij 1 1 , ãäå eij — ýëåìåíòàðíàÿ ìàòðèöà, ó êîòîðîé íà ìåñòå ( , )i j
ðàñïîëîæåíà åäèíèöà, à íà îñòàëüíûõ ìåñòàõ — íóëè. Òîãäà X áóäåò ñòàíäàðò-
íûì áàçèñîì ïðîñòðàíñòâà m n� ìàòðèö è ïëàí ïåðåâîçîê U uij�{ } ìîæåò ðàññìàò-
ðèâàòüñÿ êàê îáîáùåííûé âõîä àâòîìàòà, ò.å. êàê ýëåìåíò ëèíåéíîãî ïðîñòðàíñò-
âà R X( ) . Äàëåå, ïóñòü d a b� �( ) — âåêòîð, ñîñòîÿùèé èç âåêòîðà
a a am� ( , , )1 � , ê êîòîðîìó ïðèïèñàí âåêòîð � � � �b b bn( , , )1 � . Íàêîíåö, ïîëîæèì
f U U U( ) ( )� � T , ãäå U T — òðàíñïîíèðîâàííàÿ äëÿ U ìàòðèöà, à ñèìâîë ñóììû
îçíà÷àåò ïðÿìóþ ñóììó ìàòðèö. Î÷åâèäíî, ÷òî f áóäåò ëèíåéíûì îòîáðàæåíèåì,
êîòîðîå ïåðåâîäèò m n� ìàòðèöû â êâàäðàòíûå ( ) ( )m n m n � ìàòðèöû. Òîãäà
óñëîâèÿ (19) ìîæíî çàïèñàòü òàê:
e f U d� �( ) 0. (20)
Òàêèì îáðàçîì, ïîëó÷åí àôôèííûé àâòîìàò A V X f g� ( , , , ), ãäå g a d( )0 � è
g U( ) � 0 äëÿ âñåõ U R X� ( ). Òðåáóåòñÿ íàéòè ïëàí ïåðåâîçîê U � 0 (óïðàâëÿþùèé
âåêòîð), êîòîðûé çà åäèíèöó âðåìåíè ïåðåâîäèò àâòîìàò íàèáîëåå ýêîíîìíûì ñïî-
ñîáîì èç åäèíè÷íîãî ñîñòîÿíèÿ â íóëåâîå. Ýêîíîìíîñòü ïåðåõîäà îïðåäåëÿåòñÿ
ñêàëÿðíûì ïðîèçâåäåíèåì � �C U, , ãäå m n� ìàòðèöû C è U ðàññìàòðèâàþòñÿ êàê
âåêòîðû. Åñëè ðàâåíñòâî (20) óìíîæèòü ñïðàâà íà åäèíè÷íûé âåêòîð-ñòîëáåö eT,
òî ïîëó÷èì óñëîâèå d e� �T 0, êîòîðîå, êàê èçâåñòíî, ÿâëÿåòñÿ íåîáõîäèìûì è äîñ-
òàòî÷íûì äëÿ ðàçðåøèìîñòè òðàíñïîðòíîé çàäà÷è â çàìêíóòîé ôîðìå. Êîíå÷íî, òà-
êàÿ ôîðìóëèðîâêà íå äàåò ðåøåíèÿ èñõîäíîé îïòèìèçàöèîííîé çàäà÷è, íî ïîçâîëÿ-
åò ëåãêî èçìåíÿòü ìîäåëü, ïðèäàâàÿ åé íåîáõîäèìóþ ãèáêîñòü è äèíàìèêó. Âî-ïåð-
âûõ, ìîæíî ïåðåéòè îò ïîëíîãî äâóäîëüíîãî ãðàôà ïåðåâîçîê, êîòîðûé íåÿâíî
ôèãóðèðóåò â òðàíñïîðòíîé çàäà÷å, ê ïðîèçâîëüíûì òðàíñïîðòíûì ñåòÿì (òðàíçèò-
íàÿ çàäà÷à). Ïóñòü ãðàô ïåðåâîçîê èìååò m îðèåíòèðîâàííûõ äóã, n âåðøèí è ìàò-
ðèöó èíöèäåíòíîñòè G (ðàçìåðíîñòè m n� ), â êîòîðîé â êàæäîé ñòðîêå íàõîäèòñÿ �1
íà ìåñòå, îòêóäà èñõîäèò äóãà, è 1 íà ìåñòå, êóäà îíà çàõîäèò, à íà îñòàëüíûõ
ïîçèöèÿõ ñòîÿò íóëè. Äàëåå, ïóñòü ïðîèçâîäñòâî è ïîòðåáëåíèå â êàæäîé âåðøè-
íå õàðàêòåðèçóåòñÿ âåêòîðîì d d dn� ( , , )1 � (ïîòðåáëåíèå — ýòî îòðèöàòåëüíîå
ïðîèçâîäñòâî), à âåêòîð u u um� ( , , )1 � õàðàêòåðèçóåò çàãðóçêó äóã ãðàôà. Òîãäà
óðàâíåíèå áàëàíñà ïðèîáðåòàåò ñëåäóþùèé âèä [16]:
u G d� � 0. (21)
Äðóãèìè ñëîâàìè, âûõîäíîé ïîòîê ïðîäóêòà èç êàæäîé âåðøèíû ðàâåí âõîäíî-
ìó ïîòîêó â ýòó âåðøèíó ïëþñ ïðîèçâîäñòâî. Òàêèì îáðàçîì, ïîëó÷àåì äðóãîé
àôôèííûé àâòîìàò, â êîòîðîì d — íà÷àëüíîå ñîñòîÿíèå, u — âõîäíîé âåêòîð,
f a I( )0 � , f u( ) � 0, g u u G( ) � � äëÿ âñåõ u R X� ( ) . Òðåáóåòñÿ íàéòè ïëàí ïåðåâî-
çîê u � 0, êîòîðûé ïåðåâîäèò àâòîìàò íàèáîëåå ýêîíîìíûì ñïîñîáîì èç íà÷àëü-
íîãî ñîñòîÿíèÿ â íóëåâîå. Ýêîíîìíîñòü õàðàêòåðèçóåòñÿ ñêàëÿðíûì ïðîèçâåäå-
íèåì � �c u, âåêòîðîâ c è u ðàçìåðíîñòè m. Åñëè ðàâåíñòâî (21) óìíîæèòü ñïðà-
âà íà åäèíè÷íûé âåêòîð-ñòîëáåö eT, òî â ñèëó ñïåöèôèêè ìàòðèöû G ñíîâà
ïîëó÷èì óñëîâèå d e� �T 0, êîòîðîå çäåñü áóäåò íåîáõîäèìûì, íî, âîîáùå ãîâî-
ðÿ, íåäîñòàòî÷íûì äëÿ ñóùåñòâîâàíèÿ ïëàíà.
Òåïåðü ðàññìîòðèì äèíàìè÷åñêóþ ìîäåëü. Ââåäåì âåêòîð ñîñòîÿíèÿ �( )k äëè-
íû n, îòðàæàþùèé çàïàñû ïðîäóêöèè â k-é ïåðèîä âðåìåíè ó ïðîèçâîäèòåëåé è ïî-
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
òðåáèòåëåé. Òîãäà óðîâåíü çàïàñîâ â ïåðèîä âðåìåíè k 1 îïðåäåëÿåòñÿ àëãåáðàè-
÷åñêîé ñóììîé ïîïîëíåíèÿ è èñòîùåíèÿ çàïàñîâ [17]:
� �( ) ( ) ( )k k u k G d � � 1 , 1� �k N . (22)
Ñíîâà ïîëó÷àåì àôôèííûé àâòîìàò A V X f g� ( , , , ) , ãäå f a I( )0 � , f u( ) � 0,
g u u G( ) � � , g a d( )0 � äëÿ âñåõ u R X� ( ) . Â ïðîöåññå èçìåíåíèÿ ñòðóêòóðû àâòî-
ìàòà óñëîæíÿåòñÿ è öåëåâàÿ ôóíêöèÿ, â êîòîðîé ìîæíî ó÷åñòü çàòðàòû íà õðàíå-
íèÿ ïðîäóêöèè, õàðàêòåðèçóåìûå âåêòîðîì y k( ), îòðàçèòü âëèÿíèå ñðåäû, ñäåëàâ
ïåðåìåííûì âåêòîð ñòîèìîñòåé c k( ), è ò.ä. Êðîìå òîãî, öåëåâóþ ôóíêöèþ òå-
ïåðü ìîæíî âû÷èñëÿòü íà âñåì ïåðèîäå ìîäåëèðîâàíèÿ:
J y k k c k u k
k
N
� � �
�
� ( ( ) ( ) ( ) ( ))�
1
.
Òî÷êîé çäåñü îáîçíà÷åíî ñêàëÿðíîå ïðîèçâåäåíèå âåêòîðîâ. Òàêèì îáðàçîì,
òðàíñïîðòíàÿ çàäà÷à ïðåâðàòèëàñü â çàäà÷ó óïðàâëåíèÿ çàïàñàìè íà ïðîèçâîëüíîì
ãðàôå. Íóæíî íàéòè äèíàìè÷åñêèé ïëàí ïåðåâîçîê (âõîäíîå ñëîâî p u u N� ( ) ( )1 � ),
êîòîðûé ìèíèìèçèðóåò çàïàñû íàèáîëåå ýêîíîìíûì ñïîñîáîì. Êîíå÷íî, ðåøåíèå
òåïåðü óñëîæíÿåòñÿ è åãî íóæíî èñêàòü â âèäå ìíîãîøàãîâîãî ïðîöåññà ïðèíÿòèÿ
ðåøåíèé â äóõå äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ P. Áåëëìàíà [18].
Òàêèì æå îáðàçîì ìîæíî ââåñòè äèíàìèêó â èçâåñòíóþ ìîäåëü Ëåîíòüåâà,
à òàêæå â ðÿä äðóãèõ ýêîíîìè÷åñêèõ ìîäåëåé [17].
ÇÀÊËÞ×ÅÍÈÅ
Êîíå÷íî, â îäíîé ðàáîòå òðóäíî ðàññìîòðåòü âñå ïðîáëåìû, îòíîñÿùèåñÿ ê ýòîé òå-
ìàòèêå. Îñòàëèñü íå ðàññìîòðåííûìè òàêèå âîïðîñû, êàê èññëåäîâàíèå óïðàâëÿå-
ìîñòè è íàáëþäàåìîñòè, ñòðóêòóðíàÿ è ñõåìíàÿ ðåàëèçàöèÿ ëèíåéíûõ àâòîìàòîâ
è ò.ä. Íî óæå èç èçëîæåííîãî ÿñíî, ÷òî îáîáùåííûå ëèíåéíûå àâòîìàòû ÿâëÿþòñÿ
«ìîñòîì» ìåæäó òåîðèåé àâòîìàòîâ è òåîðèåé äèñêðåòíûõ ëèíåéíûõ ñèñòåì è ïîý-
òîìó ïðèîáðåòàþò çíà÷åíèå â ðàìêàõ âñåé ìàòåìàòè÷åñêîé òåîðèè ñèñòåì.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ì ó ÷ í è ê À . Îáùèå ëèíåéíûå àâòîìàòû // Ïðîáëåìû êèáåðíåòèêè. — 1970. — 23. — Ñ. 171–208.
2. Ë å í ã Ñ . Àëãåáðà. — Ì.: Ìèð, 1968. — 564 ñ.
3. Ê à ë ì à í Ð . , Ô à ë á Ï . , À ð á è á Ì . Î÷åðêè ïî ìàòåìàòè÷åñêîé òåîðèè ñèñòåì. — Ì.: Ìèð,
1971. — 400 ñ.
4. Ê î ñ ò ð è ê è í À . , Ì à í è í Þ . Ëèíåéíàÿ àëãåáðà è ãåîìåòðèÿ. — Ì.: Íàóêà, 1986. — 303 ñ.
5. P a t e r s o n Ì . Unsolvability in 3 3� matrices. // Studies in Appl. Mathemat. — 1970. — 49. —
P. 105–107.
6. Ð û ñ ö î â È . Ê . Ïðîáëåìà ìîðòàëüíîñòè è àôôèííûå àâòîìàòû // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç.
— 2008. — ¹ 2. — Ñ. 24–29.
7. Ã è ë ë À . Ëèíåéíûå ïîñëåäîâàòåëüíîñòíûå ìàøèíû. — Ì.: Íàóêà, 1974. — 287 ñ.
8. Ç à ä å Ë . , Ä å ç î å ð × . Òåîðèÿ ëèíåéíûõ ñèñòåì. — Ì.: Íàóêà, 1970. — 703 ñ.
9. Ñ à ë î ì à à À . Æåì÷óæèíû òåîðèè ôîðìàëüíûõ ÿçûêîâ. — Ì.: Ìèð, 1986. — 159 ñ.
10. Ì ó ð Ý . Óìîçðèòåëüíûå ýêñïåðèìåíòû ñ ïîñëåäîâàòåëüíîñòíûìè ìàøèíàìè // Àâòîìàòû. — Ì.:
Èçä-âî èíîñòð. ëèò., 1956. — Ñ. 179–210.
11. Ê à ð ë à é ë Å . Ïðèâåäåííûå ôîðìû äëÿ ñòîõàñòè÷åñêèõ ïîñëåäîâàòåëüíîñòíûõ ìàøèí // Êèáåðíå-
òè÷åñêèé ñáîðíèê. — 1966. — ¹ 3. — Ñ. 101–111.
12. Õ è á á à ð ä Ò . Òî÷íûå âåðõíèå ãðàíèöû äëèí ìèíèìàëüíûõ ýêñïåðèìåíòîâ, îïðåäåëÿþùèõ çàêëþ-
÷èòåëüíîå ñîñòîÿíèå ïîñëåäîâàòåëüíîñòíûõ ìàøèí // Òàì æå. — 1966. — ¹ 2. — Ñ. 7–23.
13. Ð û ñ ö î â È . Îöåíêà äëèíû äèàãíîñòè÷åñêîãî ñëîâà äëÿ îáùèõ ëèíåéíûõ àâòîìàòîâ // Èññëåäîâà-
íèÿ ïî àëãåáðå. — 1974. — ¹ 4. — Ñ. 95–101.
14. Ð û ñ ö î â È . Îá àñèìïòîòè÷åñêîé îöåíêå äëèíû äèàãíîñòè÷åñêîãî ñëîâà äëÿ êîíå÷íîãî àâòîìàòà //
Êèáåðíåòèêà. — 1980. — ¹ 2. — Ñ. 31–35.
15. à î ë ü ø ò å é í Å . , Þ ä è í Ä . Çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ òðàíñïîðòíîãî òèïà. — Ì.:
Íàóêà, 1969. — 382 ñ.
16. Ð î ì à í î â ñ ê è é È . Àëãîðèòìû ðåøåíèÿ ýêñòðåìàëüíûõ çàäà÷. — Ì.: Íàóêà, 1977. — 352 ñ.
17. Í å ã î é ö ý Ê . Ïðèìåíåíèå òåîðèè ñèñòåì ê ïðîáëåìàì óïðàâëåíèÿ. — Ì.: Ìèð, 1981. — 180 ñ.
18. Á å ë ë ì à í Ð . , Ê à ë à á à Ð . Äèíàìè÷åñêîå ïðîãðàììèðîâàíèå è ñîâðåìåííàÿ òåîðèÿ óïðàâëåíèÿ.
— Ì.: Íàóêà, 1969. — 118 ñ.
Ïîñòóïèëà 22.07.2008
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 21
|