free-plain-det.tex

   1 \subsection{ïÐÒÅÄÅÌÅÎÉÑ}
   2
   3
   4 \subsubsection{CÉÓÔÅÍÙ ÐÅÒÅÈÏÄÏ× É ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÅ Á×ÔÏÍÁÔÙ}
   5
   6 óÉÓÔÅÍÁ ÐÅÒÅÈÏÄÏ×
   7
   8 îÏÒÍÁÌÉÚÏ×
   9
  10 \subsection{íÁÔÒÉÃÙ}
  11 ÎÅÚÁ×ÉÓ
  12
  13
  14
  15 ---
  16
  17 ÞÅÒÅÚ ËÒÁÔÎÏÓÔÉ
  18
  19 ---
  20
  21 ÎÁ Ó×. ÍÏÄÅÌÉ
  22
  23 ÎÁ ÏÔÄÅÌØÎÙÈ ÍÏÄÅÌÑÈ-<<ÓÌÏ×ÁÈ>>
  24
  25 \begin{question}
  26  ëÁË Ó×ÑÚÁÎÙ ÁÌÇÏÒÉÔÍÙ ÐÒÏ×ÅÒËÉ $\au A = \au B$ ÄÌÑ ÄÅÔÅÒÍ./ÏÄÎÏÚÎ. É
  27  $\au A = 0$ ÄÌÑ ËÒÁÔÎ.? ëÏÇÄÁ ÍÏÖÎÏ ÒÅÛÉÔØ ÐÒÏÂÌÅÍÕ $\au A = 0$ Ó
  28  ËÒÁÔÎ.  ÎÁ ÏÓÎÏ×Å  ÁÌÇÏÒÉÔÍÁ ÄÌÑ $\au A = \au B$?
  29 \end{question}
  30
  31 \begin{definition}
  32 ðÕÓÔØ $s \in \AExp_\Sigma.$
  33 $\detA(s)$ ÏÂÏÚÎÁÞÁÅÔ ÒÅÚÕÌØÔÁÔ \tING{ÄÅÔÅÒÍÉÎÉÚÁÃÉÉ} Á×ÔÏÍÁÔÁ
  34 ÓÔÁÎÄÁÒÔÎÙÍ ÐÏÓÔÒÏÅÎÉÅÍ,
  35 ÏÓÎÏ×ÁÎÎÏÍ ÎÁ ÐÏÄÍÎÏÖÅÓÔ×ÁÈ ÍÎÏÖÅÓÔ×Á ÓÏÓÔÏÑÎÉÊ ÉÓÈÏÄÎÏÇÏ Á×ÔÏÍÁÔÁ
  36 \cite{HopcroftUllman-automata,LewisPapadimitriou-computation}.
  37 \end{definition}
  38 \begin{lemma}\label{lem:detA}
  39   \cite[Lemma~17]{KA-regevents-complete}, \cite[Lectures~8--9]{KA-lect02}.
  40   $$
  41   \KA \models s = \detA(s)
  42   $$
  43 \end{lemma}
  44
  45 \begin{definition}
  46 ðÕÓÔØ $s \in \AExp_\Sigma.$
  47 $\minA(s)$ ÏÂÏÚÎÁÞÁÅÔ ÒÅÚÕÌØÔÁÔ \tING{ÍÉÎÉÍÉÚÁÃÉÉ} Á×ÔÏÍÁÔÁ
  48 ÓÔÁÎÄÁÒÔÎÙÍ ÐÏÓÔÒÏÅÎÉÅÍ
  49 \cite{HopcroftUllman-automata,LewisPapadimitriou-computation}.
  50 \end{definition}
  51 \begin{lemma}\label{lem:minA}
  52   \cite[Lemma~18]{KA-regevents-complete}, \cite[Lectures~8--9]{KA-lect02}.
  53   $$
  54   \KA \models s = \minA(s)
  55   $$
  56 \end{lemma}
  57
  58 \begin{theorem}\label{th:minA-unique}
  59   \cite{HopcroftUllman-automata}
  60   åÓÌÉ $R_\Sigma(s) = R_\Sigma(t)$, ÔÏ $\minA(s)$ É $\minA(t)$ ÉÚÏÍÏÒÆÎÙ.
  61 \end{theorem}
  62 %%% Local Variables:
  63 %%% mode: latex
  64 %%% TeX-master: "main"
  65 %%% End: