\documentstyle[12pt,russcorr]{article}
\hfuzz=1pt
\tolerance=1000
\emergencystretch=10pt

\def\BbbR{{\rm I\!R}} %reelle Zahlen
\def\BbbN{{\rm I\!N}} %natuerliche Zahlen
\def\BbbQ{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm
Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}}
\def\BbbZ{{\mathchoice {\hbox{$\sf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\sf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\sf\scriptstyle Z\kern-0.3em Z$}}
{\hbox{$\sf\scriptscriptstyle Z\kern-0.2em Z$}}}}

\newcommand{\limit}{\mathop{\rm limit}\limits}

\begin{document}
\date{}

\centerline{Детерминизация ординальных автоматов}

\medskip

Мы будем пользоваться принятым в теории множеств определением
ординалов из  которого  следует, что  каждый  ординал совпадает  с
множеством меньших ординалов.

Пусть $\Sigma $ --- конечный алфавит, а $\rho $  ---  ординал,  больший  нуля.
Назовем $\rho $-словом в  алфавите  любое  отображение $\alpha\colon\,\rho \setminus\{0\}\longmapsto \Sigma$ (по
техническим причинам  нам  удобно исключить  ноль). $\rho$-слова  будем
называть ординальными словами. Таким  образом, $\omega$-слова  ---  это  в
общепринятой терминологии сверхслова.
\par
Ординальным  автоматом  или,  кратко,  автоматом   называется
шестерка ${\cal A}=(\Sigma,Q,q_{0},T,F_{1},F_{2})$,  где $Q$  ---  конечное  множество
состояний автомата, $\Sigma $ --- входной алфавит автомата, $q_{0}\in Q$ --- начальное
состояние  автомата, $T\subset Q*\Sigma*Q\bigcup P(Q)*\Sigma *Q$   ---   множество   переходов
автомата, $F_{1}\subset Q$ --- множество заключительных  состояний  автомата,
$F_{2}\subset  P(Q)$  ---  множество   заключительных   макросостояний   автомата.
Переходы вида $(q_{0},a,q'_{0})$, $q_{0},q'_{0}\in Q$  будем  называть  непредельными
переходами, а переходы вида $(A,a,q'_{0})$, $A\subset Q$, $q'_{0}\subset Q$  ---  предельными
переходами.
\par
Определим способ функционирования автомата $\cal A$  на $\rho $-слове $\alpha $  в
алфавите $\Sigma $ --- входном алфавите $\cal A$.
\par
Предходом  автомата  $\cal A$   на $\alpha $  называется  любое  отображение
${H\colon\,\longmapsto Q}$.       Пределом       предхода $H$        называется
limit~${H\rightleftharpoons \{q\in Q\mid\forall k<\rho\,\exists n<\rho\,(n>k\ \&\ H(n)=q)\}}$. Слово    ``предел''    будет
употребляться в работе и в обычном  смысле,  поэтому  для  предела
предхода мы выбрали нестандартное обозначение ``limit''.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Предход $H\colon\,\rho \longmapsto Q$ называется  ходом  автомата  $\cal A$   на $\alpha $  если
выполнены 3 условия:
\par
H1. $H(0)\ =\ {\rm начальное\ состояние\ автомата}\ {\cal A}$.
\par
H2.~Для всех $n<\rho $  тройка $(H(n), \alpha (n+1), H(n+1))$  является
переходом автомата $\cal A$.
\par
H3.~Для любого предельного ординала $\sigma <\rho $  тройка\\
$(\limit_{h\to \sigma}(H|\sigma),\,\alpha(\sigma),\,H(\sigma))$ является переходом автомата $\cal A$.
\par
Возможный  ход  автомата $\cal A$   на $\rho $-слове $\alpha $ является допускающим
ходом, если выполнено условие
\par
H4. $H(\rho -1)$ --- заключительное состояние $\cal A$  если $\rho $ --- непредельный
ординал и $\limit_{h\to rho} H$ ---  заключительное  макросостояние  $\cal A$  если $\rho $  ---
предельный ординал.
\par
Автомат называется детерминированным, если для любых $q\in Q$, $a\in \Sigma $
существует единственное $q'$ такое, что $(q,a,q')\in T$ и для любых $A\subset Q$,
$a\in \Sigma $ существует единственное $q'$ такое, что $(A,a,q')$ --- переход $\cal A$.
\par
Ясно, что детерминированный  автомат  на  каждом  ординальном
слове  имеет  ровно  один  возможный  ход.  На  рисунке  изображен
схематически  ход  автомата  на $\rho $-слове $\alpha $  для   непредельного $\rho $.

\begin{picture}(350,80)

\put(0,40){\line(1,0){25}}
\put(29,40){\line(1,0){25}}
\put(58,40){\line(1,0){45}}
\put(107,40){\line(1,0){30}}
\put(141,40){\line(1,0){50}}
\put(195,40){\line(1,0){45}}
\put(244,40){\line(1,0){50}}
\put(298,40){\line(1,0){45}}

\put(26,40){\bf .}
\put(55,40){\bf .}
\put(104,40){\bf .}
\put(138,40){\bf .}
\put(192,40){\bf .}
\put(241,40){\bf .}
\put(295,40){\bf .}

\put(95,45){\ldots}
\put(183,45){\ldots}
\put(296,45){\ldots}

\put(5,45){$\downarrow$}
\put(68,45){$\downarrow$}
\put(39,45){$\downarrow$}
\put(117,45){$\downarrow$}
\put(151,45){$\downarrow$}
\put(205,45){$\downarrow$}
\put(254,45){$\downarrow$}
\put(323,45){$\downarrow$}

\put(3,55){$H(0)$}
\put(66,55){$H(1)$}
\put(37,55){$H(2)$}
\put(110,55){$H(\omega)$}
\put(149,55){$H(\omega\!+\!1)$}
\put(203,55){$H(\omega\!+\!\omega)$}
\put(252,55){$H(\omega\!+\!\omega\!+\!1)$}
\put(321,55){$H(\rho\!-\!1)$}

\put(17,25){$\alpha(1)$}
\put(46,25){$\alpha(2)$}
\put(93,25){$\alpha(\omega)$}
\put(126,25){$\alpha(\omega\!+\!1)$}
\put(180,25){$\alpha(\omega\!+\!\omega)$}
\put(229,25){$\alpha(\omega\!+\!\omega\!+\!1)$}
\put(291,25){$\alpha(\rho\!-\!1)$}

\put(180,0){Рис. 1}

\end{picture}

