Эквивалентность двумерных многоленточных автоматов
Розглянуто проблему еквівалентності багатострічкових автоматів з багатовимірними стрічками, в яких рух головок монотонний у всіх напрямках (рух у зворотному напрямку неможливий). Доведено розв’язність спеціального випадку проблеми, коли розмірність стрічок менше або дорівнює двом....
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/71929 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Эквивалентность двумерных многоленточных автоматов / А.А. Григорян, С.К. Шукурян // Кибернетика и системный анализ. — 2008. — № 1. — С. 3-10. — Бібліогр.: 2 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-71929 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-719292014-12-21T23:36:15Z Эквивалентность двумерных многоленточных автоматов Григорян, А.А. Шукурян, С.К. Кибернетика Розглянуто проблему еквівалентності багатострічкових автоматів з багатовимірними стрічками, в яких рух головок монотонний у всіх напрямках (рух у зворотному напрямку неможливий). Доведено розв’язність спеціального випадку проблеми, коли розмірність стрічок менше або дорівнює двом. The paper addresses the equivalence of multitape automata with multi-dimensional tapes. Their heads move monotonically in all directions (no backward motion). The special case where the dimensions of tapes are less than or equal to 2 is proved to be solvable. 2008 Article Эквивалентность двумерных многоленточных автоматов / А.А. Григорян, С.К. Шукурян // Кибернетика и системный анализ. — 2008. — № 1. — С. 3-10. — Бібліогр.: 2 назв. — рос. http://dspace.nbuv.gov.ua/handle/123456789/71929 519.68 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 |
2008 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/71929 |
| citation_txt |
Эквивалентность двумерных многоленточных автоматов / А.А. Григорян, С.К. Шукурян // Кибернетика и системный анализ. — 2008. — № 1. — С. 3-10. — Бібліогр.: 2 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT grigorânaa ékvivalentnostʹdvumernyhmnogolentočnyhavtomatov AT šukurânsk ékvivalentnostʹdvumernyhmnogolentočnyhavtomatov |
| first_indexed |
2025-07-05T20:49:47Z |
| last_indexed |
2025-07-05T20:49:47Z |
| _version_ |
1836841526739599360 |
| fulltext |
À.À. ÃÐÈÃÎÐßÍ, Ñ.Ê. ØÓÊÓÐßÍ
ÓÄÊ 519.681 ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ ÄÂÓÌÅÐÍÛÕ
ÌÍÎÃÎËÅÍÒÎ×ÍÛÕ ÀÂÒÎÌÀÒÎÂ
Êëþ÷åâûå ñëîâà: àâòîìàòû, ìíîãîëåíòî÷íûé àâòîìàò, ìíîãîìåðíûé
àâòîìàò, ýêâèâàëåíòíîñòü.
Àâòîìàòû ñ ìíîãîìåðíûìè ëåíòàìè, â êîòîðûõ äâèæåíèå ãîëîâîê ìîíîòîííî
âî âñåõ íàïðàâëåíèÿõ (äâèæåíèå íàçàä íåâîçìîæíî), ââåäåíû â [1]. Áûëî ïî-
êàçàíî, ÷òî ïðîáëåìà ýêâèâàëåíòíîñòè â êëàññå ñõåì ïðîãðàìì íàä íåâûðîæ-
äåííûì áàçèñîì ðàíãà åäèíèöà ñâîäèòñÿ ê ýêâèâàëåíòíîñòè ìíîãîìåðíûõ
ìíîãîëåíòî÷íûõ àâòîìàòîâ.
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ ïðîáëåìà ýêâèâàëåíòíîñòè äâóìåðíûõ
ìíîãîëåíòî÷íûõ àâòîìàòîâ. Äîêàçûâàåòñÿ, ÷òî äàííàÿ ïðîáëåìà ñâîäèòñÿ ê
ýêâèâàëåíòíîñòè ìíîãîëåíòî÷íûõ àâòîìàòîâ [2].
Ïðèâåäåì íåêîòîðûå îïðåäåëåíèÿ èç [1], íåîáõîäèìûå äëÿ äàëüíåéøåãî
ðàññìîòðåíèÿ.
Ïóñòü r � 0 — öåëîå ÷èñëî, N � { }0 1, , . . . . Ìíîæåñòâî N r íàçûâàåòñÿ r-ìåð-
íîé ëåíòîé, ýëåìåíòû ìíîæåñòâà N r — r-êè âèäà ( , . . ., )a ar1 — íàçûâàþòñÿ
ÿ÷åéêàìè ëåíòû, à ÷èñëà a ar1, . . ., — êîîðäèíàòàìè ñîîòâåòñòâóþùåé ÿ÷åéêè.
ß÷åéêà ( , . . ., )0 0 ÿâëÿåòñÿ íà÷àëüíîé. Ïóñòü X — êîíå÷íûé àëôàâèò, òîãäà îòîáðà-
æåíèå N Xr � íàçûâàåòñÿ çàïîëíåíèåì r-ìåðíîé ëåíòû ñèìâîëàìè èç X .
Ìíîæåñòâî S n m n mk k� { }( , ), . . ., ( , )1 1 , ãäå n mi i, ( )1 � �i k — íàòóðàëüíûå
÷èñëà è n n i ji j� � � äëÿ ëþáûõ 1 � �i j k, , íàçûâàåòñÿ ñèãíàòóðîé
ìíîãîìåðíîãî ìíîãîëåíòî÷íîãî àâòîìàòà. Ñèãíàòóðà îïðåäåëÿåò êîëè÷åñòâî è
àðíîñòü ëåíò: åñëè ( , )n m S� , òî àâòîìàò ñ ñèãíàòóðîé S èìååò â òî÷íîñòè m
ëåíò ðàçìåðíîñòè n.
Ðàññìîòðèì ñëó÷àé, êîãäà ni � 2. Áóäåì ñ÷èòàòü, ÷òî S m� {( , ),1 1 ( , )2 2m }, ãäå
m m m m m1 2 1 20 0 0� � � �, , .
Ïóñòü A Q Q Q X q Qm F�
� � � �1 0. . . , , , , ,� � — äâóìåðíûé m-ëåíòî÷íûé
àâòîìàò ñ ñèãíàòóðîé S , ãäå Q — ìíîæåñòâî ñîñòîÿíèé, Qi ñîäåðæèò âñå òå è
òîëüêî òå ñîñòîÿíèÿ, â êîòîðûõ ñ÷èòûâàåòñÿ ëåíòà i Q Qi j,
� �, åñëè i j� , X —
âõîäíîé àëôàâèò, q0 — íà÷àëüíîå ñîñòîÿíèå, QF — ìíîæåñòâî çàêëþ÷èòåëüíûõ
ñîñòîÿíèé, � :Q X Q� � — ôóíêöèÿ ïåðåõîäîâ, � : ,Q X� � { }1 2 — ôóíêöèÿ
íàïðàâëåíèÿ äâèæåíèÿ.
Çàïîëíåííóþ ÷àñòü r-ìåðíîé ëåíòû, â êîòîðîé ñóììà êîîðäèíàò êàæäîé ÿ÷åéêè
ìåíüøå èëè ðàâíà n �1, íàçîâåì r-ìåðíûì ñëîâîì äëèíû n. Ìíîæåñòâî âñåõ r-ìåðíûõ
ñëîâ íàä àëôàâèòîì X îáîçíà÷èì � r X( ). r-ìåðíîå ñëîâî äëèíû n ðàñïîçíàåòñÿ
àâòîìàòîì, åñëè îí ïðè ðàáîòå íàä ñëîâîì ïîïàäàåò â çàêëþ÷èòåëüíîå ñîñòîÿíèå ïîñëå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 3
© À.À. Ãðèãîðÿí, Ñ.Ê. Øóêóðÿí, 2008
÷òåíèÿ èç ÿ÷åéêè, ñóììà êîîðäèíàò êîòîðîé ðàâíà n �1.
Çàïîëíåííóþ ÷àñòü r-ìåðíîé ëåíòû, â êîòîðîé ñóììà êîîðäèíàò êàæäîé
ÿ÷åéêè ðàâíà k, íàçîâåì äèàãîíàëüþ k ñëîâà è îáîçíà÷èì dk . Ïåðâûå
(ïîñëåäíèå) i i k( )0� � ñèìâîëîâ äèàãîíàëè dk îáîçíà÷èì d i d ik k( _ ) ( (_ )). Äëèíà
ñëîâà ñîâïàäàåò ñ ÷èñëîì åãî äèàãîíàëåé.
Ïóñòü äàíà ñèãíàòóðà S m m� { }( , ), ( , )1 21 2 , ãäå m1 0� , m2 0� , m m m� �1 2 0.
Íàáîð îäíîìåðíûõ è äâóìåðíûõ ñëîâ ( , . . ., )p pm1 äëèíû m íàçîâåì m-ëåíòî÷íûì
ñëîâîì ñ ñèãíàòóðîé S , åñëè ÷èñëî îäíîìåðíûõ ñëîâ ðàâíî m1 è ÷èñëî äâóìåðíûõ
ñëîâ ðàâíî m2 . Áåç îãðàíè÷åíèÿ îáùíîñòè áóäåì ñ÷èòàòü, ÷òî m-ëåíòî÷íûå ñëîâà
ñèãíàòóðû S èìåþò âèä ( , , ,p pm1 1
� � �p pm1 2
, . . ., ), ãäå p pm1 1
, . . ., —
îäíîìåðíûå ñëîâà, p p m� �1 2
, . . ., — äâóìåðíûå ñëîâà. Åñëè m2 0� , ò.å. âñå ëåíòû
îäíîìåðíûå, òî äëÿ òàêèõ m-ëåíòî÷íûõ ñëîâ â äàëüíåéøåì ñèãíàòóðà
óêàçûâàòüñÿ íå áóäåò.
Åñëè àâòîìàò A ðàñïîçíàåò/íå ðàñïîçíàåò ñëîâî w, òî îáîçíà÷èì ýòî
A w A w( ) / ( )� �1 0 ñîîòâåòñòâåííî.
Äâóìåðíûå ìíîãîëåíòî÷íûå àâòîìàòû A1 è A2 íàçîâåì ýêâèâàëåíòíûìè è
îáîçíà÷èì A A1 2~ , åñëè äëÿ êàæäîãî ñëîâà w A w A w1 2( ) ( )� , ïðè÷åì åñëè
A w A w1 2 1( ) ( )� � , òî ïîçèöèè (êîîðäèíàòû) ãîëîâîê íà äâóìåðíûõ ëåíòàõ
ñîâïàäàþò.
Äëÿ òîãî ÷òîáû îïðåäåëèòü ýêâèâàëåíòíîñòü ïî ìíîæåñòâó ðàñïîçíàâàåìûõ
ñëîâ, äëÿ êàæäîé äâóìåðíîé ëåíòû äîáàâëÿåòñÿ îäíà îäíîìåðíàÿ ëåíòà ñ àëôàâèòîì
{ }1 . Àâòîìàò ìîäèôèöèðóåòñÿ òàê, ÷òîáû ñ÷èòûâàòü «1» ñ äàííîé ëåíòû êàæ-
äûé ðàç ïðè äâèæåíèè â ïåðâîì íàïðàâëåíèè íà ñîîòâåòñòâóþùåé äâóìåðíîé ëåíòå.
Òàêèì îáðàçîì, äëèíà ñëîâà íà äîïîëíèòåëüíîé ëåíòå îïðåäåëÿåò ïîçèöèþ ãîëîâêè
íà òåêóùåé äèàãîíàëè äâóìåðíîé ëåíòû è äâà àâòîìàòà ýêâèâàëåíòíû, åñëè îíè ðàñ-
ïîçíàþò îäèíàêîâîå ìíîæåñòâî ñëîâ.
Äàëåå áóäåì ïîëàãàòü, ÷òî äâóìåðíûå àâòîìàòû óæå ñîäåðæàò ýòè äîïîëíèòåëüíûå
ëåíòû, è íå áóäåì óïîìèíàòü èõ ÿâíî (îíè ñ÷èòàþòñÿ ó÷òåííûìè â m1).
Ïîêàæåì, êàê ìîäåëèðîâàòü ïðîöåññ âû÷èñëåíèÿ äâóìåðíîãî àâòîìàòà A ñ
ñèãíàòóðîé S ñ ïîìîùüþ ( )m m1 22 -ëåíòî÷íîãî àâòîìàòà A� ñ îäíîìåðíûìè
ëåíòàìè.
Ïóñòü � � �� �1 1 1( ) ( , * )X { } — ìíîæåñòâî 2-ëåíòî÷íûõ ñëîâ ñ àëôàâèòîì
ïåðâîé ëåíòû X è àëôàâèòîì âòîðîé ëåíòû { }1, * . Îïðåäåëèì îòîáðàæåíèå
�: ( )� �2 X � .
Ïóñòü äàíî äâóìåðíîå ñëîâî w äëèíû n. Ñëîâo �( )w ñòðîèòñÿ ñëåäóþùèì
îáðàçîì (ðèñ 1). Ñîäåðæèìîå ýòîãî äâóìåðíîãî ñëîâà ïðåäñòàâëÿåòñÿ íà ïåðâîé
ëåíòå �( )w â ñëåäóþùåì ïîðÿäêå: x x x x x x x xn n00 01 10 02 11 20 0 1 1 0. . . . . ., ,� �
(äèàãîíàëü 0, äèàãîíàëü 1,..., äèàãîíàëü n �1). ×àñòü çàïîëíåíèÿ ëåíòû,
ñîîòâåòñòâóþùóþ äèàãîíàëè k äâóìåðíîãî ñëîâà (ÿ÷åéêè îò k k( ) / 1 2 äî
k k k( ) / 1 2 âêëþ÷èòåëüíî), òàêæå íàçîâåì äèàãîíàëüþ k è îáîçíà÷èì dk .
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
Ðèñ. 1
Âòîðàÿ ëåíòà �( )w ñîäåðæèò äëèíû ýòèõ äèàãîíàëåé, óìåíüøåííûå íà 1:
0 1 2 2, , , . . ., n � . Îíè ïðåäñòàâëÿþòñÿ â ôîðìå ïîñëåäîâàòåëüíîñòè ñèìâîëîâ «1»,
îòäåëåííûõ îäèí îò äðóãîãî ñèìâîëîì «*» (íàïðèìåð, * * * . . .* . . . *1 11 1 1 ). Ïóñòü �
— êîíå÷íîå 2-ëåíòî÷íîå ñëîâî èç � è åãî âòîðàÿ ëåíòà ñîäåðæèò ïî ìåíüøåé
ìåðå k 1 ñèìâîëîâ òèïà «*». ×èñëî ñèìâîëîâ òèïà «1» ìåæäó k è k 1
ñèìâîëàìè òèïà «*» îáîçíà÷èì T Tk ( ) ( ( )� �0 — ÷èñëî ñèìâîëîâ òèïà «1» ïåðåä
ïåðâûì ñèìâîëîì òèïà «*»).  ïðèâåäåííîì ñëó÷àå T w kk ( ( ))� � äëÿ 0 2� � �k n .
Ïóñòü W X X
m m� �� �1 2
1 2( ) ( ) — ìíîæåñòâî âñåõ m-ëåíòî÷íûõ ñëîâ
ñèãíàòóðû S . Îáîçíà÷èì W X
m m
1 1
1 2� �� �( ) .
Îòîáðàæåíèå � ðàñøèðÿåòñÿ íà ìíîæåñòâî âñåõ m-ëåíòî÷íûõ ñëîâ
ñèãíàòóðû S ñëåäóþùèì îáðàçîì: �:W W� 1 äëÿ m-ëåíòî÷íîãî ñëîâà
w p p p p Wm m� � � �( , . . ., , , . . ., )1 11 2
, �( ) ( , . . ., , , , . . ., ,( ) ( )
( )w p p p p pm m
� 1 1
1
1
2
1
2
1
p
m
2
2( ) ), ãäå ( , ) ( )( ) ( )p p pi i i
1 2 � �� äëÿ i m�1 2, . . ., .
Äëÿ ñëîâà w ñèãíàòóðû S w�( ) ÿâëÿåòñÿ ( )m m1 22 -ëåíòî÷íûì ñëîâîì
ñèãíàòóðû { }( , )1 21 2m m .
Ïåðâàÿ ëåíòà ñîäåðæèò ïîñëåäîâàòåëüíîñòü äèàãîíàëåé, âòîðàÿ —
ðàññòîÿíèÿ ìåæäó ñèìâîëàìè, ðàñïîëîæåííûìè â ñîñåäíèõ ÿ÷åéêàõ íà
äâóìåðíîé ëåíòå. Äëÿ ìîäåëèðîâàíèÿ ñ ïîìîùüþ îäíîìåðíûõ ëåíò äâèæåíèÿ èç
îäíîé ÿ÷åéêè â äðóãóþ íà äâóìåðíîé ëåíòå íåîáõîäèìî «ïðîïóñòèòü»/ïðîèãíî-
ðèðîâàòü ïåðâûå l ñèìâîëîâ íà ïåðâîé îäíîìåðíîé ëåíòå, ãäå l — äëèíà òåêóùåé
äèàãîíàëè â ñëó÷àå, êîãäà ìîäåëèðóåòñÿ äâèæåíèå â ïåðâîì íàïðàâëåíèè íà
äâóìåðíîé ëåíòå, è ïðîèãíîðèðîâàòü ïåðâûå l 1 ñèìâîëîâ â ñëó÷àå, êîãäà
ìîäåëèðóåòñÿ äâèæåíèå âî âòîðîì íàïðàâëåíèè. Â òî æå âðåìÿ ýòî ïðèâîäèò ê
ìíîæåñòâó ñëîâ íà âòîðîé îäíîìåðíîé ëåíòå, êîòîðîå íå ÿâëÿåòñÿ ðåãóëÿðíûì,
ò.å. íåâîçìîæíî ïîñòðîèòü êîíå÷íûé àâòîìàò, ðàñïîçíàþùèé ðàññìîòðåííîå
ìíîæåñòâî 2-ëåíòî÷íûõ ñëîâ.
×òîáû ïðåîäîëåòü âîçíèêøèå òðóäíîñòè, ðàñøèðèì ðàññìàòðèâàåìîå
ìíîæåñòâî 2-ëåíòî÷íûõ ñëîâ ñ ïîìîùüþ ñëåäóþùèõ ïðàâèë.
1. Äëÿ äàííîé äèàãîíàëè äâóìåðíîé ëåíòû ñ÷èòàåì êîäîì äèàãîíàëè ëþáóþ
ïîñëåäîâàòåëüíîñòü, êîòîðàÿ ïîìèìî èñõîäíûõ ñèìâîëîâ äèàãîíàëè, çàïèñàííûõ
â òîì æå ïîðÿäêå, ñîäåðæèò íåêîòîðûå èçáûòî÷íûå ñèìâîëû ïîñëå èñõîäíûõ,
ïðè ýòîì âìåñòî äëèíû èñõîäíîé äèàãîíàëè íà âòîðîé ëåíòå äîëæíà áûòü
çàïèñàíà äëèíà «ðàñøèðåííîé» äèàãîíàëè.
2. Åñëè ó äàííîé ïàðû ñîñåäíèõ äèàãîíàëåé ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü
ñèìâîëîâ, êîòîðàÿ çàêàí÷èâàåò ïåðâóþ äèàãîíàëü è îäíîâðåìåííî íà÷èíàåò
âòîðóþ, è åñëè ýòà ïîñëåäîâàòåëüíîñòü îïóùåíà â îäíîé èç äèàãîíàëåé âî âðåìÿ
èõ êîäèðîâàíèÿ íà ïåðâîé îäíîìåðíîé ëåíòå, òî ïîëó÷åííàÿ «óñå÷åííàÿ» ïàðà
äèàãîíàëåé òàêæå ñ÷èòàåòñÿ êîäîì äâóõ ñîñåäíèõ äèàãîíàëåé. Ïðè ýòîì âìåñòî
äëèíû èñõîäíîé äèàãîíàëè íà âòîðîé ëåíòå äîëæíà áûòü çàêîäèðîâàíà äëèíà
«óñå÷åííîé» äèàãîíàëè.
Ïîêàæåì, ÷òî òàêîå ðàñøèðåíèå ïðèâîäèò ê ðåãóëÿðíîìó ìíîæåñòâó ñëîâ íà
âòîðîé ëåíòå çà ñ÷åò òîãî, ÷òî áîëüøå íåò íåîáõîäèìîñòè èìåòü âîçðàñòàþùèå
íà åäèíèöó äëèíû äèàãîíàëåé. Ïîêàæåì òàêæå, ÷òî ñóùåñòâóåò î÷åâèäíîå
îòîáðàæåíèå ýòîãî ðàñøèðåííîãî ìíîæåñòâà íà èñõîäíîe ìíîæåñòâo
2-ëåíòî÷íûõ ñëîâ, ò.å. ïî çàäàííîé ïàðå ñëîâ íà ïðîñòûõ ëåíòàõ, ðàñïîçíàâàåìûõ
2-ëåíòî÷íûì àâòîìàòîì, ìîæíî îäíîçíà÷íî ïîëó÷èòü çàïîëíåíèå
ñîîòâåòñòâóþùåé äâóìåðíîé ëåíòû, ðàñïîçíàâàåìîé èñõîäíûì àâòîìàòîì. Äëÿ
ìíîæåñòâà âñåõ äâóìåðíûõ ñëîâ ðåçóëüòèðóþùèì ìíîæåñòâîì ñëîâ íà âòîðîé
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 5
ëåíòå áóäåò {{ } }1 * .
Ðàññìîòðèì ñëåäóþùåå ïîäìíîæåñòâî ìíîæåñòâà W W1 : � � � � � �{w w W| ,
w w� � �( )}, ò.å. ñëîâà, ó êîòîðûõ íà âòîðîé ëåíòå íàïèñàíî 0 1 2, , , . . . . Ëåãêî
óáåäèòüñÿ, ÷òî âåðíà ñëåäóþùàÿ ëåììà.
Ëåììà 1. Îòîáðàæåíèå �:W W� � âçàèìíî îäíîçíà÷íî.
Ïîñòðîèì àâòîìàò A�, êîòîðûé ðàáîòàåò íàä ñëîâàìè èç ìíîæåñòâà W1.
Ãëàâíàÿ òðóäíîñòü åãî ïîñòðîåíèÿ — ðåàëèçàöèÿ îïèñàííûõ âûøå ïðàâèë,
êîòîðûå ïîçâîëÿþò ïðåîáðàçîâàòü èñõîäíîå íåðåãóëÿðíîå ìíîæåñòâî ñëîâ
âòîðîé ëåíòû â ðåãóëÿðíîå. Ëåììû 2 è 3 îïðåäåëÿþò øàãè ïðåîáðàçîâàíèÿ
èñõîäíîãî ìíîæåñòâà â ðàñøèðåííîå ðåãóëÿðíîå ìíîæåñòâî ñ ñîõðàíåíèåì
íåêîòîðûõ áàçîâûõ ñâîéñòâ èñõîäíîãî ìíîæåñòâà.
Ìíîæåñòâî ñîñòîÿíèé A� îáîçíà÷èì Q�. Äëÿ êàæäîãî ñîñòîÿíèÿ q Q� â A�
îïðåäåëÿåòñÿ ñîîòâåòñòâóþùåå ñîñòîÿíèå q� òàêîå, ÷òî q Q q QF F�� � � � è
q Q q Qk k�� � � � . Äëÿ êàæäîãî ñîñòîÿíèÿ q Qi1 � , ãäå ëåíòà i äâóìåðíà, è âõîäíîãî
ñèìâîëà x A� áóäåò èìåòü äâà
äîïîëíèòåëüíûõ ñîñòîÿíèÿ, êîòîðûå
èñïîëüçóþòñÿ äëÿ ïåðåäâèæåíèÿ
ãîëîâêè àâòîìàòà A� íà ïåðâîé
îäíîìåðíîé ëåíòå ïðè ìîäåëèðîâàíèè
äâèæåíèÿ ãîëîâêè íà äâóìåðíîé ëåíòå
àâòîìàòà A. Ôðàãìåíò àâòîìàòà A�, ñî-
îòâåòñòâóþùèé îäíîìó ïåðåõîäó â A,
ïîêàçàí íà ðèñ. 2 äëÿ ñëó÷àåâ
�( , )q x1 1� è �( , )q x1 2� (çàøòðèõî-
âàííûå ñîñòîÿíèÿ ñîîòâåòñòâóþò
âòîðîé îäíîìåðíîé ëåíòå). Åñëè
ëåíòà i — îäíîìåðíà, òî ñîîòâåòñòâóþùèé ôðàãìåíò ãðàôà ïåðåõîäîâ àâòîìàòà A
ïîâòîðÿåòñÿ â A�.
Äàëåå ( )m m1 22 -ëåíòî÷íûé àâòîìàò A�, ïîñòðîåííûé óêàçàííûì ñïîñîáîì èç
èñõîäíîãî äâóìåðíîãî m-ëåíòî÷íîãî àâòîìàòà ñ ñèãíàòóðîé S , îáîçíà÷èì � ( )A .
Ïðè ìîäåëèðîâàíèè ÷òåíèÿ ñèìâîëà x íà äâóìåðíîé ëåíòå â ñîñòîÿíèè
q àâòîìàòà A àâòîìàò A� ðàáîòàåò ñëåäóþùèì îáðàçîì. Ïîñëå ÷òåíèÿ ñèìâîëà x
íà ïåðâîé îäíîìåðíîé ëåíòå â çàâèñèìîñòè îò çíà÷åíèÿ �( , )q x ïðîïóñêàþòñÿ l
èëè l 1 ñèìâîëîâ (l — ÷èñëî ñèìâîëîâ «1» íà âòîðîé îäíîìåðíîé ëåíòå), çàòåì
ïðîèñõîäèò ïåðåõîä â ñîñòîÿíèå, ñîîòâåòñòâóþùåå �( , )q x . Ïðîïóñê ñèìâîëîâ
îçíà÷àåò, ÷òî ïîî÷åðåäíî ñ÷èòûâàþòñÿ ñèìâîëû ñî âòîðîé è ïåðâîé ëåíò äî òåõ
ïîð, ïîêà ñî âòîðîé ëåíòû íå áóäåò ñ÷èòàí ñèìâîë «*».
Ëåììà 2.Ïóñòü w W� — m-ëåíòî÷íîå äâóìåðíîå ñëîâî ñ ñèãíàòóðîé
S A, — äâóìåðíûé m-ëåíòî÷íûé àâòîìàò ñ ñèãíàòóðîé S , A A� � � ( ). Òîãäà
A w A w� �( ( )) ( )� .
Äîêàçàòåëüñòâî. Ïîêàæåì, ÷òî ïîñëå ïðîèçâîëüíîãî øàãà k àâòîìàòà A, ãäå
k k k km i� 1 . . . , — ÷èñëî øàãîâ íà ëåíòå i, è ñîîòâåòñòâóþùåé
ïîñëåäîâàòåëüíîñòè øàãîâ àâòîìàòà A�, ìîäåëèðóþùèõ øàã àâòîìàòà A:
1) A è A� ïåðåéäóò â ñîñòîÿíèÿ, ñîîòâåòñòâóþùèå îïèñàííûì ïîñòðîåíèÿì;
2) òåêóùèé ñèìâîë ñëîâà w, îáîçðåâàåìûé àêòèâíîé ãîëîâêîé àâòîìàòà A, è
òåêóùèé ñèìâîë íà ñîîòâåòñòâóþùåé îäíîìåðíîé ëåíòå àâòîìàòà A�,
îáîçðåâàåìûé åãî àêòèâíîé ãîëîâêîé, ñîâïàäóò;
3) òåêóùèé ñèìâîë íà îäíîìåðíîé ëåíòå ñ êîäîì äëèíû äèàãîíàëè, íà
êîòîðîé íàõîäèòñÿ àêòèâíàÿ ãîëîâêà àâòîìàòà A�, ÿâëÿåòñÿ ïåðâûì ñèìâîëîì
«1» â ñîîòâåòñòâóþùåì êîäå.
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
Ðèñ. 2
Äîêàçàòåëüñòâî ïðîâîäèòñÿ èíäóêöèåé ïî k. Ðàññìîòðèì òîëüêî äâóìåðíûå
ëåíòû, òàê êàê ïîâåäåíèå A� äëÿ îäíîìåðíûõ ëåíò íå îòëè÷àåòñÿ îò ïîâåäåíèÿ
àâòîìàòà A.
Ïîñêîëüêó àâòîìàò A� ïîëíîñòüþ ïîâòîðÿåò äâèæåíèÿ àâòîìàòà A íà îäíî-
ìåðíûõ ëåíòàõ, áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî íà÷àëüíîå ñîñòîÿ-
íèå A q Ql0 � , ãäå ëåíòà l — äâóìåðíà. Êàê îïèñàíî âûøå, äâóìåðíàÿ ëåíòà l ìî-
äåëèðóåòñÿ ñ ïîìîùüþ òðåõ îäíîìåðíûõ ëåíò, íàçûâàåìûõ äàëåå ïåðâîé, âòîðîé
è òðåòüåé îäíîìåðíûìè ëåíòàìè l ñîîòâåòñòâåííî.
Åñëè k �1, òî A ïåðåéäåò â ñîñòîÿíèå a q x A� ��( , ),0 00 — â ñîñòîÿíèå a�.
Òåêóùèì ñèìâîëîì ñëîâà w íà äâóìåðíîé ëåíòå l è òåêóùèì ñèìâîëîì �( )w íà
ïåðâîé îäíîìåðíîé ëåíòå l áóäóò èëè x l
01
( ) , èëè x l
10
( ) (äèàãîíàëü 1), ãîëîâêà íà
âòîðîé îäíîìåðíîé ëåíòå l áóäåò îáîçðåâàòü åäèíñòâåííûé ñèìâîë «1» êîäà
äëèíû 1.
Ïðåäïîëîæèì, ÷òî óòâåðæäåíèå âåðíî äëÿ ïåðâûõ k �1 øàãîâ. Ýòî îçíà÷àåò,
÷òî:
1) àâòîìàò A íàõîäèòñÿ íà äèàãîíàëè k i â ñîñòîÿíèè q Qi� ;
2) àâòîìàò A� íàõîäèòñÿ â ñîîòâåòñòâóþùåì ñîñòîÿíèè q Qi�� �;
3) àâòîìàò A� íàõîäèòñÿ íà äèàãîíàëè k i íà ïåðâîé îäíîìåðíîé ëåíòå i è â
íà÷àëå êîäà äëèíû äèàãîíàëè k i íà âòîðîé îäíîìåðíîé ëåíòå i.
Ïóñòü x — òåêóùèé ñèìâîë íà ëåíòå i ñëîâà w è ïåðâîé îäíîìåðíîé ëåíòå i
ñëîâà �( )w . Òîãäà ñîãëàñíî ïîñòðîåíèþ àâòîìàò A� ïðîäâèíåòñÿ íà ïåðâîé ëåíòå i
ñòîëüêî ðàç, ñêîëüêî ñèìâîëîâ òèïà «1» êîäà äëèíû íàõîäèòñÿ ñïðàâà îò ãîëîâêè
ëåíòû äî ïåðâîãî ñèìâîëà «*». Ïî ïðåäïîëîæåíèþ èíäóêöèè ãîëîâêà âòîðîé
ëåíòû i îáîçðåâàåò ïåðâûé ñèìâîë êîäà äèàãîíàëè k i , ïîýòîìó A� ïðîäâèíåòñÿ k i
ðàç íà ïåðâîé ëåíòå i. Îí ïðîäâèíåòñÿ åùå ðàç, åñëè �( , )q x � 2. Ãîëîâêà A� íà
ïåðâîé ëåíòå i áóäåò îáîçðåâàòü ñèìâîë äèàãîíàëè k i 1. Ïðè ýòîì òåêóùèé ñèì-
âîë íà âòîðîé ëåíòå i àâòîìàòà A� ñòàíåò ïåðâûì ñèìâîëîì «1» êîäà äèàãîíàëè
k i 1. Ïîñëå ýòîãî A� ïîïàäàåò â ñîñòîÿíèå a Q j�� � , ñîîòâåòñòâóþùåå cîñòîÿíèþ
a q x Q j� ��( , ) àâòîìàòà A. Ïîñêîëüêó ïîëîæåíèå ãîëîâîê äëÿ ïåðâîé, âòîðîé è
òðåòüåé ëåíò j àâòîìàòà A� íå èçìåíèëîñü â ðàññìîòðåííîì âûøå ïðîöåññå, òî
ïðåäïîëîæåíèå èíäóêöèè äëÿ íèõ îñòàåòñÿ â ñèëå. Èòàê, ïðåäïîëîæåíèå øàãà
èíäóêöèè âåðíî è äëÿ k, ò.å. ïîñêîëüêó a Q a QF F�� � � � , òî A w A w� �( ( )) ( )� .
Ëåììà äîêàçàíà.
Ëåììà 3. Äëÿ ëþáîãî ( )m m1 22 -ëåíòî÷íîãî ñëîâà w p pm1 1 1
� ( , . . ., , p
1
1( ) ,
p p p W
m m1
2
1
2
1
2
2
( ) , . . ., , )( ) ( ) � ñóùåñòâóåò ñëîâî w W� òàêîå, ÷òî äëÿ ëþáîãî äâóìåðíî-
ãî m-ëåíòî÷íîãî àâòîìàòà A ñ ñèãíàòóðîé S A A� � �� ( ) � � � �A w A w( ) ( ( ))1 � .
Äîêàçàòåëüñòâî. Åñëè � w W� òàêîå, ÷òî w w1 � �( ), òî î÷åâèäíî, ÷òî ëåììà
âåðíà. Ïðåäïîëîæèì, ÷òî ýòî íå òàê.
Ïóñòü k — íàèìåíüøåå ÷èñëî, äëÿ êîòîðîãî T p p kk i i( , )( ) ( )1 2 � . Îáîçíà÷èì
s T p pk i i� ( , )( ) ( )1 2 . Âîçìîæíû äâà ñëó÷àÿ.
1. Ñëó÷àé s k� . Òîãäà s k� ñèìâîëîâ ïîñëå äèàãîíàëè k èãíîðè- ðóþòñÿ
àâòîìàòîì A�. Åñëè èõ óäàëèòü è ñîîòâåòñòâåííî óäàëèòü s k� ñèìâîëîâ
òèïà «1» íà âòîðîé ëåíòå, òî ñîãëàñíî ïîñòðîåíèþ ïîâåäåíèå àâòîìàòà A�
íà ñëîâå w1 íå áóäåò îòëè÷àòüñÿ îò åãî ïîâåäåíèÿ íà ðåçóëüòèðóþùåì
ñëîâå (ðèñ. 3).
2. Ñëó÷àé s k� . Ïîñëåäíèå k s� ñèìâîëîâ ÿâëÿþòñÿ íåäîñòàþùåé ÷àñòüþ
îäíîé èç äâóõ ñîñåäíèõ äèàãîíàëåé äëÿ àâòîìàòà A�. Ïîýòîìó åñëè èõ ïîâòîðèòü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 7
è ñîîòâåòñòâåííî äîáàâèòü k s� ñèìâîëîâ òèïà «1» â êîä äëèíû äèàãîíàëè íà
âòîðîé ëåíòå, òî ñîãëàñíî ïîñòðîåíèþ ïîâåäåíèå àâòîìàòà A� íà ñëîâå w1 íå áó-
äåò îòëè÷àòüñÿ îò åãî ïîâåäåíèÿ íà ðåçóëüòèðóþùåì ñëîâå (ðèñ. 4).
Ñ÷èòàÿ, ÷òî äàííûå ïðåîáðàçîâàíèÿ âûïîëíåíû äëÿ âñåõ i m�1 2, . . ., , ïîëó÷èì
w p p u u u u Wm m m
� � � �( , . . ., , , , . . ., , )( ) ( )
( ) ( )1 1
1
1
2
1
2
1
2
2 . Òàêèì îáðàçîì, w w� ��� 1 ( ) è
A w A w� � �( ) ( ( ))1 � .
Ëåììà äîêàçàíà.
Ñëåäñòâèå 1. Ñóùåñòâóåò ôàêòîðèçàöèÿ ìíîæåñòâà W1 òàêàÿ, ÷òî êàæäûé êëàññ
ñîäåðæèò îäíî è òîëüêî îäíî ñëîâî èç W � è äëÿ ïðîèçâîëüíîãî àâòîìàòà A ñ
ñèãíàòóðîé S � ( )A ðàñïîçíàåò/íå ðàñïîçíàåò âñå ñëîâà äàííîãî êëàññà.
Íàïðèìåð, ñëîâà ( , * *)x x x x x x x xr s r s
00 01 10 02 11 20 1 1 1{ } { } { } { } è
( , * *)x x x x x x W00 01 10 02 11 20 1 � � íàõîäÿòñÿ â îäíîì êëàññå.
Íà ðèñ. 5 èìååì A w A w� � � �( ) ( ( ))� — ïîñëåäîâàòåëüíîñòü «xx» áóäåò
ïðîïóùåíà àâòîìàòîì, òàê êàê T w1 3( )� � , à «x x11 20» ñîäåðæèòñÿ â äâóõ ñîñåäíèõ
äèàãîíàëÿõ, ïîñêîëüêó T w2 0( )� � .
8 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
Ðèñ. 3
Ðèñ. 4
Ðèñ. 5
Ðàññìîòðèì äðóãîé ïðèìåð. Ïóñòü äàí 1-ëåíòî÷íûé äâóìåðíûé àâòîìàò
A, ðàñïîçíàþùèé òîëüêî ñëîâà, ó êîòîðûõ x a ii0 0 1� �, , , . . . (ðèñ. 6).
Àâòîìàò A� ðàñïîçíàåò ñëîâà, êîòîðûå ñîäåðæàò ñèìâîëû òèïà «a» íà ïåðâîé
ëåíòå, îòäåëåííûå îäèí îò äðóãîãî ïîñëåäîâàòåëüíîñòüþ ïðîèçâîëüíûõ ñèìâî-
ëîâ èç X . Ïðè ýòîì âòîðàÿ
ëåíòà ñîäåðæèò òîëüêî äëè-
íû ýòèõ ïîñëåäîâàòåëüíîñ-
òåé, çàêîäèðîâàííûå ñ ïî-
ìîùüþ ñèìâîëîâ «1» è «*».
Ïàðà ( , * *)axxxaxa 111 1 ÿâëÿ-
åòñÿ ïðèìåðîì òàêîãî ñëîâà.
 ýòîì ñëó÷àå ïðîåêöèè ðàñ-
