1 \documentclass[a4paper,russian
]{report}
3 %\newcommand*{\toRead}{\textbf{To read}}
4 \newcommand*
{\toRead}{}
5 %\newcommand\localRL{\begingroup \urlstyle{tt}\Url}
6 \newcommand{\localRL}[1]{}
8 \usepackage[koi8-r
]{inputenc}
11 \bibliographystyle{alpha
}
13 % todo: ÎÏÍÅÒÁ ÓÌÅ×Á ÏÔ ôÅÏÒÅÍÁ etc.
23 \author{é×ÁÎ úÁÈÁÒØÑÝÅ×,
518 ÇÒÕÐÐÁ
}
24 \title{äÉÐÌÏÍÎÁÑ ÒÁÂÏÔÁ. ôÅÍÁ: ðÒÏÂÌÅÍÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ × ÍÏÄÅÌÑÈ
25 ÐÒÏÇÒÁÍÍ Ó ÞÁÓÔÉÞÎÏ ËÏÍÍÕÔÁÔÉ×ÎÙÍÉ É ÍÏÎÏÔÏÎÎÙÍÉ ÏÐÅÒÁÔÏÒÁÍÉ
}
27 \newcommand*
{\mainCha}[3]{
28 %% \section{íÅÔÁÔÅÏÒÉÑ ÁÌÇÅÂÒ É ÌÉÎÅÊÎÏÚÁÐÉÓÙ×ÁÅÍÙÈ ×ÙÒÁÖÅÎÉÊ
29 %% (ÓÌÕÞÁÊ ÉÄÅÍÐÏÔÅÎÔÎÏÓÔÉ)}
30 \section{îÅÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ ÐÒÏÇÒÁÍÍÙ × <<ÉÄÅÍÐÏÔÅÎÔÎÏÊ ÓÅÍÁÎÔÉËÅ>>
}
34 \section{äÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ É ÏÄÎÏÚÎÁÞÎÙÅ ÐÒÏÇÒÁÍÍÙ
}
38 \section{ðÒÏÇÒÁÍÍÙ × <<ÓÅÍÁÎÔÉËÅ, ÕÞÉÔÙ×ÁÀÝÅÊ ËÒÁÔÎÏÓÔÉ>>
}
51 \chapter{÷×ÅÄÅÎÉÅ
}\label{cha:intro
}
54 %%%%%%%%%%%%%%%%%%%%%%%%%%
56 \chapter{ïÂÝÉÅ ÐÏÎÑÔÉÑ
}\label{cha:general
}
60 \chapter{íÅÔÁÔÅÏÒÉÑ\\ ÁÂÓÔÒÁËÔÎÙÈ ÐÒÏÇÒÁÍÍ
0\d{}ÇÏ ÐÏÒÑÄËÁ\\ Ó ÏÐÅÒÁÔÏÒÁÍÉ
61 × ÏÔÓÕÔÓÔ×ÉÉ ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×
}
62 \label{cha:free-plain
}
63 \mainCha{free-plain-ndet
}{free-plain-det
}{free-plain-multi
}
65 \chapter{íÅÔÁÔÅÏÒÉÑ\\ ÁÂÓÔÒÁËÔÎÙÈ ÐÒÏÇÒÁÍÍ
0\d{}ÇÏ ÐÏÒÑÄËÁ\\ Ó
67 × ÏÔÓÕÔÓÔ×ÉÉ ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×
}
68 \label{cha:free-withTests
}
69 \mainCha{free-withTests-ndet
}{free-withTests-det
}{free-withTests-multi
}
70 %\input free-withTests
72 \chapter{íÅÔÁÔÅÏÒÉÑ\\ ÁÂÓÔÒÁËÔÎÙÈ ÐÒÏÇÒÁÍÍ
0\d{}ÇÏ ÐÏÒÑÄËÁ\\ Ó ÏÐÅÒÁÔÏÒÁÍÉ
73 × ÐÒÉÓÕÔÓÔ×ÉÉ ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×
}
74 \label{cha:hypo-plain
}
76 ÷ ÜÔÏÊ çÌÁ×Å ÍÙ ÉÓÓÌÅÄÕÅÍ ÐÒÏÂÌÅÍÕ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÐÒÏÇÒÁÍÍ ÐÒÉ ÄÏÐÏÌÎÉÔÅÌØÎÙÈ
77 ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÁÈ. ÷ÓÑ ÒÁÂÏÔÁ ÎÁÃÅÌÅÎÁ ÎÁ ÉÓÓÌÅÄÏ×ÁÎÉÅ ðü ÐÒÉ
78 ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÁÈ, ×ÙÒÁÖÁÀÝÉÈ ÞÁÓÔÉÞÎÕÀ ËÏÍÍÕÔÁÔÉ×ÎÏÓÔØ É
79 ÏÂÏÂÝ£ÎÎÕÀ ÍÏÎÏÔÏÎÎÏÓÔØ ÏÐÅÒÁÔÏÒÏ×. íÙ ÒÁÓÓÍÁÔÒÉ×ÁÅÍ ÏÂÝÉÊ ÐÏÄÈÏÄ Ë
80 ÄÏÂÁ×ÌÅÎÉÀ ÐÏÓÔÕÌÁÔÏ× × ÎÁÛÕ ÔÅÈÎÉËÕ ÉÓÓÌÅÄÏ×ÁÎÉÑ É ËÏÎÃÅÎÔÒÉÒÕÅÍ
81 ×ÎÉÍÁÎÉÅ ÎÁ ÕÓÔÁÎÏ×ÌÅÎÉÅ ÉÎÔÅÒÅÓÕÀÝÉÈ ÎÁÓ ÆÁËÔÏ× × ÓÌÕÞÁÅ ÐÏÓÔÕÌÁÔÏ×
82 ÕËÁÚÁÎÎÏÇÏ ×ÉÄÁ. ÷ ÎÁÛÅÍ ÉÓÓÌÅÄÏ×ÁÎÉÉ ÐÏÓÔÕÌÁÔÙ ÂÕÄÕÔ ×ÙÒÁÖÁÔØÓÑ
83 ÄÏÐÕÝÅÎÉÑÍÉ, ÓÔÁÎÏ×ÑÝÉÍÉÓÑ ÐÏÓÙÌËÁÍÉ × Horn
\DÆÏÒÍÕÌÁÈ.
84 äÌÑ ÁÂÓÔÒÁËÃÉÊ ÐÒÏÇÒÁÍÍ, ËÏÔÏÒÙÍ ÐÏÓ×ÑÝÅÎÁ ÜÔÁ çÌÁ×Á,
\T ÐÒÏÇÒÁÍÍÁÍ
85 ÔÏÌØËÏ Ó ÏÐÅÒÁÔÏÒÁÍÉ, ÎÏ ÂÅÚ ÔÅÓÔÏ×
\T ÉÍÅÀÔ ÓÍÙÓÌ ÐÏÓÔÕÌÁÔÙ
86 ËÏÍÍÕÔÁÔÉ×ÎÏÓÔÉ ÏÐÅÒÁÔÏÒÏ× (ÎÏ ÎÅ ÍÏÎÏÔÏÎÎÏÓÔÉ, ×Ï×ÌÅËÁÀÝÉÈ ÔÅÓÔÙ).
88 ÷ ÏÂÌÁÓÔØ, ÐÏËÒÙ×ÁÅÍÕÀ ÜÔÏÊ çÌÁ×ÏÊ, ÐÏÐÁÄÁÅÔ ÓÌÕÞÁÊ ÍÎÏÇÏÌÅÎÔÏÞÎÙÈ
89 Á×ÔÏÍÁÔÏ× (× òÁÚÄÅÌÅ~
\ref{sec:mta
} ÍÙ ×ÙÒÁÚÉÍ ÉÈ ÓÉÎÔÁËÓÉÓ É ÓÅÍÁÎÔÉËÕ
90 ÓÒÅÄÓÔ×ÁÍÉ, ÐÒÉÎÑÔÙÍÉ × ÎÁÛÅÍ ÉÓÓÌÅÄÏ×ÁÎÉÉ).
92 \mainCha{hypo-plain-ndet
}{hypo-plain-det
}{hypo-plain-multi
}
95 \chapter{íÅÔÁÔÅÏÒÉÑ\\ ÁÂÓÔÒÁËÔÎÙÈ ÐÒÏÇÒÁÍÍ
0\d{}ÇÏ ÐÏÒÑÄËÁ\\ Ó
97 × ÐÒÉÓÕÔÓÔ×ÉÉ ÓÅÍÁÎÔÉÞÅÓËÉÈ ÐÏÓÔÕÌÁÔÏ×
}
98 \label{cha:hypo-withTests
}
99 \mainCha{hypo-withTests-ndet
}{hypo-withTests-det
}{hypo-withTests-multi
}
100 %\input hypo-withTests
102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%
104 %% \chapter{òÁÚÎÙÅ ÚÁÍÅÞÁÎÉÑ É ÄÏÐÏÌÎÅÎÉÑ}
107 %%%%%%%%%%%%%%%%%%%%%%%%%
109 %\chapter{éÚ×ÅÓÔÎÙÅ ÐÒÉÍÅÎÅÎÉÑ ÎÁ ÐÒÁËÔÉËÅ}
111 %\chapter{óÐÉÓÏË ÏÔËÒÙÔÙÈ ×ÏÐÒÏÓÏ×}
115 %\todo{[ËÏÒÏÔËÏ ÓÕÔØ ÔÏÇÏ, ÞÔÏ ÓÄÅÌÁÎÏ ÎÏ×ÏÇÏ, ÎÁ ÆÏÎÅ ÓÔÁÒÏÇÏ]}
119 \chapter{óÐÒÁ×ËÁ ÐÏ ÄÒÕÇÉÍ ÐÏÎÑÔÉÑÍ
}
122 \chapter{ôÅÒÍÉÎÙ É ÏÂÏÚÎÁÞÅÎÉÑ
}
127 \section{ïÂÏÚÎÁÞÅÎÉÑ
}
131 \nocite{KA-lect04,lectAK
}
132 \nocite{HopcroftUllman-automata-new
}
135 %\bibliography{courseiv}
136 \bibliography{my,KA,KA-add,KA-other,common-books,uni-papers,alg-books,kf-works,automata,dmta-equiv,multiautomata,E-alg,equiv-commut
}