Эквивалентность регулярных выражений в частично коммутативном алфавите
Розглянуто проблему еквівалентності регулярних виразів в частково комутативному алфавіті, коли елементи неперетинних підмножин переставні. Доказано розв’язність спеціального випадку проблеми, коли потужність однієї підмножини більша одиниці, а потужність решти підмножин дорівнює одиниці....
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44368 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Эквивалентность регулярных выражений в частично коммутативном алфавите / А.С. Шукурян // Кибернетика и системный анализ. — 2009. — № 3. — С. 65-74. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-44368 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-443682025-02-09T16:54:57Z Эквивалентность регулярных выражений в частично коммутативном алфавите Еквівалентність регулярних виразів в частково комутативному алфавіті Equivalence of regular expressions over a partially commutative alphabet Шукурян, А.С. Кибернетика Розглянуто проблему еквівалентності регулярних виразів в частково комутативному алфавіті, коли елементи неперетинних підмножин переставні. Доказано розв’язність спеціального випадку проблеми, коли потужність однієї підмножини більша одиниці, а потужність решти підмножин дорівнює одиниці. The equivalence problem is considered for regular expressions over a partially commutative alphabet. The alphabet is decomposed into disjoint subsets of noncommutative elements. The special case of the problem when the cardinal number of only one of subsets is larger than 1 and cardinal numbers of other subsets are equal to 1 is proved to be algorithmically solvable. 2009 Article Эквивалентность регулярных выражений в частично коммутативном алфавите / А.С. Шукурян // Кибернетика и системный анализ. — 2009. — № 3. — С. 65-74. — Бібліогр.: 7 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44368 519.681 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
https://nasplib.isofts.kiev.ua/handle/123456789/44368 |
| citation_txt |
Эквивалентность регулярных выражений в частично коммутативном алфавите / А.С. Шукурян // Кибернетика и системный анализ. — 2009. — № 3. — С. 65-74. — Бібліогр.: 7 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šukurânas ékvivalentnostʹregulârnyhvyraženijvčastičnokommutativnomalfavite AT šukurânas ekvívalentnístʹregulârnihvirazívvčastkovokomutativnomualfavítí AT šukurânas equivalenceofregularexpressionsoverapartiallycommutativealphabet |
| first_indexed |
2025-11-28T06:30:32Z |
| last_indexed |
2025-11-28T06:30:32Z |
| _version_ |
1850014634505928704 |
| fulltext |
ÓÄÊ 519.681
À.Ñ. ØÓÊÓÐßÍ
ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉ
 ×ÀÑÒÈ×ÍÎ ÊÎÌÌÓÒÀÒÈÂÍÎÌ ÀËÔÀÂÈÒÅ
Êëþ÷åâûå ñëîâà: ðåãóëÿðíûå âûðàæåíèÿ, ÷àñòè÷íî êîììóòàòèâíûé àëôàâèò,
àâòîìàòû, ýêâèâàëåíòíîñòü.
Àëãîðèòìè÷åñêàÿ ðàçðåøèìîñòü ïðîáëåìû ýêâèâàëåíòíîñòè ðåãóëÿðíûõ âûðàæå-
íèé â êîììóòàòèâíîì àëôàâèòå äîêàçàíà Â.Í. Ðåäüêî â 1964 ã. Èç ðåçóëüòàòà,
ïîëó÷åííîãî Â.À. Òóçîâûì â 1971 ã., ñëåäóåò, ÷òî â îáùåì ñëó÷àå ïðîáëåìà ýê-
âèâàëåíòíîñòè ðåãóëÿðíûõ âûðàæåíèé â ÷àñòè÷íî êîììóòàòèâíîì àëôàâèòå àëãî-
ðèòìè÷åñêè íåðàçðåøèìà. Ïîä ÷àñòè÷íî êîììóòàòèâíûì àëôàâèòîì ïîíèìàåòñÿ
îáúåäèíåíèå íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâ, â êîòîðîì ëþáûå äâà ñèìâîëà èç
îäíîãî è òîãî æå ïîäìíîæåñòâà íå ïåðåñòàíîâî÷íû, à ëþáûå äâà ñèìâîëà èç
ðàçíûõ ïîäìíîæåñòâ ïåðåñòàíîâî÷íû.  îïðåäåëåííîì ñìûñëå ýòîò àëôàâèò ÿâ-
ëÿåòñÿ îáîáùåíèåì êîììóòàòèâíîãî àëôàâèòà, êîòîðûé ñîîòâåòñòâóåò ñëó÷àþ,
êîãäà ìîùíîñòü êàæäîãî ïîäìíîæåñòâà ðàâíà åäèíèöå. B.A. Òóçîâ ïîêàçàë, ÷òî
åñëè ñóùåñòâóåò õîòÿ áû äâà ïîäìíîæåñòâà ìîùíîñòè, áîëüøåé åäèíèöû, òî
ïðîáëåìà ýêâèâàëåíòíîñòè àëãîðèòìè÷åñêè íåðàçðåøèìà. Òàêèì îáðàçîì, òîëüêî
äëÿ îäíîãî ñïåöèàëüíîãî ñëó÷àÿ íå áûëî èçâåñòíî, ðàçðåøèìà ëè ïðîáëåìà ýê-
âèâàëåíòíîñòè: êîãäà ìîùíîñòü îäíîãî èç ïîäìíîæåñòâ â ÷àñòè÷íî êîììóòàòèâ-
íîì àëôàâèòå áîëüøå åäèíèöû, à ìîùíîñòü âñåõ îñòàëüíûõ ïîäìíîæåñòâ ðàâíà
åäèíèöå.  äàííîé ñòàòüå äîêàçàíî, ÷òî è â ýòîì ñëó÷àå ïðîáëåìà ýêâèâàëåí-
òíîñòè ðåãóëÿðíûõ âûðàæåíèé àëãîðèòìè÷åñêè ðàçðåøèìà.
Ïóñòü Y— êîíå÷íûé àëôàâèò, Y Yn1 , ,� — ðàçáèåíèå àëôàâèòà Y ïî îòíîøå-
íèþ � íà íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà. Åñëè Y— ìíîæåñòâî, òî ìîùíîñòü
ýòîãî ìíîæåñòâà îáîçíà÷èì | |Y .
Ïóñòü R1 è R2 — ðåãóëÿðíûå âûðàæåíèÿ [1] â àëôàâèòå Y . Åñëè äëÿ êàæäîãî
w R� 1ñóùåñòâóåò ñëîâî w R�� 2 , ñîâïàäàþùåå ñ w ñ òî÷íîñòüþ äî ïåðåñòàíîâêè
ñìåæíûõ ñèìâîëîâ, îòíîñÿùèõñÿ ê ðàçíûì êëàññàì ðàçáèåíèÿ àëôàâèòà Y è, íàáî-
ðîò, äëÿ êàæäîãî ñëîâà w R�� 2 ñóùåñòâóåò ñëîâî w R� 1, ñîâïàäàþùåå ñ �w ñ òî÷-
íîñòüþ äî ïåðåñòàíîâêè ñìåæíûõ ñèìâîëîâ, îòíîñÿùèõñÿ ê êëàññàì ðàçáèåíèÿ àë-
ôàâèòà Y , òî ðåãóëÿðíûå âûðàæåíèÿ R1 è R2 íàçîâåì �-ýêâèâàëåíòíûìè è îáîçíà-
÷èì R R1 2~ ( )� .
Ñ îäíîé ñòîðîíû, Â.Í. Ðåäüêî ïîêàçàë [2], ÷òî åñëè âñå êëàññû ðàçáèåíèÿ àëôà-
âèòà îäíîýëåìåíòíû, òî ïðîáëåìà �-ýêâèâàëåíòíîñòè àëãîðèòìè÷åñêè ðàçðåøèìà.
Ñ äðóãîé ñòîðîíû, êàê âûòåêàåò èç ðåçóëüòàòà Â.À. Òóçîâà [3], åñëè ðàçáèåíèå àëôàâè-
òà ñîäåðæèò õîòÿ áû äâà êëàññà ñ ÷èñëîì ñèìâîëîâ, íå ìåíüøèì äâóõ, òî ïðîáëåìà
�-ýêâèâàëåíòíîñòè ñâîäèòñÿ ê ïðîáëåìå ýêâèâàëåíòíîñòè íåäåòåðìèíèðîâàííûõ ìíî-
ãîëåíòî÷íûõ àâòîìàòîâ [4] è, ñëåäîâàòåëüíî, àëãîðèòìè÷åñêè íåðàçðåøèìà.
 íàñòîÿùåé ðàáîòå ðàññìàòðèâàåòñÿ «ïðîìåæóòî÷íûé ñëó÷àé», êîãäà âñå
êëàññû ðàçáèåíèÿ àëôàâèòà Y , êðîìå îäíîãî, îäíîýëåìåíòíûå. Èññëåäîâàíèå îñíî-
âàíî íà èñïîëüçîâàíèè íåêîòîðûõ ðåçóëüòàòîâ òåîðèè ÷àñòè÷íî êîììóòàòèâíûõ ïî-
ëóãðóïï [5] è àâòîìàòîâ ñ ìíîãîìåðíûìè ëåíòàìè [6, 7].
 ðàçä. 1 îïèñûâàåòñÿ ñïåöèàëüíîå ïðåäñòàâëåíèå ýëåìåíòîâ ÷àñòè÷íî êîììó-