ïîçíàâàåìûõ 2-ëåíòî÷íûõ
ñëîâ — ìíîæåñòâà { { }}a x è
{{ } }1 * íà ïåðâîé è âòîðîé
ëåíòàõ ñîîòâåòñòâåííî.
Ïóñòü äàíû äâà äâóìåðíûõ m-ëåíòî÷íûõ àâòîìàòà A1 è A2 ñ ñèãíàòóðîé
S . Ïóñòü � �A A1 1� ( ) è � �A A2 2� ( ).
Ëåììà 4.Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå: � � �A A A A1 2 1 2~ ~ .
Äîêàçàòåëüñòâî.Ïðåäïîëîæèì îáðàòíîå: � �A A1 2~ , íî A1 è A2 íå
ýêâèâàëåíòíû. Ýòî îçíà÷àåò, ÷òî � �w A w A w, ( ) ( )1 2 . Èç ëåììû 2 ñëåäóåò, ÷òî
A w A w1 1( ) ( ( ))� � � è A w A w2 2( ) ( ( ))� � � . Îòñþäà ïîëó÷àåì, ÷òî � �A w1 ( ( ))�
� �A w2 ( ( ))� . Íî ýòî ïðîòèâîðå÷èò A A� �1 2~ . Òàêèì îáðàçîì, ïðåäïîëîæåíèå, ÷òî
A1 è A2 íå ýêâèâàëåíòíû, íåâåðíî.
Ëåììà äîêàçàíà.
Ëåììà 5. Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå: � � � � �A A A A1 2 1 2~ ~ .
Äîêàçàòåëüñòâî. Èç � � �A A1 2~ ñëåäóåò, ÷òî � � � � � � �w A w A w, ( ) ( )1 2 . Åñëè
w W� � �, òî ñîãëàñíî ëåììå 3 ñóùåñòâóåò w W A w A w� �� � � � � � � �, ( ) ( )1 1 è
� � � � � �A w A w2 2( ) ( ), à çíà÷èò, � � � � � � �A w A w1 2( ) ( ) . Òàêèì îáðàçîì, ìîæíî ñ÷èòàòü,
÷òî w W�� �.
Èç ëåììû 2 âûòåêàåò, ÷òî A w A w1
1
1( ( )) ( )�� � � � � è A w A w2
1
2( ( )) ( )�� � � � � .
Ñëåäîâàòåëüíî, A w A w1
1
2
1( ( )) ( ( ))� �� �� � � . Ýòî îçíà÷àåò, ÷òî A1 è A2 íå
ýêâèâàëåíòíû.
Ëåììà äîêàçàíà.
Ëåììû 4 è 5 ïðèâîäÿò ê ñëåäóþùåé òåîðåìå.
Òåîðåìà. Ñïðàâåäëèâî óòâåðæäåíèå A A A A1 2 1 2~ ~ .� � �
Ñëåäñòâèå 2. Ïðîáëåìà ýêâèâàëåíòíîñòè äâóìåðíûõ ìíîãîëåíòî÷íûõ
àâòîìàòîâ ðàçðåøèìà.
Ýòî ñëåäóåò èç òåîðåìû è òîãî ôàêòà, ÷òî ïðîáëåìà ýêâèâàëåíòíîñòè
ìíîãîëåíòî÷íûõ àâòîìàòîâ ðàçðåøèìà [2].
Àâòîðû âûðàæàþò ãëóáîêóþ áëàãîäàðíîñòü ÷ëåíó-êîððåñïîíäåíòó ÍÀÍ
Óêðàèíû À.À. Ëåòè÷åâñêîìó, îïðåäåëèâøåìó áîëåå 30 ëåò íàçàä îáùåå íà-
ïðàâëåíèå èññëåäîâàíèé, ïðîôåññîðó Ä. Êíóòó, ñóùåñòâåííî ïîâëèÿâøåìó
íà âîçîáíîâëåíèå èññëåäîâàíèé, è äîêòîðó ôèç.-ìàò. íàóê À.Á. Ãîäëåâñêîìó
çà ïîñòîÿííûé èíòåðåñ ê ðàáîòå, öåííûå ñîâåòû è çàìå÷àíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ã î ä ë å â ñ ê è é À . Á . , Ë å ò è ÷ å â ñ ê è é À . À . , Ø ó ê ó ð ÿ í Ñ . Ê . Î ñâîäèìîñòè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 9
Ðèñ. 6
ïðîáëåìû ôóíêöèîíàëüíîé ýêâèâàëåíòíîñòè ñõåì ïðîãðàìì íàä íåâûðîæäåííûì áàçèñîì
ðàíãà åäèíèöà ê ýêâèâàëåíòíîñòè àâòîìàòîâ ñ ìíîãîìåðíûìè ëåíòàìè // Êèáåðíåòèêà. —
1980. — ¹ 6. — Ñ. 1–7.
2. H a r j u T . , K a r h u m a k i J . The equivalence problem of multitape finite automata // Theoret.
Comput. Sci. — 1991. — 78. — P. 347–355.
Ïîñòóïèëà 24.04.2007
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
|