\par
Пусть $H$ --- ход детерминированного автомата $\cal A$  на $\rho $-слове $\alpha $. Для
$n<\rho $ состояние $H(n)$ будем  называть  состоянием  автомата  $\cal A$  после
прочтения $n$ первых букв $\alpha $.
\par
Скажем, что автомат $\cal A$  допускает  ординальное  слово $\alpha $,  если
существует допускающий ход $\cal A$  на $\alpha $.  Ординальные  автоматы  назовем
$\rho $-эквивалентными, если они допускают одни и те же $\rho $-слова.
\par
ТЕОРЕМА.  {\it Для  любого  ординального  автомата  $\cal A$    существует
детерминированный ординальный автомат  $\cal B$, $\rho $-эквивалентный  $\cal A$   для
всех счетных ординалов $\rho $. Автомат $\cal B$  можно построить по  $\cal A$,  причем
количество состояний $\cal B$ есть $2^{2^{O(N)}}$, где $N$ ---  количество  состояний
$\cal A$.}
\par
Все  дальнейшее  является   доказательством   этой   теоремы.
Зафиксируем автомат ${\cal A}=(\Sigma,Q,\ldots)$.
\par
Прежде чем определить автомат $\cal B$, мы введем некоторые  понятия
и докажем некоторые леммы.
\par
Пусть $\rho $  ---  счетный  ординал,  больший  нуля,  а $\alpha $  это $\rho $-слово.
Зафиксируем $\rho $ и $\alpha $. Это мы делаем потому, что большинство  вводимых
понятий будет зависеть от $\alpha $ и  они  будут  громоздкими,  если  эту
зависимость учитывать. Конструкция автомата $\cal B$,  разумеется,  никак
от $\rho $ и $\alpha $ зависеть не будет.
\par
Назовем точкой любую пару $(i,q)$, $i<\rho$, $q\in Q$.  Точку $(0, q_{0})$
назовем    исходной.    Назовем    предельным     (соответственно,
непредельным) путем отображение $P$ вида $P\colon\,[m,k]\longmapsto Q$,  где $m,k<\rho$,
$m\le k$, $[m,k]\rightleftharpoons \{i<\rho\mid m\le i\le k\}$ (соответственно  вида $P\colon\,[m,k[\longmapsto Q$,  где
$m,k<\rho$, $m<k$, $k$ ---  предельный, $[m,k[\rightleftharpoons \{i<\rho\mid m\le i<k\}$),  удовлетворяющие
свойству H2  для  всех $\sigma \in [m,k-1]$ (соответственно, $\sigma \in [m,k[\,$)   и
свойству H3  для  всех $\sigma \in [m+1,k]$ (соответственно, $\sigma \in [m+1,k[\,$).
Конечные  и  бесконечные  пути  будем  называть   просто   путями.
Множество $[m,k]$ (соответственно $[m,\sigma [\,$)   назовем    областью
определения пути. Точку $(m,P(m))$ назовем началом пути, $m$ начальным
моментом пути, а $P(m)$ --- первым  состоянием  пути,  точку $(k,P(k))$
назовем концом пути, $k$ последним моментом пути, а $P(k)$  последним
состоянием  пути  (в  случае  конечного  пути).  Пути  с  областью
определения $M$ будем также называть $M$-путями. В случае бесконечного
пути ординал $\sigma $ назовем верхней гранью $P$. Если $P$ --- $[m,k]$-путь,  то
будем также говорить, что $P$ ---  путь  из  точки $(m,P(m))$  в  точку
$(k,P(k))$, или $P$ соединяет $(m,P(m))$ с $(k,P(k))$.
\par
Скажем,что  точка $(n,q)$  достижима  из  точки $(m,q')$,  если
имеется путь из $(m,q')$ в $(n,q)$. Скажем, что $M$-путь $P$ не выходит за
пределы макросостояния $A$, если $\forall n\in M\,P(n)\in A$. Пусть $P_{1}$  ---  конечный
путь, а $P_{2}$ --- любой путь, начало  которого  равно  концу  пути $P_{1}$.
Очевидным образом определяется конкатенация $P_{1}P_{2}$ путей $P_{1}$ и $P_{2}$.
\par
Первым основным понятием является  понятие  пучка  путей  или
просто пучка. Пучком называется любая тройка $\Pi=(i,q,A)$,  где $i<\rho$,
$q\in Q$, $A\subset Q$, и точка $(i,q)$ достижима из исходной точки.  Точку $(i,q)$
назовем началом пучка $\Pi$, а ординал $i$ --- начальным моментом пучка, $q$
--- начальным состоянием пучка, множество $A$ --- ограничителем пучка $\Pi$.
Множеством точек пучка $\Pi$ назовем множество $T(\Pi)$ всех точек $(n,q')$,
для которых существует  путь  из  начала  пучка  $\Pi$  в $(n,q')$,  не
выходящий за пределы  ограничителя  пучка  $\Pi$.  Множество  $T_{n}(\Pi)=
\{(n,q)\mid (n,q)\in T(\Pi)\}$ назовем $n$-м сечением  пучка  $\Pi$,  а  множество
$Q_{n}(\Pi)=\{q\mid (n,q)\in T(\Pi)\}$ назовем множеством состояний  пучка  $\Pi$  в
момент $n$. Скажем, что путь $P$ принадлежит пучку $\Pi$, если начало пути
$P$ принадлежит $T(\Pi)$ и $P$ не выходит за пределы  ограничителей  пучка
$\Pi$.
\par
Будем  пользоваться  ``$*$-символикой''.  Символ   $*$   на   месте
некоторого параметра обозначает,  что  этот  параметр  может  быть
любым. Например $[*,n]$-путь --- это любой путь с  последним  моментом
$n$, пучок $(*,*,A)$ --- любой пучок с ограничителем $A$ и т.д.
\par
Теперь определим другие два основных понятия: ``$n$ есть  момент
сброса пучка $\Pi$'' и ``накопление точки $(n,q)$ относительно  пучка  $\Pi$'',
или кратко ``$\Pi$-накопление $(n,q)$''. Но сначала определим $\Pi$-накопление
пути.  Пусть  $\Pi=(i,q,A)$  пучок.  Зафиксируем  некоторый   линейный
порядок на множестве $Q$.  Пусть $q_{1},\ldots,
q_{|A|}$  ---  состояния  из $A$,
занумерованные по порядку на $Q$. $\Pi$-накопление  пути $P\colon\,M\longmapsto Q$  это
такое максимальное число $m\le |A|$, что существуют $i_{1},\ldots,
i_{m}\in M$  такие,
что $i_{1}<i_{2}<\ldots
<i_{m}$ и $P(i_{1})=q_{1},\ldots,
P(i_{m})=q_{m}$. Если таких $m$ нет вовсе,
то накопление $P$ равно 0. Вообще далее максимум  элементов  пустого
множества считается равным 0.
\par
Перейдем к обещанным определениям. Пусть $n\ge i$, $(n,q)\in T(\Pi)$.
\par
1) $\Pi$-накопление точки $(n,q)$ равно наибольшему  из  накоплений
таких путей $P$,  ведущих  в  $(n,q)$,  принадлежащих  пучку  $\Pi$,  что
множество $[$начальный момент $P$; $n[$  не  содержит  моментов  сброса
пучка $\Pi$.
\par
2) $n$ является моментом сброса пучка $\Pi$, или просто сбросом  $\Pi$,
если $\Pi$-накопления всех точек из $T_{n}(\Pi)$ равны $|A|$, т.е.\ максимальны.
Будем говорить в таком случае, что $\Pi$ имеет в момент $n$ максимальное
накопление.
\par
Это является корректным определением трансфинитной  индукцией
по $n$.
\par
Нам будет удобнее распространить понятие $\Pi$-накопления на  все
точки, положив $\Pi$-накопление точки $(n,q)$,  не  принадлежащей  $T(\Pi)$,
равным $-1$.
\par
Следующая лемма, связывающая существование  пути  с  заданным
пределом $A$ с  существованием  пучка  с  неограниченным  множеством
сбросов, является основной для работы.  Подмножество  $B\subset \sigma $  назовем
неограниченным в $\sigma $, если $\forall k<\sigma\,\exists n<\sigma\,(n>k, n\in B)$.

ЛЕММА 1. {\it Пусть $\sigma $ --- счетный предельный ординал, $\sigma \le \rho$, и\\
$A\subset Q$.}

1)~{\it Если $P$ --- это $[*,\sigma [$-путь  с  пределом  $A$,  начальная  точка
которого достижима из исходной, то существует такое $k<\sigma $,  что  при
всех $n\ge k$, $n<\sigma $  пучок $(n, P(n), A)$  имеет  неограниченное  в $\sigma $
множество сбросов.}

2)~{\it Если пучок $\Pi=(*,*,A)$ имеет неограниченное в $\sigma $  множество
сбросов, то существует $[*,\sigma [$-путь  с  пределом  $A$,  принадлежащий
пучку $\Pi$.}
\par
ДОКАЗАТЕЛЬСТВО.   В    доказательстве     все     переменные
$n,k,m,n_{1},n_{2},\ldots$
 пробегают множество ординалов, меньших $\sigma $.
\par
1)~Пусть $P\colon\,[n_{0},\sigma [\longmapsto Q$  ---  путь  с  пределом  $A$   и   точка
${(n_{0},P(n_{0}))}$ достижима из исходной. Возьмем ${n_{1}>n_{0}}$ такое,  что ${\forall n\ge n_{1}\,
P(n)\in A}$. На множестве ${[n_{1},\sigma [}$ рассмотрим отношение эквивалентности $\sim$
следующим  образом: ${i\sim j}$,   если   найдется ${n\ge i,j}$   такое,   что
${Q_{n}(i,P(i),A) = Q_{n}(j,P(j),A)}$. Отношение $\sim$  транзитивно,  поскольку,
если $\Pi_{1}$ и $\Pi_{2}$ имеют одинаковые ограничители,  то ${Q_{n}(\Pi_{1}) = Q_{n}(\Pi_{2})}$
влечет ${Q_{k}(\Pi_{1}) = Q_{k}(\Pi_{2})}$ для всех ${k\ge n}$.  Докажем,  что ${i\sim k}$  и ${i<j<k}$
влечет ${i\sim j\sim k}$. Скажем, что пучок ${\Pi_{2} = (i_{2},q_{2},A_{2})}$ является  потомком
пучка ${\Pi_{1} = (i_{1},q_{1},A_{1})}$, если ${A_{2}\subset A_{1}}$, ${(i_{2},q_{2})\in T(\Pi_{1})}$. Это  определение
мы будем использовать и за пределами леммы 1.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Очевидно, что если $\Pi_{2}$ --- потомок  $\Pi_{1}$,  то  $T(\Pi_{2})\subset T(\Pi_{1})$.  Пусть
$i\sim k$, $i<j<k$. Положим  $\Pi_{1} = (i,P(i),A)$,  $\Pi_{2} = (j,P(j),A)$,  $\Pi_{3} =
(k,P(k),A)$.

Для $m,n\ge n_{1}$  точки $(m,P(m))$, $(n,P(n))$  соединимы  путем,  не
выходящим за пределы $A$ (именно частью пути $P$), следовательно $\Pi_{2}$  ---
потомок  $\Pi_{1}$,  а  $\Pi_{3}$  ---   потомок   $\Pi_{2}$.   Значит   для   всех ${n\ge k}$
${Q_{n}(\Pi_{3})\subset Q_{n}(\Pi_{2})\subset Q_{n}(\Pi_{1})}$, но так как при  всех  достаточно  больших $n$
${Q_{n}(\Pi_{3}) = Q_{n}(\Pi_{1})}$,  мы  получаем ${i\sim j\sim k}$.  Поэтому   каждый   класс
эквивалентности имеет вид $[m,n[$  или $[m,\sigma [$.  Докажем,  что  число
классов эквивалентности конечно и, следовательно, существует класс
эквивалентности    вида $[m,\sigma [$.    Допустим,    число    классов
эквивалентности  больше $|A|$.  Тогда  существуют   неэквивалентные
${k_{1}<k_{2}\ldots
<k_{|A|+1}}$.  В  последовательности  ${\Pi_{1} = (k_{1},P(k_{1}),A),\ldots,
\Pi_{|A|+1} = (k_{|A|+1},P(k_{|A|+1}),A)}$  каждый  пучок  является  потомком
предыдущего,   следовательно   для ${n=k_{|A|+1}}$    выполнено
${Q_{n}(\Pi_{1})\subset Q_{n}(\Pi_{2})\subset \ldots
\subset Q_{n}(\Pi_{|A|+1})\subset A}$. Последнее невозможно так  как  все
$Q_{n}(\Pi_{j})$ должны быть различны.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Итак,  мы   доказали,   что   существует   наибольший   класс
эквивалентности, т.е.\ для некоторого $n_{2}$, все ординалы большие $n_{2}$,
эквивалентны. Очевидно, можно считать $n_{2}\ge n_{1}$.
\par
Докажем,  что  при   всех $n\ge n_{2}$   пучок $(n,P(n),A)$   имеет
неограниченное в $\sigma $  множество  сбросов.  Допустим  противное:  при
некотором $n_{3}>n_{2}$  пучок  $\Pi=(n_{3},P(n_{3}),A)$  имеет  ограниченное  в $\sigma $
множество сбросов, т.е.\ существует $n_{4}>n_{3}$ такое, что  никакое $n\ge n_{4}$
не  является  моментом  сброса  $\Pi$.  Так  как  предел $P$  равен  $A$,
существует такое $n_{5}>n_{4}$, что $\Pi$-накопление пути $P = P|[n_{4},n_{5}]$  равно
$|A|$.

\begin{picture}(350,220)

\put(2,195){\line(1,0){96}}
\put(102,195){\line(1,0){76}}
\put(182,195){\line(1,0){116}}
\put(302,195){\line(1,0){58}}

\put(2,95){\line(1,0){96}}
\put(102,95){\line(1,0){121}}
\put(227,95){\line(1,0){66}}

\put(0,195){\bf .}
\put(99,195){\bf .}
\put(179,195){\bf .}
\put(299,195){\bf .}

\put(0,95){\bf .}
\put(99,95){\bf .}
\put(224,95){\bf .}
\put(294,95){\bf .}

\put(0,185){$\uparrow$}
\put(98,185){$\uparrow$}
\put(178,185){$\uparrow$}
\put(298,185){$\uparrow$}

\put(0,85){$\uparrow$}
\put(98,85){$\uparrow$}

\put(0,205){$(n_{0},P(n_{0}))$}
\put(85,205){$(n_{1},P(n_{1}))$}
\put(165,205){$(n_{2},P(n_{2}))$}
\put(285,205){$(n_{3},P(n_{3}))$}

\put(0,105){$(n_{3},P(n_{3}))$}
\put(90,105){$(n_{4},P(n_{4}))$}
\put(210,105){$(n_{5},P(n_{5}))$}
\put(285,105){$(n_{6},P(n_{6}))$}

\put(345,88){$Q_{n_{6}}(\Pi)$}

\put(180,10){Рис. 2}
\put(85,30){нет сбросов $\Pi$}
\put(0,45){пучка $\Pi$}
\put(85,45){места заведомо}
\put(0,60){начало}
\put(85,60){начиная с этого}
\put(104,80){путь с накоплением $|A|$}
\put(165,135){эквивалентности}
\put(85,150){предела $P$}
\put(165,150){шего класса}
\put(290,150){пучка $P$}
\put(0,165){начало $P$}
\put(85,165){начало}
\put(165,165){начало наиболь-}
\put(290,165){начало}

\end{picture}

\par
Поскольку $n_{3}\sim n_{5}$,  существует  такое $n_{6}>n_{5}$, что ${Q_{n_{6}}(\Pi) =
Q_{n_{6}}(n_{5},P(n_{5}),A)}$. Докажем, что  накопление  пучка  $\Pi$  в  момент $n_{6}$
максимально. Пусть $(n_{6},q)$ --- произвольная  точка  $T_{n_{6}}(\Pi)$.  Докажем,
что $\Pi$-накоп\-ление точки $(n_{6},q)$ равно $|A|$. Так как  отрезок $[n_{4},n_{6}]$
не содержит сбросов пучка $\Pi$,  достаточно  указать $[n_{4},n_{6}]$-путь  в
пучке $\Pi$ с накоплением $|A|$ и  последним  состоянием $q$. Этот  путь
будет конкатенацией путей $P_{1}$ и $P_{2}$, где $P_{1}$ --- это $P|[n_{4},n_{5}]$, а $P_{2}$  ---
любой путь в пучке $\Pi$, соединяющий $(n_{5},P(n_{5}))$ и $(n_{6},q)$. Такой  путь
существует,   поскольку ${q\in Q_{n_{6}}(\Pi)}$    и ${Q_{n_{6}}(\Pi)=Q_{n_{6}}(n_{5},P(n_{5}),A)}$.
Следовательно, ${q\in Q_{n_{6}}(n_{5},P(n_{5}),A)}$.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
2)~Пусть  пучок  $\Pi=(n_{0},q_{0},A)$  имеет  неограниченное  в $\sigma $
множество сбросов. Так как $\sigma $ ---  счетный  ординал,  существует
возрастающая   последовательность $n_{1},n_{2},n_{3},\ldots,
n_{i},\ldots$
  моментов
сброса пучка $\Pi$, неограниченная в $\sigma $.  Для  каждого $i\ge 1$  и  каждого
$q\in Q_{n_{i+1}}(\Pi)$ существует $[n_{i},n_{i+1}]$-путь $P$  в  пучке  $\Pi$  с  последним
состоянием $q$ и $n$-накоплением $|A|$. Зафиксируем один  такой  путь  и
обозначим  его $P_{i+1,q}$.  Для  каждого $q\in Q_{n_{1}}(\Pi)$  зафиксируем  в $n$
некоторый  путь,  соединяющий  точку $(n_{1},q)$  с   началом   пучка.
Обозначим этот путь  $P_{1,q}$.  Докажем,  что  существует  бесконечная
конкатенация $P = P_{1,q_{1}}P_{2,q_{2}}\ldots
P_{i,q_{i}}\ldots$,
 где $q_{i}\in Q_{n_{i}}(\Pi)$.  Тогда  $P$
очевидно имеет верхнюю грань $\sigma $ и предел $A$ и принадлежит $\Pi$.
\par
Применим лемму Кенига, утверждающую,  что  любое  бесконечное
дерево с конечными степенями вершин  имеет  бесконечную  ветвь.  В
нашем случае вершины дерева --- это  последовательность  путей  вида
$\{(n_{0},q_{0})\},P_{1,q_{1}},\ldots,
P_{i,q_{i}}$, где для  всех $j<i$  конец  $P_{j,q_{j}}$  равен
началу $P_{j+1,q_{j+1}}$, и пары вида  $(\{(n_{0},q_{0})\};P_{1,q})$.  Ребра  соединяют
последовательности с их продолжениями на один член. Степени вершин
ограничены $|A|+1$.  Корень  ---  это $\{(n_{0},q_{0})\}$.  Дерево  бесконечно,
потому что для всех $i\ge 1$, $q\in Q_{n_{i}}(\Pi)$  можно  построить,  двигаясь  от
конца к началу, путь вида $P_{1,q_{1}}P_{2,q_{2}}\ldots P_{i,q_{i}}$  с $q_{i}=q$,  Бесконечная
ветвь в этом дереве и есть нужный нам путь.
\par
Лемма доказана.
\par
Пусть $n\le \rho $.  Назовем $\le n$-пучком  (соответственно, $<n$-пуч\-ком)
любой пучок  с  начальным  моментом $\le n$ (соответственно $<n$).  На
$\le n$-пуч\-ках    (соответственно, $<n$-пуч\-ках)     введем     понятие
$\le n$-экви\-валентности (соответственно, $<n$-экви\-валеньности). Пусть  ${\Pi_{1}
= (i_{1},q_{1},A_{1})}$, ${\Pi_{2}=(i_{2},q_{2},A_{2})}$. Тогда ${\Pi_{1} \equiv_{\le n}\Pi_{2}}$ (соответственно  ${\Pi_{1}
\equiv_{\le n}\Pi_{2}}$), если выполнены условия
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Е1.~$A_{1}=A_{2}$.

Е2.~$\exists m\le n$ (соответственно $m<n$) такое, что $m\ge i_{1},i_{2}$ и $Q_{m}(\Pi_{1}) =
Q_{m}(\Pi_{2})$. Для случая $\le n$-эквивалентности это просто  означает,  что
$Q_{n}(\Pi_{1}) = Q_{n}(\Pi_{2})$.
\par
$<n$-эквивалентность  мы   будем   рассматривать   только   для
предельных $n$.
\par
Определим  на  пучках  полный  порядок.  Для  этого   линейно
упорядочим любым способом пары вида (состояние  $\cal A$,  макросостояния
автомата $\cal A$).
\par
Скажем, что  $\Pi_{1}<\Pi_{2}$,  если $i_{1}<i_{2}$,  или $i_{1}=i_{2}$  и $(q_{1},A_{1}) <
(q_{2},A_{2})$.
\par
Назовем $\le n$-пучок (соответственно, $<n$-пучок) $\Pi$ $\le n$-минимальным
(соответственно, $<n$-минимальным), если не  существует  меньшего  $\Pi$
пучка, $\le n$-эквивалентного (соответственно, $<n$-эквивалентного) пучку
$\Pi$.   Обозначим   $M\le n$ (соответственно   $M<n$)    множество    всех
$\le n$-минимальных $\le n$-пучков  (соответственно, $<n$).  Очевидно,   оба
множества конечны.
\par
СЛЕДСТВИЕ 1. {\it Пусть $n$ --- предельный ординал, $\sigma \le \rho $ и  пусть  $A\subset Q$.
Тогда следующие условия эквивалентны:}
\par
(1)~{\it Существует возможный ход $\cal A$ на $\sigma $-слове $\alpha|\sigma $ с пределом $A$.}
\par
(2)~{\it Существует $<\sigma $-минимальный  пучок  с  ограничителем  $A$  и
неограниченным в $\sigma $ множеством сбросов.}
\par
ДОКАЗАТЕЛЬСТВО. Импликация $(1)\Longrightarrow (2)$  следует  непосредственно
из леммы~2.
\par
Импликация  $(2)\Longrightarrow (1)$  следует   из   леммы~1   и   следующего
очевидного замечания: Если два пучка $<\sigma $-эквивалентны и один из них
имеет неограниченное в $\sigma $ множество сбросов, то и множество сбросов
другого неограничено в $\sigma $.
\par
Теперь  мы  можем  перейти  к  построению  детерминированного
автомата $\cal C$, $\rho $-эквивалентного  $\cal A$  для  всех  счетных  ординалов $\rho $.
Сначала рассмотрим простейший нетривиальный случай $\rho  = \omega $. Построим
автомат $\cal C'$, эквивалентный $\cal A$  на  $\omega$-словах.
\par
Первым делом мы, не определяя ни множества состояний  $\cal C'$,  ни
переходов $\cal C'$, укажем в какое состояние $\cal C'$  должен  перейти  после
прочтения $n$ первых букв  $\omega$-слова $\alpha $. Неформально, в момент $n$ автомат
$\cal C'$ хранит следующую информацию.
\par
1)~Множество $D_{n}$ всех состояний, достижимых в момент $n$ (т.е.\
таких состояний $q$, что точка $(n,q)$ достижима из исходной точки).
\par
2)~Для каждого $\le n$-минимального  пучка  $\Pi$  автомат  $\cal C$  хранит
ограничитель $\Pi$, $Q_{n}(\Pi)$ и  $\Pi$-накопления  в  момент $n$  состояний  из
$Q_{n}(\Pi)$. Назовем тройку (ограничитель $\Pi$, $Q_{n}(\Pi)$, $f_{n,\Pi})$,  где $f_{n,\Pi}$  ---
график функции $\Pi$-накопления состояния $q$ в момент $n$, $n$-срезом пучка
$\Pi$, и обозначим $I_{n}(\Pi)$.
\par
3)~Границу неподвижности в момент $n$,  определяемую  следующим
образом.  Номер  элемента $x$  в  конечном  линейно   упорядоченном
множестве $X$ определяется стандартным образом: нумерация начинается
с 1 и элементы нумеруются по порядку. Скажем, что пучок $\Pi$  из  $M_{\le n}$
(напомним, $M_{\le n}$ --- множество $\le n$-минимальности  пучков)  подвижен  в
момент $n$, если $\Pi\notin M_{\le n}$ или номер $\Pi$ в $M_{\le n}$ не равен номеру $\Pi$ в $M_{\le n}$ (а
значит,  меньше).  Пусть  $\Pi_{1},\ldots,
\Pi_{m}$  ---   все   пучки   из $M_{\le n}$,
занумерованные по порядку.
\par
Границей неподвижности в момент $n$ назовем максимальное  такое
$l$, что все  пучки  ${\Pi_{1},\ldots,
\Pi_{l}}$  неподвижны  в  момент $n$.  Обозначим
границу  неподвижности  в  момент $n$  через $\gamma _{n}$.  Итак,  определим
формально состояние, в которое автомат  $\cal C'$  должен  перейти  после
прочтения ${\alpha (1)\ldots
\alpha (n)}$. Назовем $n$-пред\-ставлением последовательность
${K_{n} = (D_{n}, I_{n}(\Pi_{1}), \ldots,
I_{n}(\Pi_{m}), \gamma _{n})}$,  где  ${\Pi_{1},\ldots,
\Pi_{m}}$  ---   все
${\le n}$-ми\-ни\-мальные пучки, занумерованные по порядку.  После  прочтения
${\alpha (1)\ldots
\alpha (n)}$   автомат   должен   перейти   в   состояние    равное
$n$-пред\-ставлению.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Определим множество состояний  автомата  $\cal C'$.  Назовем  срезом
любую тройку вида $(A,S,f)$, где $A\subset Q$, $S\subset A$, $f\colon\,\longmapsto \{0,\ldots,
|A|\}$.  Срез
имеет  максимальное  накопление,  если $\forall s\in S\,f(1) = |A|$.  Срезы
$(A_{1},S_{1},f_{1})$ и $(A_{2},S_{2},f_{2})$ эквивалентны, если $A_{1}=A_{2}$, $S_{1}=S_{2}$. Множество
состояний автомата $\cal C'$ состоит из всех последовательностей вида  $K=
(D,I_{1},\ldots,
I_{m},\gamma)$, где
\par
П1.~$D\subset Q$
\par
П2.~$\forall j\le m$ $I_{j}$ является срезом
\par
П3.~$\gamma \in {\BbbN}$, $\gamma \le m$
\par
П4.~Для всех $j,k\le m$, $j<>k$ срезы $A_{j}$ и $A_{k}$ не эквивалентны.
\par
Из-за свойства П4 число сотояний $\cal C'$ конечно. Верхнюю  границу
$2^{2^{O(N)}}$ мы докажем в  общем  случае.  Состояния  автомата  $\cal C$   будем
называть  представлениями.   Последовательности,   удовлетворяющие
свойствам  П1-П3  назовем  полупредставлениями.  Срез $I_{j}$   будем
называть $j$-м  срезом  представления  (состояния)  $K$  а  множество
$\{I_{1}\ldots
I_{m}\}$ назовем множеством срезов представления $K$.  Множество $D$
будем называть множеством достижимых состояний представления $K$,  а
множество $\{I_{1},\ldots,
I_{\sigma _{n}}\}$ назовем зоной  неподвижности  представления
$K$. Число $\gamma $ назовем границей неподвижности представления $K$.
\par
Теперь определим множество переходов $\cal C'$ так,  чтобы  прочитав
$\alpha (1)\ldots
\alpha (n)$,   автомат   $\cal C'$   перешел    в    состояние,    равное
$n$-представлению.
\par
Начальное  состояние $\cal C'$   ---   это   последовательность $(D,
I_{1},\ldots,
I_{m}, \gamma )$, где $D = \{q_{0}\}$, $q_{0}$  ---  начальное  состояние $\cal A$, $\gamma =0$,
$I_{1},\ldots,
I_{m}$ --- все срезы вида $(A,\{q_{0}\},\sigma_{A,q_{0}})$, где $q_{0}\in A\subset Q$,
$$
\sigma_{A,q}\colon\,\{q\}\longmapsto {\BbbN},\ \sigma_{A,q}(q) = \cases{1,\ {\rm если}\ q\ {\rm первый\ элемент} A;\cr 0,\ {\rm иначе,}}
$$
занумерованы  по  порядку: ${(A,\{q_{0}\},\sigma_{A,q_{0}})<(B,\{q_{0}\},\sigma_{B,q_{0}})}$,   если
${(q_{0},A)<(q_{0},B)}$ (напомним, что на парах $(q,A)$ зафиксирован  исходный
порядок).
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Определим  переходы  $\cal C'$.  Предельные  переходы  можно  взять,
очевидно, любыми. Определим  непредельные  переходы,  т.е.\ укажем
состояние  $K$,  в  которое  переходит  $\cal C'$   из   состояния   $K=
(D,I_{1},\ldots,
I_{m},\gamma)$ при чтении буквы $a$.  Представление  $K'$  получается
последовательным  применением  к  $K$  трех   процедур,   называемых
Преобразование,  Добавление   и   Сокращение.   Каждая   процедура
определена   на    полупредставлениях    и    дает    на    выходе
полупредставление.   При   этом   последовательность,   выдаваемая
процедурой Вычеркивание, удовлетворяет еще  и  свойству  П4,  т.е.\
является  представлением.  Процедура  Преобразование   имеет   еще
дополнительный  параметр  типа:  бинарное  отношение  на $Q$.   При
вычислении  состояния  $K'$  в  качестве  значения  этого  параметра
берется отношение $R_{0}=\{(q_{1},q_{2})\mid (q_{1}aq_{2})$  ---  переход ${\cal A} \}$,  однако  в
дальнейшем это будет не всегда так.  Теперь  определим  каждую  из
трех процедур. Пусть  $K=(D,I_{1},\ldots,
I_{m},Z)$, $I_{j}=(A_{j},S_{j},f_{j})$ --- исходное
полупредставление.
\par
Процедура Преобразование с параметром $R\subset Q*Q$ делает следующее.
\par
1)~Заменяет $D$ на $D' = \{q'\mid \exists q\in D\, (q,q')\in R\}$

2)~Заменяет $S_{j}$ на $S'_{j} = \{q' \mid \exists q\in S\, (q,q')\in R\}$

3)~Заменяет $f_{j}$ на функцию $f'_{j}\colon\,S'_{j}\longmapsto \{0,\ldots,
|A|\}$ определенную
так. $f'_{j}(q')$ равно максимуму по всем таким $q$, что $q\in S_{j}$ и $(q,q')\in R$,
\par
величины $s(q) = \cases{f_{j}(q)+1,\ {\rm  если\ номер}\ q'\ {\rm в}\ A_{j}\ {\rm равен}\ f_{j}(q)+1\cr f(q),\ {\rm иначе.}}$
\par
В результате 2) и 3) срез $I_{j} = (A_{j},S_{j},f_{j})$ заменен  на  срез ${I' =
(A_{j},S'_{j},f'_{j})}$.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Процедура  Добавление,   примененная   к   последовательности
${(D,I_{1},\ldots I_{m},\gamma)}$       дает               последовательность
${(D,I_{1},\ldots,I_{m},I_{m+1},\ldots,I_{m+l})}$, где ${I_{m+1},\ldots,I_{m+l}}$ --- занумерованы  по
порядку на парах $(q,A)$ все срезы вида ${(A,\{q\},\sigma_{A,q})}$, ${q\in D'}$, ${q\in A\subset Q}$.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Процедура Сокращение  делает  с  входной  последовательностью
$(D,I_{1},\ldots,
I_{m},\gamma)$ следующее. Для всех $j\le m$,  если  существует  такое
$k<j$,  что $I_{k}$  эквивалентно $I_{j}$,  то $I_{j}$  вычеркивается.  Затем $\gamma$
заменяется наибольшее такое $l$, что $\forall j\le l$ $j$-й срез не был вычеркнут.
\par
Множество переходов $\cal C'$ определено.  Нетрудно  проверить,  что
состояние $\cal C'$ после прочтения $\alpha(1)\ldots
\alpha(n)$ равно $n$-представлению.
\par
Заключительных состояний в  $\cal C'$  нет.  Прежде  чем  определить
заключительные  макросостояния  $\cal C'$  докажем  лемму.  Обозначим $b$
количество $<\omega$-минимальных пучков.
\par
ЛЕММА 2. 1)~{\it Нижний предел $\liminf\limits_{n\to\infty}\gamma_{n}$ равен $a$.}
\par
2)~{\it Существует такое $K<\omega $, что  при  всех $n\ge K$, $n<\omega $  первые $b$
пучков в $M_{\le n}$ --- это минимальные пучки.}
\par
ДОКАЗАТЕЛЬСТВО. Пусть $\Pi_{1},\ldots,\Pi_{b}$ --- все $<\omega $-минимальные  пучки,
занумерованные по  порядку.  Поскольку  пучков,  меньших  $\Pi_{b}$  лишь
конечное число, найдется такое $n_{0}$, что любой  пучок,  меньший  $\Pi_{b}$,
$n_{0}$-эквивалентен одному из  пучков  $\Pi_{1},\ldots,
\Pi_{b}$.  Это  означает,  что
первые $b$ пучков в $M_{\le n}$ при $n\ge n_{0}$ --- это $\Pi_{1},\ldots,
\Pi_{b}$. Положим $k = n_{0}$.
Утверждение~2) доказано.
\par
В частности, $\forall n>n_{0}\ \gamma_{n}\ge b$. Докажем, что $\forall l>n_{0}\ \exists n\ge l\ \gamma _{n}=b$.  Пусть
$l\ge n_{0}$. Если в $M_{\le l}$ ровно $b$  пучков,  то  доказывать  нечего.  Иначе,
пусть $\Pi$ --- это $(b+1)$-й пучок в $M_{\le l}$.  Так  как  $\Pi$  не $<\omega $-минимален,
существует такое $n>l$,  что  $\Pi$ $\le n$-эквивалентен  одному  из  пучков
$\Pi_{1},\ldots,
\Pi_{b}$. Пусть $n_{1}$ --- наименьшее такое $n$.  Тогда $\gamma _{n}=b$,  поскольку
все пучки с номерами, большими $b$,  подвижны  в  момент $n_{1}$.  Лемма
доказана.
\par
Определим множество заключительных макросостояний $\cal C'$. Пусть $\cal K$
--- макросостояние $\cal C'$, то  есть  некоторое  множество  представлений.
Назовем абсолютной границей неподвижности $\gamma({\cal K})$  макросостояния $\cal K$
минимум  границ  неподвижности   представлений   из $K$.   Назовем
абсолютной зоной неподвижности представления $K\in {\cal K}$ множество  срезов
$K$ с номерами $<\gamma({\cal K})$. Нам известно (по лемме~2),  что  если ${\cal K}=\limit_{n\to \infty}
K_{n}$,  то  абсолютная  граница  неподвижности ${\cal K}$  равна $b$ (числу
$<\omega $-минимальных  пучков),  причем  зона  абсолютной   неподвижности
любого состояния $K$ из ${\cal K}$ состоит из $n$-представлений $<\omega $-минимальных
пучков для $n$ таких, что $K_{n}=K$. Пэтому скажем, что ${\cal K}$  заключительно,
если существует $K\in {\cal K}$ такое, что некоторый срез из  зоны  абсолютной
неподвижности $K$  имеет  максимальное  накопление  и  ограничитель,
этого среза является заключительным макросостоянием автомата $\cal A$.

Очевидно, справедливо

СЛЕДСТВИЕ 2. {\it $\cal A$  допускает $\alpha $  тогда  и  только  тогда,  когда
макропредставление $\cal A$ $\limit_{n\to\infty} K_{n}$ заключительно.}
\par
Итак, случай $\rho  = \omega $ разобран. Перейдем к случаю  произвольного
счетного $\rho $. Усовершенствуем автомат $\cal C'$. Понятия подвижности пучка,
границы неподвижности в момент $n$ без изменения переносятся на  все
$n<\rho $. Обобщение леммы~2 на случай произвольных предельных ординалов
доказывается точно так же. Сформулируем его.
\par
ЛЕММА~3. {\it Для любого предельного ординала $\sigma \le \rho $ выполнено}
\par
1)~{\it $\liminf\limits_{n\to\infty} Z=b_{\sigma}$, где $b_{\sigma }$ --- число $<\sigma $-минимальных пучков}

2)~{\it Существует такое $n_{0}<\sigma $, что при всех $n<\sigma$, $n\ge n_{0}$  первых $b$
пучков в $M_{\le n}$ это $<\sigma $-минимальные пучки.}
\par
Напомним, что пучок $Pi_{2} = (i_{2},q_{2},A_{2})$ называется потомком пучка
$\Pi_{1} = (*,*,A_{1})$, если $A_{1}\supset A_{2}$ и $(i_{2},q_{2})\in T(\Pi_{1})$.  Будем  говорить,  что
пучок $\Pi_{2}$ $\le n$-связан с пучком $\Pi_{1}$, если существует пучок  $\Pi$,  который
$\le n$-эквивалентен $\Pi_{2}$ и является потомком $\Pi_{1}$. При этом $\le n$-накоп\-лением
пары  $(\Pi_{1},\Pi_{2})$  называется  величина $h_{n}(\Pi_{1},\Pi_{2})$  равная   максимуму
$\Pi$-накоп\-лению точки $(q,m)$ по всем таким $(q,m)$,  что  $\Pi_{2}$  не  имеет
сбросов на отрезке $[m,n]$ и существует потомок  $\Pi= (m,q,*)$  пучка
$\Pi_{1}$, $\le n$-экви\-валентный   $\Pi_{2}$.   Аналогично   определяется   понятие
$<n$-связанности и $<n$-накопления связи.
\par
Ясно, что если $n$ --- момент сброса пучка $\Pi_{1}$, то $h_{n}(\Pi_{1},\Pi_{2}) = 0$.
Легко видеть, что если $\Pi_{2}$ $\le n$-связан с $\Pi_{1}$ и $m\ge n$, то $\Pi_{2}$ $\le m$-связан  с
$\Pi_{1}$, причем, если отрезок $[n,m]$ не содержит сбросов  пучка  $\Pi_{1}$,  то
$h_{m}(\Pi_{1},\Pi_{2}) \ge  h_{n}(\Pi_{1},\Pi_{1})$. То есть функция $h_{n}(\Pi_{1},\Pi_{2})$ может уменьшаться
с ростом $n$ только становясь равной нулю.
\par
Теперь не определяя автомат $\cal C$, скажем,  какую  информацию  он
должен хранить после прочтения $n$ первых букв слова $\alpha$  ($n\le \rho$). Это
вся та информация, которую хранит $\cal C'$, и дополнительно информация о
связях  между $\le n$-минимальными  пучками   и $\le n$-накопления   всех
связанных пар.
\par
Формально,  назовем  связью  упорядоченную  пару  натуральных
чисел. Связь $(i,j)$ будем обозначать ${i\longmapsto j}$. Множеством  связей  в
момент $n$ назовем множество ${U_{n} = \{i\longmapsto j\mid}$ пучок  $\Pi_{j}$ $\le n$-связан  с
пучком  $\Pi_{i}\}$,   где   ${\Pi_{1},\ldots,
\Pi_{m}}$   ---   все $\le n$-минимальные   пучки,
занумерованные по порядку. Назовем накоплением связей в  момент $n$
функцию ${g_{n}\colon\,\longmapsto \{0,\ldots |Q|\}}$, определенную равенством ${g(i\longmapsto j)=}$
($\le n$-накоп\-лению   пары   ${(\Pi_{i},\Pi_{j})=h_{n}(\Pi_{i},\Pi_{j})}$.   Назовем   расширенным
$n$-пред\-ставлением последовательность ${J_{n} = (K_{n},U_{n},g_{n})}$. (Напомним,
что $K_{n}$ обозначает $n$-пред\-ставление).
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Назовем расширенным представлением  любую  последовательность
вида $J=(D,I_{1},\ldots,
I_{m},\gamma,U,g)$, удовлетворяющую условиям П1 ---  П4  и
дополнительно условиям
\par
П5~$U\subset \{1,\ldots,m\}$

П6~$g\colon\,U\longmapsto \{0,\ldots,|Q|\}$.
\par
Элементы $U$ назовем связями  расширенного  представления $J$,  а
значение $g(i\longmapsto j)$  накоплением  связи $(i\longmapsto j)$  в  расширенном
представлении $J$. Последовательности $J$,  удовлетворяющие  свойствам
П1, П2, П3, П5, П6 назовем расширенными полупредставлениями.
\par
Положим  множество  состояний  $\cal C$   равным   множеству   всех
расширенных представлений. Оценим количество состояний автомата $\cal C$.
Пусть $N$ --- количество состояний автомата $\cal A$.
\par
Ввиду П4, $m\le |P(Q)|^{2} = 2^{2N}$
\par
Мощность области изменения $D$ не превосходит $|P(Q)|\le 2^{N}$.
\par
Количество различных срезов $\le  2^{N}*(N+2)^{N}$.
\par
Количество различных $\gamma $ не более $m+1 \le  2^{2N}+1$.
\par
Мощность области изменения $U$  не  более $2^{m^{2}}\le  2^{2^{4N}}$.
\par
Мощность  области  изменения $g$  не  более\\
$(N+2)^{m^{2}}\le (N+1)^{2^{4N}}=2^{2^{O(N)}}$.
\par
Итак, количество состояний $\cal C$ не превышает
$$
2^{N}*(2^{N}*(N+2)^{N})^{2^{2N}}*(2^{2N}+1)*2^{2^{4N}}*2^{2^{O(N)}} = 2^{2^{0(N)}}.
$$
Теперь  определим  непредельные  переходы  автомата   $\cal C$.   Из
состояния $J$, читая букву $a$, автомат $\tau$ переходит  в  состояние $J'$,
полученное  из $J$  последовательным  применением  трех   процедур:
Преобразование1, Добавление1, Сокращение1. Область  определения  и
множество значений  всех  процедур  ---  это  множество  расширенных
полупредставлений.
\par
Пусть $J = (D,I_{1},\ldots,I_{m},\gamma,U,g)$   ---   исходное   расширенное
полупредставление.
\par
Процедура  Преобразование1  состоит  в  применении  процедуры
Преобразование к представлению $(D,I_{1},\ldots,I_{m},\gamma)$. При  этом $U$  и $g$
никак не изменяются.
\par
Скажем, что срез вида $(A,\{q\},*)$  связан  со  срезом $(B,S,*)$,
если\\ $A\subset B$, $q\in S$.
\par
Процедура Добавление1 добавляет все срезы вида $(A,\{q\},\sigma_{A,q})$,
${q\in A\subset Q}$, ${q\in D}$ точно так же, как  и  процедура  Добавление.  Обозначим
полученную последовательность ${(A',I_{1},\ldots,I_{m},I_{m+1},\ldots,I_{m+l},Z,U,g)}$,
где ${I_{m+1},\ldots,I_{m+l}}$ --- добавленные срезы.  После  этого  для  каждого
нового среза ${I_{m+i} = (*,\{q\},*)}$  и  любого  среза $I_{j}$, ${j\le m+2}$,  если
окажется, что $I_{m+i}$ связан с $I_{j}$, то в $U$ добавляется связь ${j\longmapsto m+i}$
и ее накопление устанавливается равным накоплению $q$ в срезе $I_{j}$.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Процедура Сокращение1  работает  следующим  образом.  Сначала
вычеркиваются все срезы $I_{j}$ для которых существует $k<j$  такое,  что
$I_{k}$ эквивалентен $I_{j}$.
\par
Затем определяется новая граница неподвижности так же как и в
процедуре Сокращение.  После  вычеркивания,  каждый  невычеркнутый
срез $I_{j}$ получил какой-то новый номер. Обозначим этот  номер $n(j)$.
Новое множество связей $U'$ состоит из таких  связей $n(j)\longmapsto n(l)$,
что $I_{j}$ и $I_{l}$ не были вычеркнуты  и  существует  срез $I_{k}$ (возможно
вычеркнутый),  эквивалентный $I_{l}$,   такой,   что   связь $j\longmapsto k$
принадлежит $U$. При  этом  накопление  связи $n(j)\longmapsto n(l)$  из $U'$
устанавливается равным максимуму величин $g(j\longmapsto k)$ по всем  таким
$k$, что $I_{k}$ эквивалентен $I_{j}$ и связь $j\longmapsto k$ принадлежит $U$.
\par
Описание процедур закончено. Тем самым мы определили переходы
автомата $\cal C$. Нетрудно проверить, что если в момент $n$ автомат $\cal C$  находился
в состоянии,  равном  расширенному $n$-представлению,  то  прочитав
букву $(n+1)$  он  перейдет  в   состояние,   равное   расширенному
$(n+1)$-представлению.
\par
Теперь перейдем к построению предельных переходов автомата $\cal C$.
Нам понадобится два вспомогательных утверждения.
\par
Пусть $\sigma $ --- предельный ординал, $\sigma \le \rho $. Непосредственно из леммы~1
нетрудно извлечь
\par
СЛЕДСТВИЕ~2. {\it Следующие  условия  эквивалентны}
\par
(1)~{\it В пучке $\Pi$ имеется $[*,\sigma [$-путь с пределом $A$.}
\par
(2) {\it Некоторый $<\sigma $-минимальный пучок $\Pi$, $<\sigma $-связанный с $\Pi$  имеет
ограничитель $A$ и неограниченное в $\sigma $ множество сбросов.}
\par
Следующее утверждение дает возможность считать на  предельных
шагах накопление состояний.
\par
Пусть опять $\sigma $ --- предельный ординал, $\sigma \le \rho $.
\par
СЛЕДСТВИЕ~3. {\it Пусть $r\ge 1$. Следующие условия эквивалентны}
\par
(1)~{\it В пучке $\Pi$ есть $[n,\sigma [$-путь с накоплением $\ge r$ и пределом  $A$,
такой, что $[n,\sigma [$ не содержит сбросов пучка $\Pi$.}

(2) {\it Существует $<\sigma $-минимальный пучок $\Pi_{1}=(*,*,A)$, $<\sigma $-связанный
с $\Pi$, имеющий неограниченное в $\sigma $ множество  сбросов  и  такой,  что
$\exists k\in \sigma\,\forall m\ge k,\,m\in \sigma $ накопление пары $(\Pi,\Pi_{1})$ в момент $m$ больше или  равно
$r$.}
\par
ДОКАЗАТЕЛЬСТВО. Все переменные $n_{0},n_{1},\ldots,m,k$ пробегают $\sigma $.
\par
$(1)\Longrightarrow (2)$. Пусть $P$ --- $[n,\sigma [$-путь с накоплением $\ge r$ и пределом $A$,
принадлежащий пучку $\Pi$. Тогда существует $n_{0}\ge n$ такое, что накопление
пути $P_{1} = P|[n,n_{0}]$ больше или равно $r$. По лемме~1 существует $n_{1}\ge n_{0}$
такое, что пучок $(n_{1},P(n_{1}),A)$ имеет неограниченное в $\sigma $  множество
сбросов.    Положим    $\Pi_{1}$    равным $<\sigma $-минимальному     пучку,
$<\sigma $-эквивалентному пучку $(n_{1},P(n_{1}),A)$. Тогда, во-первых,  $\Pi_{1}$  имеет
неограниченное в $\sigma $ множество сбросов. Во-вторых, $\Pi_{1}$ $<\sigma $-связан с $\Pi$.
В-третьих, накопление пары $(\Pi,\Pi_{1})$ при всех $m\ge n_{1}$ больше  или  равно
$r$, поскольку $\Pi$-накопление точки $(n_{1},P(n_{1}))$  больше  или  равно $r$.
Положим $k=n_{1}$.
\par
$(2)\Longrightarrow (1)$. Пусть пучок $\Pi_{1} = [*,*,A]$ и  число $k$  удовлетворяет
условиям утверждения~(2). Тогда накопление пары $(\Pi,\Pi_{1})$ в момент $m$
больше или равно $r$. Следовательно существует $<\sigma $-пучок $\Pi_{2} = (l,q,A)$
такой, что $l\le k, \Pi_{2}={}_{<\sigma}\Pi$, $\Pi_{2}$ --- потомок $\Pi$ и $\Pi$-накопление точки $(l,q)$
больше или равно $r$, причем отрезок $[l,k]$ не содержит сбросов пучка
$\Pi$.

\begin{picture}(350,80)

\end{picture}

\centerline{Рис.~3}
\par
Так как $\Pi_{1}$ имеет  неограниченное  в $\sigma $  множество  сбросов  и
$\Pi_{2}={}_{<\sigma}\Pi$, то и $\Pi_{2}$ имеет неограниченное в $\sigma $  множество  сбросов.  По
лемме~1 в $\Pi_{1}$ имеется $[*,\sigma [$-путь $P_{2}$ с пределом $A$. Ясно, что началом
$P_{2}$ можно считать точку $(l,q)$.  Так  как  $\Pi_{2}$  ---  потомок  $Pi$,  точка
$(l,q)\in T(\Pi)$. $\Pi$-накоп\-ление $(l,q)$ больше или равно $r$,  следовательно,
в пучке $\Pi$ существует путь $P_{1}$ с накоплением $\ge r$ и  концом $(l,q)$,  и
начальным моментом $i$ таким, что отрезок $[i,l]$ не содержит моментов
сброса пучка $\Pi$. Поскольку для всех $m\ge k$ накопление  пары  $(\Pi,\Pi_{1})$  в
момент $m$ положительно, то отрезок $[k,\sigma [$ не имеет сбросов пучка  $\Pi$.
Следовательно, весь  отрезок $[i,\sigma [$  не  имеет  сбросов  пучка  $\Pi$.
Положим $n=i$ и $P=P_{1}P_{2}$. Следствие доказано.
\par
Из следствия~2 и 3 легко извлечь способ построения предельных
переходов автомата $\cal C$.
\par
Пусть ${\cal J}$  макросостояние  автомата  $\cal C$,  то   есть   множество
уточненных представлений. Требуется указать состояние $J$, в которое
переходит $\cal C$  при чтении на предельном шаге буквы $a$, если ${\cal J}$ --- предел
хода на предыдущих шагах.
\par
Заметим, что если ${\cal J} = \limit_{n\to\sigma} J_{n}$, то ${\cal J}$ удовлетворяет  следующим
условиям
\par
1)~Для любых $J'$, $J''\in {\cal J}$ для всех $i\le \gamma({\cal J})$ ограничитель $i$-го среза
в $J'$ равен ограничителю $i$-го среза в $J''$. То  есть  можно  говорить
об ограничителе $i$-го среза ${\cal J}$ при $i\le \gamma({\cal J})$.
\par
2)~$\forall i,j\le \gamma ({\cal J})\ \forall J',J''\in {\cal J}$ ($J'$ содержит связь $i\longmapsto j\Longleftrightarrow J$  содержит
связь $i\longmapsto j$). То есть связи внутри зоны абсолютной неподвижности
у всех состояний из ${\cal J}$ одинаковы. Потому можно  говорить  о  связях
внутри зоны абсолютной неподвижности ${\cal J}$.
\par
3)~Пусть $i\le \gamma ({\cal J})$ и  в  любом  состоянии $J\in {\cal J}$ $i$-й  срез  имеет
немаксимальное накопление (т.е. $i$-й $<\sigma $-минимальный  пучок  имеет
ограниченное в $\sigma $ множество сбросов). Тогда для любой связи $i\longmapsto j$
внутри зоны абсолютной неподвижности ${\cal J}$ накопления связи $(i\longmapsto j)$
во всех состояниях $J\in {\cal J}$  одинаковы.  Это  следует  из  монотонности
накопления при отсутсвии сбросов.  Поэтому  в  этом  случае  можно
говорить о накоплении связи $i\longmapsto j$ в ${\cal J}$.
\par
Мы  будем   определять   предельные   переходы   только   для
макросостояний ${\cal J}$, удовлетворяющих свойствам 1)--3).  Для  получения
состояния $J'$, в  которое $\cal C$  переходит  из  макросостояния ${\cal J}$  на
предельном шаге, читая букву $a$, мы применим к $J$   последовательно
четыре  процедуры   Свертывание,   Преобразование1,   Добавление1,
Сокращение1.

Расширим область определения процедуры  Добавление1.  Именно,
введем для  каждого $A\subset Q$, $A<>Q$  новое  состояние $q_{A}$.  Заменим  в
определении  расширенного   полупредставления   множество $Q$   на
множество $Q'=Q\bigcup \{q\mid A\in Q\}$.
\par
Процедура Свертывание. Пусть ${\cal J}$ исходное множество расширенных
представлений. Для каждого $j\le \gamma ({\cal J})$ положим  $A$  равным  ограничителю
$j$-го среза в ${\cal J}$. Положим $S_{j} = \{q_{A_{k}}\colon\,\exists k\le \gamma ({\cal J})$:  в ${\cal J}$  имеется  связь
$j\longmapsto k$ и $k$-ый срез в некотором состоянии из ${\cal J}$ имеет  максимальное
накопление$\}$. Если $q_{A_{k}}\in S_{j}$, то положим
$$
f(q)=\cases{\{{\rm накоплению\ связи}\ j\longmapsto k\ {\rm в}\ {\cal J},\ {\rm если\ во\ всех}\ J\in {\cal J}\cr
\ j{\rm -й\ срез\ в}\ J\ {\rm имеет\ немаксимальное\ накопление}\cr \{0,\ {\rm иначе.}}
$$

Положим $I_{j}=(A_{j},S_{j},f_{j})$.
\par
Положим $D = \{q_{A_{i}}\mid i\le \gamma ({\cal J}),\ \exists J\in {\cal J}$ $i$-й срез в ${\cal J}$ имеет максимальное
накопление$\}$.
\par
Положим $\gamma=\gamma({\cal J})$.
\par
Положим $U$ $=$ множеству связей ${\cal J}$ внутри зоны неподвижности.
\par
Наконец, накопление $g(j\longmapsto k)$ связи $j\longmapsto k$  из $U$  положим
равным $f_{j}(q_{A_{k}})$.
\par
Последовательность ${\cal J} = (D,I_{1},\ldots,I_{\gamma(J)},\gamma,U,g)$  выдадим  на
выход.
\par
Процедуру Преобразование1 применяем с параметром $R = \{(q_{A},q')\mid (A,a,q)$ --- предельный переход $\cal A$ $\}$.
\par
Итак, предельные переходы автомата $\cal C$  описаны.
\par
Рутинной проверкой можно убедиться, что прочитав $\alpha(1)\ldots\alpha (n)$
автомат   $\cal C$    приходит    в    состояние,    равное    уточненному
$n$-представлению.
\par
Заключительные состояния $\cal C$ --- это те уточненные представления,
в которых множество возможных  состояний  содержит  заключительное
состояние $\cal A$.
\par
Заключительные макросостояния $\cal C$ --- это  те  макросостояния,  в
применении к которым  процедура  свертывание  выдает  множество $D$
содержащее  такое $q_{A}$,  что  $A$  ---  заключительное   макросостояние
автомата $\cal A$.
\par
Автомат   определен   и   теорема   доказана.

\end{document}