òàòèâíîé ïîëóãðóïïû, íà êîòîðîì îñíîâàíû äàëüíåéøèå ïîñòðîåíèÿ. Â ðàçä 2 ïî-
êàçàíî, ÷òî ïðîáëåìà �-ýêâèâàëåíòíîñòè, êîãäà ìîùíîñòè ïîäìíîæåñòâ ðàâíû åäè-
íèöå, àëãîðèòìè÷åñêè ðàçðåøèìà. Äîêàçàòåëüñòâî îòëè÷àåòñÿ îò äîêàçàòåëüñòâà
â [2], è äåìîíñòðèðóåò èäåþ, ïðèìåíÿåìóþ äëÿ äîêàçàòåëüñòâà ðàññìîòðåííîãî â
ñòàòüå «ïðîìåæóòî÷íîãî ñëó÷àÿ». Ñïåöèàëüíàÿ ìíîãîìåðíàÿ ëåíòà [6] èñïîëüçóåò-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 65
© À.Ñ. Øóêóðÿí, 2009
ñÿ äëÿ çàïèñè ñëåäîâ âûïîëíåíèÿ äàííîãî àâòîìàòà. Ìîíîòîííîå äâèæåíèå âïåðåä
ïî ëåíòå âûïîëíÿåòñÿ îòíîñèòåëüíî äèàãîíàëåé ëåíòû: îò òåêóùåé äèàãîíàëè ê
ñìåæíîé. Â ðàçä. 3 äîêàçàíà ðàçðåøèìîñòü ïðîáëåìû ýêâèâàëåíòíîñòè ðåãóëÿðíûõ
âûðàæåíèé â íåêîììóòàòèâíîì àëôàâèòå. Äîêàçàòåëüñòâî òàêæå îòëè÷íî îò èçâåñò-
íîãî äîêàçàòåëüñòâà â [4] è èñïîëüçóåò ìíîãîìåðíóþ ëåíòó, íî êàæäûé øàã i äâè-
æåíèÿ ïî ëåíòå âûïîëíÿåòñÿ íå ê ñìåæíîé äèàãîíàëè, à ê äèàãîíàëè ñ íîìåðîì
� � 2i , ãäå � — íîìåð òåêóùåé äèàãîíàëè. Â ðàçä. 4 ïîñòðîåíà ñïåöèàëüíàÿ êîìáè-
íàöèÿ ñëó÷àåâ, ðàññìîòðåííûõ â ðàçä. 2 è 3, êîòîðàÿ ñîîòâåòñòâóåò ïîñòàâëåííîé
çàäà÷å. Äîêàçàíî, ÷òî ïðîáëåìà �-ýêâèâàëåíòíîñòè çäåñü àëãîðèòìè÷åñêè ðàçðåøè-
ìà. Òàêèì îáðàçîì, ïîëó÷åíà êëàññèôèêàöèÿ ïî àëãîðèòìè÷åñêîé ðàçðåøèìîñòè
ïðîáëåìû �-ýêâèâàëåíòíîñòè.
1. ×ÀÑÒÈ×ÍÎ ÊÎÌÌÓÒÀÒÈÂÍÛÅ ÏÎËÓÃÐÓÏÏÛ
Åñëè X — àëôàâèò, òî ïîëóãðóïïó âñåõ ñëîâ â àëôàâèòå X , âêëþ÷àÿ è ïóñòîå
ñëîâî, îáîçíà÷èì FX , à ïîëóãðóïïó âñåõ n-êîìïîíåíòíûõ âåêòîðîâ-ñëîâ — F
X
n .
Ïóñòü G — ïîëóãðóïïà ñ åäèíèöåé, ïîðîæäåííàÿ ìíîæåñòâîì îáðàçóþùèõ
Y y yn� �{ , , }1 . Îíà íàçûâàåòñÿ ñâîáîäíîé ÷àñòè÷íî êîììóòàòèâíîé ïîëóãðóïïîé,
åñëè çàäàåòñÿ êîíå÷íûì ÷èñëîì îïðåäåëÿþùèõ ñîîòíîøåíèé âèäà y y y yi j j i� [5].
Ïóñòü K: F FY
n�
{ , }0 1
— ãîìîìîðôèçì, îïðåäåëåííûé íàä ïîëóãðóïïîé FY è
ñîïîñòàâëÿþùèé ñëîâàì èç FY n-êè ñëîâ â áèíàðíîì àëôàâèòå {0, 1} [6]. Íà îáðà-
çóþùèõ FY ãîìîìîðôèçì K çàäàåòñÿ ðàâåíñòâîì K yi i n i( ) ( , , )� �� �1 , ãäå
� ij i j j
i j j i
i j
e y y y y
y y y y
�
�
�
�
�
�
1
0
, ,
, ,
, .
åñëè
åñëè
åñëè
Ïðè ýòîì K e e e( ) ( ,... , )� .
Ëåììà 1 [6]. Ïóñòü y yi j, — îáðàçóþùèå G, y yi j , g y yi j1 � , g y yj i2 � —
ýëåìåíòû G, ïîëó÷åííûå â ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèè ïîëóãðóïïû G ê îáðà-
çóþùèì y yi j, . Òîãäà g g K y y K y yi j j i1 2� � �( ) ( ) .
Ýòî óòâåðæäåíèå ïîçâîëÿåò ðàññìàòðèâàòü ãîìîìîðôèçì K êàê îòîáðàæåíèå,
äåéñòâóþùåå íå òîëüêî íà ïîëóãðóïïå FY , íî è íà ÷àñòè÷íî êîììóòàòèâíîé ïîëó-
ãðóïïå G.
Íà ìíîæåñòâå îáðàçóþùèõ Y çàäàåòñÿ ëèíåéíûé ïîðÿäîê [6], îáîçíà÷àåìûé � ,
êîòîðûé ñîâïàäàåò ñ ïîðÿäêîì ïåðå÷èñëåíèÿ îáðàçóþùèõ (ëåêñèêîãðàôè÷åñêèì ïî-
ðÿäêîì). Îòíîøåíèå � èñïîëüçóåòñÿ äàëåå äëÿ óïîðÿäî÷åíèÿ ïðåäñòàâëåíèé ýëåìåí-
òîâ G è îïðåäåëåíèÿ èõ êàíîíè÷åñêîãî ïðåäñòàâëåíèÿ. Ïóñòü h FY� . Ìàñêîé âõîæäå-
íèé îáðàçóþùåé y Y� â ñëîâî h íàçûâàåòñÿ ñëîâî èç íóëåé è åäèíèö, ïîëó÷àþùååñÿ
èç h â ðåçóëüòàòå çàìåíû âñåõ âõîæäåíèé îáðàçóþùåé y íà 1, à âñåõ âõîæäåíèé
îñòàëüíûõ îáðàçóþùèõ — íà 0. Åñëè ðàññìàòðèâàòü ìàñêè íå òîëüêî êàê ñëîâà â àë-
ôàâèòå {0, 1}, íî è êàê öåëûå äâîè÷íûå ÷èñëà, òî ïîÿâëÿåòñÿ âîçìîæíîñòü ñðàâíè-
âàòü èõ. Áóäåì ñ÷èòàòü, ÷òî ëåêñèêîãðàôè÷åñêèé ïîðÿäîê çàäàåò ïîðÿäîê ñðàâíåíèÿ
äâîè÷íûõ ïðåäñòàâëåíèé äëÿ îáðàçóþùèõ. Ïóñòü g — ýëåìåíò ïîëóãðóïïû G;
h q FY, � — åãî ïðåäñòàâëåíèÿ. Ñ÷èòàåòñÿ, ÷òî ïðåäñòàâëåíèå h ìåíüøå ïðåäñòàâëå-
íèÿ q h q, � , åñëè ñóùåñòâóåò òàêàÿ îáðàçóþùàÿ y, ÷òî: 1) åñëè y y� � , òî ìàñêè âõîæ-
äåíèé îáðàçóþùåé y� â ñëîâà h è q ñîâïàäàþò; 2) ìàñêà âõîæäåíèé îáðàçóþùåé y â
ñëîâî h ìåíüøå ìàñêè âõîæäåíèé ýòîé îáðàçóþùåé â ñëîâî q.
Ëåììà 2 [6]. Ëþáûå äâà ðàçíûå ïðåäñòàâëåíèÿ îäíîãî è òîãî æå ýëåìåíòà ïî-
ëóãðóïïû G ñðàâíèìû ïî îòíîøåíèþ � .
Èç ëåììû 2 ñëåäóåò, ÷òî äëÿ êàæäîãî ýëåìåíòà èç G ñóùåñòâóåò íàèìåíüøåå
ïðåäñòàâëåíèå, íàçûâàåìîå êàíîíè÷åñêîé ôîðìîé ýëåìåíòà, èíäóöèðîâàííîé ïî-
ðÿäêîì � íà ìíîæåñòâå îáðàçóþùèõ [6]. Îòìåòèì ñëåäóþùåå ñâîéñòâî êàíîíè÷åñ-
66 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
êîãî ïðåäñòàâëåíèÿ ýëåìåíòîâ: ëþáûå äâà ñèìâîëà, ñòîÿùèå ðÿäîì â êàíîíè÷åñêîì
ïðåäñòàâëåíèè, ëèáî íå ïåðåñòàíîâî÷íû, ëèáî ëåâûé ìåíüøå (â ñìûñëå ïîðÿäêà � )
ïðàâîãî.
Îïðåäåëÿåòñÿ îòíîøåíèå ýêâèâàëåíòíîñòè � íà ïîëóãðóïïå FY ñëåäóþùèì îá-
ðàçîì: åñëè w1è w2 — ñëîâà èç FY , òî w w1 2� òîãäà è òîëüêî òîãäà, êîãäà w1 ñîâïà-
äàåò ñ w2 ñ òî÷íîñòüþ äî îïðåäåëÿþùèõ ñîîòíîøåíèé.
Îòíîøåíèå � äåëèò FY íà íåïåðåñåêàþùèåñÿ êëàññû — êëàññû êîììóòàòèâ-
íîñòè. Î÷åâèäíî, ÷òî êàæäîìó ýëåìåíòó g èç G ñîîòâåòñòâóåò íåêîòîðûé êëàññ êîì-
ìóòàòèâíîñòè Cg , à ýëåìåíò èç Cg , ÿâëÿþùèéñÿ êàíîíè÷åñêîé ôîðìîé ýëåìåíòà g,
íàçîâåì ïðåäñòàâèòåëåì êëàññà êîììóòàòèâíîñòè Cg .
Ëåììà 3 [6]. Âñÿêàÿ ñâîáîäíàÿ ÷àñòè÷íî êîììóòàòèâíàÿ ïîëóãðóïïà ñ n îáðà-
çóþùèìè èçîìîðôíà íåêîòîðîé ïîäïîëóãðóïïå ïðÿìîãî ïðîèçâåäåíèÿ n ñâîáîä-
íûõ ïîëóãðóïï ñ äâóìÿ îáðàçóþùèìè.
Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ýòîé ëåììû â [6] îïóùåíî êàê î÷åâèäíîå.
Çäåñü îíî ïðèâîäèòñÿ, ïîñêîëüêó ñîäåðæèò íåêîòîðûå ðàññóæäåíèÿ, èñïîëüçóåìûå
â äàëüíåéøåì.
Èç ëåììû 1 ñëåäóåò, ÷òî ãîìîìîðôèçì K ìîæíî ðàññìîòðåòü íà ïîëóãðóïïå G.
Ëåììà 3 ïîêàçûâàåò, ÷òî ïîëóãðóïïà G èçîìîðôíà ñâîåìó ãîìîìîðôíîìó îáðàçó
K G( ) . Äîêàçàòåëüñòâî ïðîâîäèòñÿ èíäóêöèåé ïî äëèíå êàíîíè÷åñêîé ôîðìû.
Ïóñòü f g G, � . Èç îïðåäåëåíèÿ ãîìîìîðôèçìà ñëåäóåò, ÷òî K f K g( ) ( )� �
� �f g äëÿ îáðàçóþùèõ ïîëóãðóïïû G.
Ïðåäïîëîæèì, ÷òî ëåììà âåðíà äëÿ ïðîèçâîëüíûõ f , g G� , äëÿ êîòîðûõ äëèíû
êàíîíè÷åñêèõ ôîðì ðàâíû �. Ïîêàæåì, ÷òî ëåììà âåðíà è â òîì ñëó÷àå, êîãäà äëèíà
êàíîíè÷åñêèõ ôîðì f , g G� ðàâíà � � 1.
Ïóñòü, íàîáîðîò, K f K g( ) ( )� , íî f g . Ðàññìîòðèì êîìïîíåíòó � i âåêòîðà
K f n( ) ( , , )� � �� � �1 , êîòîðàÿ íå ÿâëÿåòñÿ ïóñòîé è íà÷èíàåòñÿ ñ ñèìâîëà «1».
Äîïóñòèì, ÷òî ýòà êîìïîíåíòà ñîîòâåòñòâóåò îáðàçóþùåé yi . Ïðåäïîëîæèì, ÷òî
«1» è ñàìûå ëåâûå ñèìâîëû «0» êîìïîíåíò, ñîîòâåòñòâóþùèõ îáðàçóþùèì, íå
êîììóòàòèâíûì ñ yi , óäàëåíû, à ðåçóëüòàò îáîçíà÷èì � � �� � �� �( , , )1 n .
Ñîãëàñíî ïîñòðîåíèþ
ãîìîìîðôèçìà K ñóùåñòâó-
þò f �è g G� � , äëèíû êàíîíè-
÷åñêèõ ôîðì êîòîðûõ ðàâíû
� è f f yi� � , g g yi� � è
K f K g( ) ( )� � � � �� . Íî òîã-
äà ñîãëàñíî ïðåäïîëîæåíèþ
èíäóêöèè f g� � � è, ñëåäîâà-
òåëüíî, f g� . Ïîñëåäíåå
ïðîòèâîðå÷èò ïðåäïîëîæå-
íèþ, ÷òî f g .
Ðàññìîòðèì ïðèìåð. Ïóñòü çàäàíî ìíîæåñòâî îáðàçóþùèõ Y a b c d� { , , , } ñ ñî-
îòíîøåíèÿìè ac ca� , ad da� , bc cb� , bd db� , cd dc� . Ïîñòðîèì ãîìîìîðôèçì K :
F FY �
{ , }0 1
4 : K a e e( ) ( , , , )� 1 0 , K b( ) � ( , , , )0 1 e e , K c e e e( ) ( , , , )� 1 , K d e e e( ) ( , , , )� �1
� ( , , , )e e e 1 . Ëåãêî çàìåòèòü, ÷òî K ac( ) � � �K a K c e( ) ( ) ( , , , )1 0 1 K c K a( ) ( ) �
� K ca( ) , òîãäà êàê K ab e e( ) ( , , , )� 10 01 è K ba e e( ) ( , , , )� 01 10 (ðèñ. 1) .
Íèæå ïðèâåäåí àëãîðèòì CFBuilder (Canonical Form Builder), êîòîðûé ïî ïðî-
èçâîëüíîìó âåêòîðó — îáðàçó ãîìîìîðôèçìà K : F FY
n�
{ , }0 1
, ñòðîèò êàíîíè÷åñêóþ
ôîðìó ýëåìåíòà g G� .
Àëãîðèòì CFBuilder. Åñëè K — âåêòîð, òî åãî êîìïîíåíòó i îáîçíà÷èì K i[ ] ,
à ÷èñëî êîìïîíåíò âåêòîðà — �( )K . Âåêòîð, èñïîëüçóåìûé äëÿ õðàíåíèÿ çíà÷åíèÿ
ãîìîìîðôíîãî îáðàçà K w( ) ñëîâà w, w FY� , îáîçíà÷èì K .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 67
Ðèñ. 1
Êëàññû
êîììóòàòèâíîñòè
begin;
// 1. Âõîä: êîíå÷íûé âõîäíîé àëôàâèò Y , ìíîæåñòâî C âñåõ îïðåäåëÿþùèõ
// ñîîòíîøåíèé âèäà y y y yi j j i� , y y Yi j, � , i j Y, { , , | |}� �1 , i j , âåêòîð K .
// Ïðåäïîëàãàåòñÿ, ÷òî âõîíîå çíà÷åíèå âåêòîðà K êîððåêòíî, ò.å. ñîâïàäàåò ñ
// ãîìîìîðôíûì îáðàçîì íåêîòîðîãî ñëîâà èç FY .
input K;
input Y;
input C;
// Íà÷àëüíîå çíà÷åíèå ðåçóëüòàòà — ïóñòîå ñëîâî.
assign ResultWord = e;
// Èòåðàöèÿ àëãîðèòìà.
while (K e e �( , , ))
{
// 2. Âûáèðàåì ìèíèìàëüíûé èíäåêñ òàêèõ êîìïîíåíò âåêòîðà K ,
// êîòîðûå íà÷èíàþòñÿ ñ «1». Óäàëÿåì «1» èç êîäà êîìïîíåíòû,
// ñîîòâåòñòâóþùåé ýòîìó èíäåêñó.
for (i = 1, …, |Y|)
{
// i — èíäåêñ êîìïîíåíòû, íà÷èíàþùåéñÿ ñ «1».
if ((K[i])[1] = 1)
{
erase (K[i])[1] from K[i];
break;
}
}
// 3. Âûáèðàåì ñèìâîë â àëôàâèòå, ñîîòâåòñòâóþùèé ïîëó÷åííîìó èíäåêñó.
// Äîáàâëÿåì åå ñïðàâà ê ðåçóëüòàòó.
assign s = Y[i];
add s to ResultWord;
// 4. Îïðåäåëÿåì ìíîæåñòâî Letters ñèìâîëîâ, íå êîììóòàòèâíûõ ñ
// âûáðàííûì ñèìâîëîì àëôàâèòà.
assign Letters = {y | y �Y; {sy = ys} �C};
// 5. Îïðåäåëÿåì ìíîæåñòâî èíäåêñîâ äëÿ âñåõ ñèìâîëîâ â Letters.
for (� �y Letters)
{
add j, that Y [j] = y to Indices;
}
// 6. Äëÿ êàæäîãî èíäåêñà j � Indices óäàëÿåì ñòàðøèé ðàçðÿä äâîè÷íîãî
// êîäà êîìïîíåíòû j âåêòîðà K, åñëè îí íà÷èíàåòñÿ ñ «0».
for (� �j Indices)
{
erase (K[j])[1] from K[j];
}
}
// 7. Âûâîäèì ðåçóëüòàò.
output ResultWord;
end;
Ðàññìîòðèì ðàáîòó ýòîãî àëãîðèòìà íà ïðèìåðå. Âîçüìåì ñëîâî w daba� , K w( ) �
= (101, 010, å, 1). Êëàññ êîììóòàòèâíîñòè ñëîâà w — { , , , }adba abda abad daba . Èç K �
= (101, 010, å, 1) àëãîðèòì ñíà÷àëà âûáèðàåò ïåðâóþ êîìïîíåíòó K[1] = 101, ñîîò-
âåòñòâóþùóþ ñèìâîëó a â àëôàâèòå Y . Ñèìâîë, íå êîììóòàòèâíûé ñ a, — ýòî b,
ñëåäîâàòåëüíî, K � (01, 10, å, 1). Çàòåì àëãîðèòì âûáèðàåò âòîðóþ êîìïîíåíòó,
ñîîòâåòñòâóþùóþ b.  ýòîì ñëó÷àå K � (1, 0, å, 1). Àëãîðèòì âûáèðàåò a:
K � (å, å, å, 1), çàòåì d: K � (å, å, å, å). Èòàê, ïîëó÷àåì ñëîâî abad, ÿâëÿþùååñÿ
ïðåäñòàâèòåëåì êëàññà êîììóòàòèâíîñòè { , , , }adba abda abad daba .
68 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
Ëåììà 4. Àëãîðèòì CFBuilder êîððåêòåí. Äëÿ ïðîèçâîëüíîãî âåêòîðà
K K ww � ( ) îí ïîëó÷àåò êàíîíè÷åñêóþ ôîðìó ýëåìåíòà g G� , ïðåäñòàâëÿþùóþ
ñëîâî w â ïîëóãðóïïå FY .
Äîêàçàòåëüñòâî. Çàìåòèì, ÷òî åñëè âåêòîð K � (å, …, å), òî àëãîðèòì âûâîäèò
ïóñòîå ñëîâî, íå âõîäÿ â ãëàâíûé öèêë.
Ñôîðìóëèðóåì íåêîòîðûå î÷åâèäíûå ïðåäóñëîâèÿ äëÿ ãëàâíîãî öèêëà àëãî-
ðèòìà, âûòåêàþùèå èç ïîñòðîåíèÿ ãîìîìîðôèçìà K:
1) K e e �( , , ), �( )K n� ;
2) � � �i j n, { , , }1 , i j , y y y yi j j i :
2.1) K i K j[ ] [ ] ,
2.2) ( [ ])[ ] ( [ ])[ ]K i K j1 1 1 0� � � ,
( [ ])[ ] !K i j1 0� � � �, j n�� �{ , , }1 , i j �,
y y y yi j j i� � , ( [ ])[ ]K j� �1 1,
2.3) � �( [ ]) ( [ ])K i K j� ;
3) � � � � � � � i n K i j n y y y yi j j i{ , , }( [ ])[ ] { , , }1 1 1 1
( [ ])[ ]K j 1 0� ;
4) �( )ResultWord � 0
(òåïåðü, ÷òîáû äîêàçàòü êîððåêòíîñòü àëãîðèòìà CFBuilder, ïîêàæåì, ÷òî äëÿ
ïðîèçâîëüíîé èòåðàöèè èìåþò ìåñòî ñëåäóþùèå èíâàðèàíòû öèêëà):
5) ResultWord it ResultWord it y K ii it[ ] [ ] ( [ ])[ ]� � � �1 1 1 è � � �j n{ , , }1
( [ ])[ ]K j i jit 1 1� � � , K i K i K i nit it it� � �1 2[ ] ( [ ])[ ] ( [ ])[ ] , � �( [ ]) ( [ ])K i K iit it� � �1 1;
6) ResultWord it ResultWord it y K ii it[ ] [ ] ( [ ])[ ]� � �1 1 1 è � � �j n{ , , }1
( [ ])[ ]K jit 1 0� , y y y y K j K j K j ni j j i it it it � � ��1 2[ ] ( [ ])[ ] ( [ ])[ ] ,
� �it itK j K j� � �1 1( [ ]) ( [ ]) .
Èíâàðèàíò 5) îçíà÷àåò, ÷òî âñåãäà âûáèðàåòñÿ ìèíèìàëüíûé èíäåêñ êîìïî-
íåíò âåêòîðà K , êîòîðûå íà÷èíàþòñÿ ñ «1». Çàòåì «1» óäàëÿåòñÿ è ñèìâîë àëôà-
âèòà, ñîîòâåòñòâóþùèé âûáðàííîìó èíäåêñó, âûáèðàåòñÿ è äîáàâëÿåòñÿ ñïðàâà ê
ResultWord â êàæäîé èòåðàöèè. Èñòèííîñòü èíâàðèàíòà î÷åâèäíûì îáðàçîì ñëåäó-
åò èç ñåìàíòèêè øàãîâ 2 è 3 àëãîðèòìà ñ ó÷åòîì ïðåäóñëîâèÿ 3).
Èíâàðèàíò 6), â ñâîþ î÷åðåäü, îçíà÷àåò, ÷òî ïåðâûé ñèìâîë êàæäîé êîìïîíåí-
òû, ñîîòâåòñòâóþùåé ñèìâîëó â àëôàâèòå, íå êîììóòàòèâíîìó ñ ïîñëåäíèì ñèìâî-
ëîì ResultWord, óäàëÿåòñÿ. Ñîãëàñíî ïðåäóñëîâèþ 2) óäàëÿåìûé ñèìâîë — ýòî
«0». Èñòèííîñòü æå èíâàðèàíòà 6) âûòåêàåò èç ñåìàíòèêè øàãîâ 5 è 6 àëãîðèòìà.
Èç èñòèííîñòè èíâàðèàíòîâ 5) è 6) ñëåäóåò, ÷òî íà÷àëüíûé âåêòîð K áóäåò
ïðåîáðàçîâàí â K e e� �( , , ) ÷åðåç êîíå÷íîå ÷èñëî èòåðàöèé.
Ñîãëàñíî èíâàðèàíòó 5) ïîðÿäîê âûáîðà ñèìâîëîâ ñîîòâåòñòâóåò ïîðÿäêó ñèì-
âîëîâ â àëôàâèòå. Ñëåäîâàòåëüíî, ëþáûå äâà ñèìâîëà, ñòîÿùèå ðÿäîì, ëèáî íå ïå-
ðåñòàíîâî÷íû, ëèáî ëåâûé ìåíüøå (â ñìûñëå ïîðÿäêà � ) ïðàâîãî. Òàêèì îáðàçîì,
ResultWord ÿâëÿåòñÿ êàíîíè÷åñêîé ôîðìîé.
2. ÏÐÎÁËÅÌÀ ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉ
 ÊÎÌÌÓÒÀÒÈÂÍÎÌ ÀËÔÀÂÈÒÅ
Ïóñòü A Y S F sR � , , , ,� 0 — äåòåðìèíèðîâàííûé àâòîìàò, ðàñïîçíàþùèé â òî÷íîñòè
ðåãóëÿðíîå âûðàæåíèå R âî âõîäíîì àëôàâèòå Y , | |Y n� , ñ ìíîæåñòâîì ñîñòîÿíèé S ,
ôóíêöèåé ïåðåõîäîâ �, ìíîæåñòâîì çàêëþ÷èòåëüíûõ ñîñòîÿíèé F è íà÷àëüíûì ñîñòîÿ-
íèåì s0 . Ïðåäïîëîæèì òàêæå, ÷òî çàäàíî ðàçáèåíèå àëôàâèòà Y íà íåïåðåñåêàþùèåñÿ
êëàññû êîììóòàòèâíîñòè, â êàæäîì èç êîòîðûõ ñîäåðæèòñÿ ïî îäíîìó ñèìâîëó:
Y Y Yi n� � �... , | |Yi � 1, i n� 1,... , . Ïîêàæåì, ÷òî â ýòîì ñëó÷àå ïðîáëåìà �-ýêâèâà-
ëåíòíîñòè ðåãóëÿðíûõ âûðàæåíèé àëãîðèòìè÷åñêè ðàçðåøèìà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 69
Ââåäåì ïîíÿòèå ñëåäîâ âûïîëíåíèÿ çàäàííîãî àâòîìàòà A íà ìíîãîìåðíîé
ëåíòå. Ïóñòü N � {0, 1, …}. Ìíîæåñòâî N n íàçûâàåòñÿ n-ìåðíîé ëåíòîé [6, 7],
ýëåìåíòû ìíîæåñòâà N n — n-êè âèäà ( ,... , )� �1 n — ÿ÷åéêàìè ëåíòû, à ÷èñëà
� �1 ,... , n — êîîðäèíàòàìè ñîîòâåòñòâóþùåé ÿ÷åéêè. ß÷åéêà (0, …, 0) íàçûâàåòñÿ
íà÷àëüíîé. ß÷åéêó a n1 11 1� �( , , )� � íàçîâåì ïðåäøåñòâåííèöåé ÿ÷åéêè
a n2 21 2� �( , , )� � , åñëè îäíà èç êîîðäèíàò a1 ìåíüøå ñîîòâåòñòâóþùåé
êîîðäèíàòû a2 íà åäèíèöó, à âñå îñòàëüíûå êîîðäèíàòû îáåèõ ÿ÷ååê ñîâïàäàþò.
Ââåäåì ñïåöèàëüíûé ïðåäèêàò äëÿ ïðåäñòàâëåíèÿ îòíîøåíèÿ ïðåäøåñòâîâàíèÿ è
îáîçíà÷èì åãî � , � ( , )a a1 2 èñòèííî òîãäà è òîëüêî òîãäà, êîãäà a1 ÿâëÿåòñÿ
ïðåäøåñòâåííèöåé a 2 . Ââåäåì òàêæå äðóãîé ïðåäèêàò � j , � j a a( , )1 2 èñòèííî
òîãäà è òîëüêî òîãäà, êîãäà � ( , )a a1 2 èñòèííî è ÿ÷åéêè a1, a2 îòëè÷àþòñÿ
çíà÷åíèÿìè êîîðäèíàòû j.
Ìíîæåñòâî âñåõ ïîäìíîæåñòâ ìíîæåñòâà ñîñòîÿíèé S àâòîìàòà A îáîçíà÷èì
2S , à ìíîæåñòâî âñåõ ïðåäøåñòâåííèö ÿ÷åéêè a — P a( ) .
Îñíîâûâàÿñü íà ôóíêöèè ïåðåõîäîâ � àâòîìàòà A, íà ìíîæåñòâå 2S îïðåäåëèì
ôóíêöèþ ïåðåõîäîâ � ñëåäóþùèì îáðàçîì: �({ , , }, ) { ( , ),s s y s ym i1 1 1� � ��
... , ( , )}� s ym i , y Yi � , s Sj � , j m� �1, , , { , , }s sm
S
1 2� � .
Îòîáðàæåíèå �À
n SN: � 2 áóäåì íàçûâàòü ìíîæåñòâîì ñëåäîâ âûïîëíåíèÿ
àâòîìàòà A òîãäà è òîëüêî òîãäà, êîãäà:
1) �À s( , , ) { }0 0 0� � , P( ,... , )0 0 � � ;
2) � � �a N n \ { , , }0 0 , P a a a aj
j
j( ) { | ( , )( ) ( )�
pred pred
� èñòèííî, j n nk� �1 , , , k n� },
� � �À À
n
n À
n
n
a a y a yk
k
( ) ( ( ), ) ... ( ( ),
( ) ( )� � �
pred pred
1
1
� � ) .
Êîíå÷íîå ïîäìíîæåñòâî ñëåäîâ âûïîëíåíèÿ, ñîäåðæàùåå âñå ÿ÷åéêè, ó
êîòîðûõ ñóììà êîîðäèíàò êàæäîé ÿ÷åéêè ìåíüøå èëè ðàâíà n �1, íàçîâåì ñëîâîì
ñëåäîâ (âûïîëíåíèÿ) äëèíû k. Ìíîæåñòâî âñåõ ñëîâ ñëåäîâ îáîçíà÷èì � A ,
ìíîæåñòâî âñåõ ÿ÷ååê, èñïîëüçîâàííûõ â äàííîì ñëîâå ñëåäîâ �, — U� .
×àñòü ñëîâà ñëåäîâ �, ñóììà êîîðäèíàò ÿ÷ååê êîòîðîé ðàâíà k, íàçîâåì äèàãî-
íàëüþ k ñëîâà ñëåäîâ � è îáîçíà÷èì dk ( )� . Äëèíà dk ( )� ðàâíà k � 1, äëèíà �( )�
ñëîâà ñëåäîâ � — êîëè÷åñòâó ñîäåðæèìûõ äèàãîíàëåé.
Äëÿ äàííîãî ñëîâà ñëåäîâ � îïðåäåëèì ïóòü p a ap pm
�
1
... , m � 1, a Upj
� � ,
j m� �{ , , }1 , êàê ïîñëåäîâàòåëüíîñòü ÿ÷ååê, äëÿ êîòîðûõ � ( ... )a ap pv v� 1
,
v m� � �1 1, , .
Åñòåñòâåííî ñâÿçàòü ñ ïóòåì p a ap pm
�
1
... åãî õàðàêòåðèñòèêó � p �
�
�
y yp pm1 1
... , ãäå y Yp ii
� , i �{1, ..., n}, j �{1, ..., m�1}, òîãäà è òîëüêî òîãäà, êîãäà
êîîðäèíàòà i óâåëè÷èâàåòñÿ íà 1 â ÿ÷åéêå a pj� 1
ïî ñðàâíåíèþ ñ ÿ÷åéêîé a pj
.
Ïóòü p a ap pm
�
1
... íàçîâåì ïîëíûì, åñëè a p1
= (0, …, 0). Ñêàæåì, ÷òî ïîëíûé
ïóòü p a ap pm
�
1
... ïðèíèìàåòñÿ àâòîìàòîì A, åñëè �A pa
m
( ) ñîäåðæèò çàêëþ÷è-
òåëüíîå ñîñòîÿíèå àâòîìàòà A. Êîîðäèíàòû ÿ÷åéêè a pm
íàçîâåì êàíîíè÷åñêîé ôîð-
ìîé ïîëíîãî ïóòè p a ap pm
�
1
... .
Äëÿ äàííîãî àâòîìàòà A ìíîæåñòâî âñåõ ïóòåé, ïðèíèìàåìûõ àâòîìàòîì A, â
ñëîâå ñëåäîâ � îáîçíà÷èì APA (� , à ìíîæåñòâî èõ êàíîíè÷åñêèõ ôîðì —
CFAPA (� .
Ãðàôè÷åñêîå ïðåäñòàâëåíèå ñëîâà ñëåäîâ è åãî äèàãîíàëåé ïðèâåäåíî íà ðèñ. 2 .
Ïóñòü àâòîìàòû A1 è A2 ðàñïîçíàþò â òî÷íîñòè ðåãóëÿðíûå âûðàæåíèÿ R1 è
R2 ñîîòâåòñòâåííî, à S1, S 2 — èõ ìíîæåñòâà ñîñòîÿíèé. Ïðåäïîëîæèì òàêæå, ÷òî
k s� �2 1, ãäå S S S� max{| | , | |}1 2 , �1 è �2 — ñëîâa ñëåäîâ, � �( ) ( )� �1 2� � k.
Ëåììà 5. CF CFAP APA A1 1 2 2( ) ( )� �� � R1~ R2 (�).
Äîêàçàòåëüñòâî. Ñíà÷àëà ïîêàæåì, ÷òî CF CFAP APA A1 1 2 2( ) ( )� �� � R1~ R2 (�).
70 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
Ïðåäïîëîæèì, ÷òî R1íå �-ýêâèâàëåíòíî R2 è â ñëîâàõ �
è �2 íå ñóùåñòâóåò
ïóòè äëèíû k, êîòîðûé ïðèíèìàåòñÿ àâòîìàòîì A1, íî íå ïðèíèìàåòñÿ àâòîìàòîì
A2 , èëè, íàîáîðîò, êîòîðûé ïðèíèìàåòñÿ àâòîìàòîì A2 , íî íå ïðèíèìàåòñÿ àâòîìà-
òîì A1.
 ñèëó ïðåäïîëîæåíèÿ ñóùåñòâóåò ïîëíûé ïóòü p a ap pm
�
1
... äëèíû, áîëüøåé
k, m k� , êîòîðûé ïðèíèìàåòñÿ îäíèì èç àâòîìàòîâ, ñêàæåì A1, íî íå ïðèíèìàåòñÿ
àâòîìàòîì A2 .
Ýòî îçíà÷àåò, ÷òî �A pa
m1
( ) ñîäåðæèò çàêëþ÷èòåëüíîå ñîñòîÿíèå àâòîìàòà A1,
òîãäà êàê �A pa
m2
( ) íå ñîäåðæèò çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ àâòîìàòà A2 . Ïîñêîëüêó
m k� , ñóùåñòâóåò äâå ÿ÷åéêè a è a� â ïóòè p, òàêèå, ÷òî ñóììà êîîðäèíàò ÿ÷åéêè a�
áîëüøå ñóììû êîîðäèíàò ÿ÷åéêè a, � �A Aa a
1 2
( ) ( )� � è p a à à ap pm
� � � ��
1
.
Ïóñòü � p� — õàðàêòåðèñòèêà ïîäïóòè p à a pm
�� �� ïóòè p è �� � � ��p à a —
ïóòü îò ÿ÷åéêè a äî ÿ÷åéêè ��a , èìåþùèé òó æå õàðàêòåðèñòèêó � p�. Î÷åâèäíî, ÷òî
òàêîé ïóòü ñóùåñòâóåò. Îáîçíà÷èì ���p ïîäïóòü ïóòè p, êîòîðûé íà÷èíàåòñÿ ñ a p1
è
îêàí÷èâàåòñÿ ïðåäøåñòâåííèöåé ÿ÷åéêè a. Êîíêàòåíàöèþ äâóõ ïóòåé ���p è ��p
îáîçíà÷èì p p pnew � ��� ��. Åãî äëèíà ìåíüøå äëèíû íà÷àëüíîãî ïóòè p. Î÷åâèäíî,
÷òî �A a
1
( )�� ñîäåðæèò çàêëþ÷èòåëüíîå ñîñòîÿíèå àâòîìàòà A1, a �A a
2
( )�� íå ñîäåð-
æèò çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ àâòîìàòà A2 . Åñëè äëèíà ïóòè pnew áîëüøå k, òî
âûïîëíÿåì ïðîöåäóðó, îïèñàííóþ âûøå, äî òåõ ïîð, ïîêà íå ïîëó÷èì ïóòü äëèíû,
íå ïðåâûøàþùåé k. Íî ýòî ïðîòèâîðå÷èò íà÷àëüíîìó ïðåäïîëîæåíèþ î òîì, ÷òî
íå ñóùåñòâóåò òàêîãî ïóòè â ñëîâàõ ñëåäîâ �1 è �2 , êîòîðûé ïðèíèìàëñÿ áû îäíèì
èç àâòîìàòîâ, íî íå ïðèíèìàëñÿ áû äðóãèì.
Ïîñêîëüêó óòâåðæäåíèå R1~ R2 (��� CF CFAP APA A1 1 2 2( ) ( )� �� î÷åâèäíî, ëåì-
ìà äîêàçàíà.
3. ÏÐÎÁËÅÌÀ ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉ
 ÍÅÊÎÌÌÓÒÀÒÈÂÍÎÌ ÀËÔÀÂÈÒÅ
Êàê îòìå÷àëîñü â íà÷àëå ñòàòüè, ïðè äîêàçàòåëüñòâå òàêæå áóäåì èñïîëüçîâàòü ïî-
íÿòèå ìíîãîìåðíîé ëåíòû, ââåäåííîå â ïðåäûäóùåì ðàçäåëå. Îïðåäåëåíèÿ ïîíÿ-
òèé ïðåäøåñòâåííèöû è ïóòè áóäóò èçìåíåíû. Ñôîðìóëèðóåì è äîêàæåì ëåììó î
ðàçðåøèìîñòè ïðîáëåìû ýêâèâàëåíòíîñòè ðåãóëÿðíûõ âûðàæåíèé â íåêîììóòàòèâ-
íîì àëôàâèòå. Ýòî òàêæå èçâåñòíûé ðåçóëüòàò [4], äîêàçàííûé äðóãèì ñïîñîáîì.
Ïðîàíàëèçèðóåì ñëó÷àé, êîãäà | |Y � 2 .
Ïóñòü Y y y� { , }1 2 , y y y y1 2 2 1 . Ðàññìîòðèì äâóìåðíóþ ëåíòó N 2 . Èñïîëüçóÿ
áèíàðíóþ êîäèðîâêó, ïðèâåäåííóþ â ðàçä. 1: (1, 0) äëÿ y1 è (0, 1) äëÿ y2 è ò.ä., ïî-
ëó÷èì ñëåäóþùåå ñîîòâåòñòâèå ìåæäó ñëîâàìè FY è ÿ÷åéêàìè N 2 : K e( ) ( , )� 0 0 ,
K y( ) ( , )1 1 0� , K y( ) ( , )2 0 1� , K y y( ) ( , ) ( , )1 1 11 00 3 0� � , K y y( ) ( , ) ( , )1 2 10 01 2 1� � ,
K y y( ) ( , ) ( , )2 1 01 10 1 2� � , K y y( ) ( , ) ( , )2 2 00 11 0 3� � , ... (ðèñ. 3).
Òàêèì îáðàçîì, ñëåäû âûïîëíåíèÿ îïðåäåëÿþòñÿ ñ ïîìîùüþ äèàãîíàëåé ëåíòû è
ñëåäóþùåãî àëãîðèòìà äâèæåíèÿ: øàã 0 — äèàãîíàëü ñ íîìåðîì 0, øàã i � 1— äèàãî-
íàëü ñ íîìåðîì di
i� 2 .  ýòîì ñëó÷àå íîìåð äèàãîíàëè íå ñîâïàäàåò ñ íîìåðîì øàãà.
Ñîîòâåòñòâåííî, ñëåäû âûïîëíåíèÿ ñâÿçàíû òîëüêî ñ ÿ÷åéêàìè îòìå÷åííûõ
äèàãîíàëåé.  òî æå âðåìÿ â ýòîì ñëó÷àå ìíîæåñòâî ñîñòîÿíèé äëÿ äàííîé ÿ÷åéêè
ëåíòû ñîñòîèò òîëüêî èç îäíîãî ñîñòîÿíèÿ è êàæäàÿ ÿ÷åéêà èìååò ëèøü îäíó ïðåä-
øåñòâåííèöó. Êîîðäèíàòû ïðåäøåñòâåííèöû ïîëó÷àþòñÿ óäàëåíèåì ñàìîé ëåâîé
åäèíèöû è ñàìîãî ëåâîãî íóëÿ èç êîîðäèíàò äàííîé ÿ÷åéêè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 71
Ðèñ. 2
y3
y2y1
Àíàëîãè÷íî îïðåäåëåíèþ â ðàçä. 2 ïóòü p a ap pm
�
1
... , m � 1, a Upj
� � ,
j m� �{ , , }1 , ðàññìàòðèâàåòñÿ êàê ïîñëåäîâàòåëüíîñòü ÿ÷ååê ïåðå÷èñëåííûõ äèàãî-
íàëåé, ãäå � ( , )a ap pv v� 1
, v m� � �1 1, , .
Ïîíÿòèÿ ïîëíîãî ïóòè, ïðèíèìàåìîãî ïóòè è êàíîíè÷åñêîé ôîðìû îïðåäåëÿ-
þòñÿ òàê æå, êàê â ðàçä. 2. Ïîíÿòèå õàðàêòåðèñòèêè äëÿ äàííîãî ïóòè p îòëè÷àåòñÿ
îò ïîíÿòèÿ õàðàêòåðèñòèêè, ïðèâåäåííîãî â ðàçä. 2, ñëåäóþùèì: ðàçíèöà êîîðäè-
íàò íå ðàâíà åäèíèöå, à ÿâëÿåòñÿ ïåðåìåííîé è ðàâíà 2i äëÿ øàãà i. Ïîñêîëüêó äëÿ
äàííîãî ñëó÷àÿ ðàññìàòðèâàåòñÿ áèíàð-
íîå ïðåäñòàâëåíèå êîîðäèíàò, òî ñîîò-
âåòñòâóþùèì îáðàçîì ìåíÿåòñÿ è ïðåä-
ñòàâëåíèå êàíîíè÷åñêîé ôîðìû. Ðàñ-
ñìàòðèâàþòñÿ ñëîâà ñëåäîâ,
îïðåäåëÿåìûå îãðàíè÷åíèåì íà èõ äëè-
íó: 20 , 2 20 1� , . . .
, 2 2 2 2 10 1 1� � �� � ��k k , ãäå k s� 2| |
(ðèñ. 4).
Àíàëîãè÷íî ëåììå 5 ôîðìóëèðóåò-
ñÿ è äîêàçûâàåòñÿ ëåììà 6 äëÿ ñëîâ ñëå-
äîâ �1 è �2 äëèíû k s� �2 1, ãäå
S S S� max{| | , | |}1 2 . Èäåÿ äîêàçàò-
åëüñòâà àíàëîãè÷íà èäåå äîêàçàòåëüñòâà
ëåììû 5.
Ëåììà 6.
CF CFAP APA A1 1 2 2( ) ( )� �� � R1~ R2 (�� .
Äîêàçàòåëüñòâî. Äëèíà k ñëîâ ñëåäîâ äîñòàòî÷íà, ÷òîáû ïðîâåñòè äîêàçàò-
åëüñòâî àíàëîãè÷íî äîêàçàòåëüñòâó ëåììû 5, òàê êàê â ýòîì ñëó÷àå ìíîæåñòâî ñî-
ñòîÿíèé äëÿ êàæäîé ÿ÷åéêè ñîäåðæèò ëèøü îäíî ñîñòîÿíèå, à ÷èñëî ðàññìàòðèâàå-
ìûõ äèàãîíàëåé ðàâíî k.
Cëó÷àé, êîãäà | |Y � 2 , ïðèâîäèò òîëüêî ê óâåëè÷åíèþ ðàçìåðíîñòè ëåíòû, ò.å.
ðàçìåðíîñòü ëåíòû ñîâïàäàåò ñ | |Y .
72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
Ðèñ. 4
Ðèñ. 3
Ïðåäïîëîæèì, ÷òî R1íå �-ýêâèâàëåíòíî R2 è â ñëîâàõ �
è �2 íå ñóùåñòâóåò
ïóòè äëèíû k, êîòîðûé ïðèíèìàåòñÿ àâòîìàòîì A1, íî íå ïðèíèìàåòñÿ àâòîìàòîì
A2 , èëè, íàîáîðîò, êîòîðûé ïðèíèìàåòñÿ àâòîìàòîì A2 , íî íå ïðèíèìàåòñÿ àâòîìà-
òîì A1.
 ñèëó ïðåäïîëîæåíèÿ ñóùåñòâóåò ïîëíûé ïóòü p a ap pm
�
1
... äëèíû, áîëüøåé
k, m k� , êîòîðûé ïðèíèìàåòñÿ îäíèì èç àâòîìàòîâ, ñêàæåì A1, íî íå ïðèíèìàåòñÿ
àâòîìàòîì A2 .
Ýòî îçíà÷àåò, ÷òî �A pa
m1
( ) ñîäåðæèò çàêëþ÷èòåëüíîå ñîñòîÿíèå àâòîìàòà A1,
òîãäà êàê �A pa
m2
( ) íå ñîäåðæèò çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ àâòîìàòà A2 . Ïîñêîëüêó
m k� , ñóùåñòâóåò äâå ÿ÷åéêè a è a� â ïóòè p, òàêèå, ÷òî ñóììà êîîðäèíàò ÿ÷åéêè a�
áîëüøå ñóììû êîîðäèíàò ÿ÷åéêè a, � �A Aa a
1 2
( ) ( )� � è p a à à ap pm
� � � ��
1
.
Ïóñòü � p� — õàðàêòåðèñòèêà ïîäïóòè p à a pm
�� �� ïóòè p è �� � � ��p à a —
ïóòü îò ÿ÷åéêè a äî ÿ÷åéêè ��a , èìåþùèé òó æå õàðàêòåðèñòèêó � p�. Î÷åâèäíî, ÷òî
òàêîé ïóòü ñóùåñòâóåò. Îáîçíà÷èì ���p ïîäïóòü ïóòè p, êîòîðûé íà÷èíàåòñÿ ñ a p1
è
îêàí÷èâàåòñÿ ïðåäøåñòâåííèöåé ÿ÷åéêè a. Êîíêàòåíàöèþ äâóõ ïóòåé ���p è ��p
îáîçíà÷èì p p pnew � ��� ��. Åãî äëèíà ìåíüøå äëèíû íà÷àëüíîãî ïóòè p. Î÷åâèäíî,
÷òî �A a
1
( )�� ñîäåðæèò çàêëþ÷èòåëüíîå ñîñòîÿíèå àâòîìàòà A1, a �A a
2
( )�� íå ñîäåð-
æèò çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ àâòîìàòà A2 . Åñëè äëèíà ïóòè pnew áîëüøå k, òî
âûïîëíÿåì ïðîöåäóðó, îïèñàííóþ âûøå, äî òåõ ïîð, ïîêà íå ïîëó÷èì ïóòü äëèíû,
íå ïðåâûøàþùåé k. Íî ýòî ïðîòèâîðå÷èò íà÷àëüíîìó ïðåäïîëîæåíèþ î òîì, ÷òî
íå ñóùåñòâóåò òàêîãî ïóòè â ñëîâàõ ñëåäîâ �1 è �2 , êîòîðûé ïðèíèìàëñÿ áû îäíèì
èç àâòîìàòîâ, íî íå ïðèíèìàëñÿ áû äðóãèì.
Ïîñêîëüêó óòâåðæäåíèå R1~ R2 (��� CF CFAP APA A1 1 2 2( ) ( )� �� î÷åâèäíî, ëåì-
ìà äîêàçàíà.
3. ÏÐÎÁËÅÌÀ ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉ
 ÍÅÊÎÌÌÓÒÀÒÈÂÍÎÌ ÀËÔÀÂÈÒÅ
Êàê îòìå÷àëîñü â íà÷àëå ñòàòüè, ïðè äîêàçàòåëüñòâå òàêæå áóäåì èñïîëüçîâàòü ïî-
íÿòèå ìíîãîìåðíîé ëåíòû, ââåäåííîå â ïðåäûäóùåì ðàçäåëå. Îïðåäåëåíèÿ ïîíÿ-
òèé ïðåäøåñòâåííèöû è ïóòè áóäóò èçìåíåíû. Ñôîðìóëèðóåì è äîêàæåì ëåììó î
ðàçðåøèìîñòè ïðîáëåìû ýêâèâàëåíòíîñòè ðåãóëÿðíûõ âûðàæåíèé â íåêîììóòàòèâ-
íîì àëôàâèòå. Ýòî òàêæå èçâåñòíûé ðåçóëüòàò [4], äîêàçàííûé äðóãèì ñïîñîáîì.
Ïðîàíàëèçèðóåì ñëó÷àé, êîãäà | |Y � 2 .
Ïóñòü Y y y� { , }1 2 , y y y y1 2 2 1 . Ðàññìîòðèì äâóìåðíóþ ëåíòó N 2 . Èñïîëüçóÿ
áèíàðíóþ êîäèðîâêó, ïðèâåäåííóþ â ðàçä. 1: (1, 0) äëÿ y1 è (0, 1) äëÿ y2 è ò.ä., ïî-
ëó÷èì ñëåäóþùåå ñîîòâåòñòâèå ìåæäó ñëîâàìè FY è ÿ÷åéêàìè N 2 : K e( ) ( , )� 0 0 ,
K y( ) ( , )1 1 0� , K y( ) ( , )2 0 1� , K y y( ) ( , ) ( , )1 1 11 00 3 0� � , K y y( ) ( , ) ( , )1 2 10 01 2 1� � ,
K y y( ) ( , ) ( , )2 1 01 10 1 2� � , K y y( ) ( , ) ( , )2 2 00 11 0 3� � , ... (ðèñ. 3).
Òàêèì îáðàçîì, ñëåäû âûïîëíåíèÿ îïðåäåëÿþòñÿ ñ ïîìîùüþ äèàãîíàëåé ëåíòû è
ñëåäóþùåãî àëãîðèòìà äâèæåíèÿ: øàã 0 — äèàãîíàëü ñ íîìåðîì 0, øàã i � 1— äèàãî-
íàëü ñ íîìåðîì di
i� 2 .  ýòîì ñëó÷àå íîìåð äèàãîíàëè íå ñîâïàäàåò ñ íîìåðîì øàãà.
Ñîîòâåòñòâåííî, ñëåäû âûïîëíåíèÿ ñâÿçàíû òîëüêî ñ ÿ÷åéêàìè îòìå÷åííûõ
äèàãîíàëåé.  òî æå âðåìÿ â ýòîì ñëó÷àå ìíîæåñòâî ñîñòîÿíèé äëÿ äàííîé ÿ÷åéêè
ëåíòû ñîñòîèò òîëüêî èç îäíîãî ñîñòîÿíèÿ è êàæäàÿ ÿ÷åéêà èìååò ëèøü îäíó ïðåä-
øåñòâåííèöó. Êîîðäèíàòû ïðåäøåñòâåííèöû ïîëó÷àþòñÿ óäàëåíèåì ñàìîé ëåâîé
åäèíèöû è ñàìîãî ëåâîãî íóëÿ èç êîîðäèíàò äàííîé ÿ÷åéêè.
Àíàëîãè÷íî îïðåäåëåíèþ â ðàçä. 2 ïóòü p a ap pm
�
1
... , m � 1, a Upj
� � ,
j m� �{ , , }1 , ðàññìàòðèâàåòñÿ êàê ïîñëåäîâàòåëüíîñòü ÿ÷ååê ïåðå÷èñëåííûõ äèàãî-
íàëåé, ãäå � ( , )a ap pv v� 1
, v m� � �1 1, , .
Ïîíÿòèÿ ïîëíîãî ïóòè, ïðèíèìàåìîãî ïóòè è êàíîíè÷åñêîé ôîðìû îïðåäåëÿ-
þòñÿ òàê æå, êàê â ðàçä. 2. Ïîíÿòèå õàðàêòåðèñòèêè äëÿ äàííîãî ïóòè p îòëè÷àåòñÿ
îò ïîíÿòèÿ õàðàêòåðèñòèêè, ïðèâåäåííîãî â ðàçä. 2, ñëåäóþùèì: ðàçíèöà êîîðäè-
íàò íå ðàâíà åäèíèöå, à ÿâëÿåòñÿ ïåðåìåííîé è ðàâíà 2i äëÿ øàãà i. Ïîñêîëüêó äëÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 73
äàííîãî ñëó÷àÿ ðàññìàòðèâàåòñÿ áèíàð-
íîå ïðåäñòàâëåíèå êîîðäèíàò, òî ñîîò-
âåòñòâóþùèì îáðàçîì ìåíÿåòñÿ è ïðåä-
ñòàâëåíèå êàíîíè÷åñêîé ôîðìû. Ðàñ-
ñìàòðèâàþòñÿ ñëîâà ñëåäîâ,
îïðåäåëÿåìûå îãðàíè÷åíèåì íà èõ äëè-
íó: 20 , 2 20 1� , . . .
, 2 2 2 2 10 1 1� � �� � ��k k , ãäå k s� 2| |
(ðèñ. 4).
Àíàëîãè÷íî ëåììå 5 ôîðìóëèðóåò-
ñÿ è äîêàçûâàåòñÿ ëåììà 6 äëÿ ñëîâ ñëå-
äîâ �1 è �2 äëèíû k s� �2 1, ãäå
S S S� max{| | , | |}1 2 . Èäåÿ äîêàçàò-
åëüñòâà àíàëîãè÷íà èäåå äîêàçàòåëüñòâà
ëåììû 5.
Ëåììà 6.
CF CFAP APA A1 1 2 2( ) ( )� �� � R1~ R2 (�� .
Äîêàçàòåëüñòâî. Äëèíà k ñëîâ ñëåäîâ äîñòàòî÷íà, ÷òîáû ïðîâåñòè äîêàçàò-
åëüñòâî àíàëîãè÷íî äîêàçàòåëüñòâó ëåììû 5, òàê êàê â ýòîì ñëó÷àå ìíîæåñòâî ñî-
ñòîÿíèé äëÿ êàæäîé ÿ÷åéêè ñîäåðæèò ëèøü îäíî ñîñòîÿíèå, à ÷èñëî ðàññìàòðèâàå-
ìûõ äèàãîíàëåé ðàâíî k.
Cëó÷àé, êîãäà | |Y � 2 , ïðèâîäèò òîëüêî ê óâåëè÷åíèþ ðàçìåðíîñòè ëåíòû, ò.å.
ðàçìåðíîñòü ëåíòû ñîâïàäàåò ñ | |Y .
4. ÏÐÎÁËÅÌÀ ÝÊÂÈÂÀËÅÍÒÍÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉ
 ×ÀÑÒÈ×ÍÎ ÊÎÌÌÓÒÀÒÈÂÍÎÌ ÀËÔÀÂÈÒÅ
Êàê îòìå÷àëîñü ðàíåå, îáùèé ñëó÷àé ïðîáëåìû ýêâèâàëåíòíîñòè ðåãóëÿðíûõ âû-
ðàæåíèé â ÷àñòè÷íî êîììóòàòèâíîì àëôàâèòå àëãîðèòìè÷åñêè íåðàçðåøèì.
Ïóñòü àëôàâèò Y Yi
i
n
�
�1
� , ãäå | |Y1 2� , | |Yi � 1, i n� �2, , . Îáîçíà÷èì | |Y1 ñèìâî-
ëîì q. Ðàññìîòðèì ( )n q� �1 -ìåðíóþ ëåíòó N n q� �1; q ðàçìåðíîñòåé ëåíòû èñïîëü-
çóåòñÿ äëÿ ìîäåëèðîâàíèÿ äâèæåíèÿ ïî ñèìâîëàì èç Y1, à îñòàëüíûå n �1 — äëÿ
ìîäåëèðîâàíèÿ äâèæåíèÿ ïî ñèìâîëàì èç Yi , i n� �2, , . Íèæå ïðèâåäåíû íåêîòî-
ðûå îáîáùåíèÿ ðàññìîòðåííûõ ïîíÿòèé äëÿ äàííîãî ñëó÷àÿ.
Èñïîëüçóåì áèíàðíîå êîäèðîâàíèå êîîðäèíàò ÿ÷ååê àíàëîãè÷íî ðàññìîòðåí-
íûì â ðàçä. 1. Åñëè a n� ( ,... , )� �1 — ÿ÷åéêà, òî áèíàðíîå ïðåäñòàâëåíèå êîîðäè-
íàòû � i îáîçíà÷èì b i( )� , à äëèíó áèíàðíîãî ïðåäñòàâëåíèÿ, ò.å. êîëè÷åñòâî áè-
òîâ — | ( )|b i� . Ïóñòü ïîçèöèè áèíàðíîãî ïðåäñòàâëåíèÿ ïðîíóìåðîâàíû ñïðàâà
íàëåâî, íà÷èíàÿ ñ 0. Òîãäà íîìåð ñàìîãî ëåâîãî çíà÷èìîãî áèòà b i( )� , ò.å. ñàìîãî
ëåâîãî áèòà áèíàðíîãî ïðåäñòàâëåíèÿ, êîòîðûé ðàâåí åäèíèöå, îáîçíà÷èì
NMSB( )� i . Åñëè â b i( )� íåò åäèíèö, òî NMSB( )� i � 0 .
ß÷åéêà a n q1 11 1 1� � �( ,... , )� � íàçûâàåòñÿ ïðåäøåñòâåííèöåé ÿ÷åéêè a2 �
� � �( ,... , )� �21 2 1n q è ñîîòâåòñòâóþùèé ïðåäèêàò, îáîçíà÷àåìûé �( , )a a1 2 , èìååò
çíà÷åíèå èñòèíà òîãäà è òîëüêî òîãäà, êîãäà � � �j n{ , , }1 ,
k j j n q� � � � � � �1 1 1 1, , , , , , ÷òî � �1 2k k� , è
1) � �
�
2 1
1
0 2 1
j j
b j� � �
�| ( )|
, | ( )| | ( )|b jj b� �2 1 1� � , åñëè j k� ;
2) � �
�
2 1
1
0 2 1
j j
b j� � �
�| ( )|
, | ( )| | ( )|b jj b� �2 1 1� � , åñëè j k� è NMSB( )�2 j �
� | ( )|b j�2 ;
3) � �
�
2 1
1
1 2 1
j j
b j� �
�
*
| ( )|
, åñëè j k� è NMSB( )�2 j � | ( )|b j�2 .
74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
Ðèñ. 5
y1
y3
y2
Îòîáðàæåíèå �A : N n S� 2 íàçîâåì ìíîæåñòâîì ñëåäîâ âûïîëíåíèÿ àâòîìàòà
A òîãäà è òîëüêî òîãäà, êîãäà:
1) �A s( , , ) { }0 0 0� � , P( ,... , )0 0 � � ;
2) � � �a N n \ { , , }0 0 , P a a a aj
j
j( ) { , ( , )( ) ( )�
pred pred
� èñòèííî, j n nk� �1 , , ,
k n q� � �1}, � � �À À
n
n À
n
n
a a y a yk
k
( ) ( ( ), ) ... ( ( ),
( ) ( )� � �
pred pred
1
1
� � ) .
Êîíå÷íîå ïîäìíîæåñòâî ñëåäîâ âûïîëíåíèÿ, ñîäåðæàùåå âñå ÿ÷åéêè, ó êîòî-
ðûõ ñóììà êîîðäèíàò êàæäîé ÿ÷åéêè ìåíüøå èëè ðàâíà n �1, íàçîâåì ñëîâîì ñëå-
äîâ (âûïîëíåíèÿ) äëèíû k. Ìíîæåñòâî âñåõ ñëîâ ñëåäîâ îáîçíà÷èì � A , ìíîæåñòâî
âñåõ ÿ÷ååê, èñïîëüçîâàííûõ â äàííîì ñëîâå ñëåäîâ �, — U� .
×àñòü ñëîâà ñëåäîâ �, ñóììà êîîðäèíàò ÿ÷ååê êîòîðîé ðàâíà k, íàçîâåì äèàãî-
íàëüþ k ñëîâà ñëåäîâ � è îáîçíà÷èì dk �� . Äëèíà dk �� ðàâíà k � 1, äëèíà �(�
ñëîâà ñëåäîâ � — êîëè÷åñòâó ñîäåðæèìûõ äèàãîíàëåé.
Îïðåäåëèì ïóòü p a ap pm
�
1
... , m � 1, a Upj
� � , j m� �{ , , }1 , äëÿ äàííîãî ñëî-
âà ñëåäîâ � êàê ïîñëåäîâàòåëüíîñòü ÿ÷ååê, äëÿ êîòîðûõ �( , )a ap pv v� 1
, v m� � �1 1, , .
Äëÿ äàííîãî ïóòè p a ap pm
�
1
... ñëîâî � p p py y
m
�
�1 1
... â àëôàâèòå Y íàçîâåì
õàðàêòåðèñòèêîé ïóòè p òîãäà è òîëüêî òîãäà, êîãäà � � �j m{ , , }1 , i n q� � � �{ , , }1 1
(ðèñ. 5):
1) y Yp ij
� , i i ip j p j
� � �
�
1 1
1
� �[ ] [ ] ;
2) y Ypj
� 1 � � �
�
NMSB(� �p j p j
i b i
1
1[ ]) | ( [ ])| .
Ïóòü p a ap pm
�
1
... íàçîâåì ïîëíûì, åñëè a p1
� (0, …, 0). Ñêàæåì, ÷òî ïîëíûé
ïóòü p a ap pm
�
1
... ïðèíèìàåòñÿ àâòîìàòîì A, åñëè �A pa
m
( ) ñîäåðæèò çàêëþ÷è-
òåëüíîå ñîñòîÿíèå àâòîìàòà A. Êîîðäèíàòû ÿ÷åéêè a pm
íàçîâåì êàíîíè÷åñêîé ôîð-
ìîé ïîëíîãî ïóòè p a ap pm
�
1
... .
Äëÿ êàæäîãî àâòîìàòà A ìíîæåñòâî âñåõ ïðèíèìàþùèõñÿ ïóòåé â ñëîâå ñëå-
äîâ � îáîçíà÷èì APA (� , à ìíîæåñòâî èõ êàíîíè÷åñêèõ ôîðì — CFAPA (� .
Ïóñòü àâòîìàòû A1 è A2 ðàñïîçíàþò â òî÷íîñòè ðåãóëÿðíûå âûðàæåíèÿ R1 è
R2 ñîîòâåòñòâåííî, à S1, S 2 — èõ ìíîæåñòâà ñîñòîÿíèé. Ïðåäïîëîæèì òàêæå, ÷òî
k s� �2 1, ãäå S S S� max{| | , | |}1 2 , �
è �2 — ñëîâà ñëåäîâ, àâòîìàòîâ A1 è A2
äëèíû k.
Ëåììà 7. CF CFAP APA A1 1 2 2( ) ( )� �� � R1~ R2 (�� .
Äîêàçàòåëüñòâî ïðîâîäèòñÿ àíàëîãè÷íî äîêàçàòåëüñòâó ëåììû 5. Ñîãëàñíî
ðàññóæäåíèÿì, ïðîâåäåííûì â ïðåäûäóùåì ðàçäåëå, ñëîâî ñëåäîâ äëèíû 2 1
| |si �
äëÿ äàííîãî àâòîìàòà Ai ñ ìíîæåñòâîì ñîñòîÿíèé S i ñîäåðæèò âñå ïîëíûå ïóòè
êàê äëÿ «êîììóòàòèâíûõ», òàê è äëÿ «íåêîììóòàòèâíûõ» ðàçìåðíîñòåé. Â òî æå
âðåìÿ ðàññìîòðåíèå ïîëíûõ ïóòåé ñ ïîâòîðÿþùèìèñÿ ìíîæåñòâàìè ñîñòîÿíèé
ìîæíî ñâåñòè ê ðàññìîòðåíèþ ïîëíûõ ïóòåé ñ íåïîâòîðÿþùèìèñÿ ìíîæåñòâàìè
ñîñòîÿíèé, êàê â ëåììå 5.
Òåîðåìà. Ïóñòü Y — ÷àñòè÷íî êîììóòàòèâíûé àëôàâèò, ðàçáèòûé íà íåïåðå-
ñåêàþùèåñÿ ïîäìíîæåñòâà ñèìâîëîâ ñî ñëåäóþùèìè ñâîéñòâàìè:
1) ëþáûå äâà ñèìâîëà èç ðàçíûõ ïîäìíîæåñòâ ïåðåñòàíîâî÷íû, à ëþáûå äâà
ñèìâîëà èç îäíîãî è òîãî æå ïîäìíîæåñòâà íå ïåðåñòàíîâî÷íû;
2) â ðàçáèåíèè ñóùåñòâóåò ëèøü îäíî ïîäìíîæåñòâî ñ ìîùíîñòüþ, áîëüøåé
åäèíèöû.
Ïðîáëåìà ýêâèâàëåíòíîñòè ðåãóëÿðíûõ âûðàæåíèé íàä ÷àñòè÷íî êîììóòàòèâ-
íîì àëôàâèòîì Y àëãîðèòìè÷åñêè ðàçðåøèìà.
Àâòîð âûðàæàåò ãëóáîêóþ áëàãîäàðíîñòü íàó÷íîìó ðóêîâîäèòåëþ ä-ðó ôèç.-ìàò.
íàóê, àêàäåìèêó À.À. Ëåòè÷åâñêîìó è ä-ðó ôèç.-ìàò. íàóê À.Á. Ãîäëåâñêîìó çà öåííûå
ñîâåòû è çàìå÷àíèÿ â ïðîöåññå íàïèñàíèÿ è ïîäãîòîâêè ðóêîïèñè ê ïå÷àòè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 75
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. À õ î À . , Ó ë ü ì à í Ä æ . Òåîðèÿ ñèíòàêñè÷åñêîãî àíàëèçà, ïåðåâîäà è êîìïèëÿöèè. Ò. 1. —
Ì.: Ìèð, 1978. — 612 ñ.
2. Ð å ä ü ê î Â . Í . Îá àëãåáðå êîììóòàòèâíûõ ñîáûòèé /// Óêð. ìàò. æóð. — 1964. — 16, ¹ 2. —
Ñ. 185–195.
3. Ò ó ç î â  . À . Ïðîáëåìû ðàçðåøåíèÿ äëÿ ãðàô-ñõåì ñ ïåðåñòàíîâî÷íûìè îïåðàòîðàìè. II //
Êèáåðíåòèêà. — 1971. — ¹ 5. — Ñ. 23–32.
4. R a b i n M . O . , S c o t t D . Finite automata and their decision problems // IBM Journ. of Res. and
Development. — 1959. — 3 (2). — Ð. 114–125.
5. P r e s t o n C . The Algebraic Theory of Semigroups // Amer. Math. Soc. — 1961. — N 7. — Ð. 148–159.
6. Ã î ä ë å â ñ ê è é À . Á . , Ë å ò è ÷ å â ñ ê è é À . À . , Ø ó ê ó ð ÿ í Ñ . Ê . Î ñâîäèìîñòè
ïðîáëåìû ôóíêöèîíàëüíîé ýêâèâàëåíòíîñòè ñõåì ïðîãðàìì íàä íåâûðîæäåííûì áàçèñîì ðàíãà åäèíèöà
ê ýêâèâàëåíòíîñòè àâòîìàòîâ ñ ìíîãîìåðíûìè ëåíòàìè // Êèáåðíåòèêà. — 1980. — ¹ 6. — Ñ. 1–7.
7. G r i g o r i a n H . A . , S h o u k o u r i a n S . K . The equivalence problem of multidimensional
multitape automata // Journ. of Comput. and System. Sci. — 2008. — 74, N 7. — P. 1131–1138.
Ïîñòóïèëà 06.11.2008
76 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
|