mesi.tex

% !TEX encoding = UTF-8 Unicode
\documentclass[a4paper]{article}
\usepackage[bulgarian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb, amsthm, amsmath, mathrsfs,alltt}
\usepackage{latexsym}
\usepackage{enumerate}
\usepackage{datetime}
%this package allows for hyperlinks within the pdf document
\usepackage[colorlinks=true, linkcolor=blue,pdfstartview=FitV,
citecolor=green, urlcolor=blue]{hyperref}

\theoremstyle{definition}
\newtheorem{theorem}{Теорема}
\newtheorem{lemma}{Лема}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Твърдение}
\newtheorem{example}{Пример}
\newtheorem{definition}{Определение}
\newtheorem{question}{Въпрос}
\newtheorem{problem}{Задача}
\newtheorem{remark}{Забележка}

\newenvironment{hint}{\noindent{\bf Упътване.}\hspace*{1em}}{\qed\par\vspace*{1em}}

\usepackage{mysymbols}
\reversemarginpar
\usepackage{marginnote}

% \let\oldmarginpar\marginpar
% \renewcommand\marginpar[1]{\leavevmode\oldmarginpar{\raggedright\scriptsize #1}}



% \author{Стефан Вътев\thanks{Draft compiled at \currenttime\ on \today}}
\title{М.Е.С.И.}
% \institute{
% Софийски Университет, Факултет по математика и информатика,\\ 
% бул. Джеймс Баучер 5, 1164 София, България\\ 
% \email{stefanv@fmi.uni-sofia.bg}
% }
\begin{document}
\maketitle

\section{Увод}

\begin{itemize}
\item
  Машини на Тюринг
\item
  Разрешими и полуразрешими езици
\item
  Сложностни класове $\texttt{PSPACE}$, $\texttt{NPSPACE}$, $\texttt{P}$, $\texttt{NP}$ и други.
\item
  Сводимости между проблеми: сводимост на Карп $\leq_P$ и ефективна сводимост $\leq_m$.
\end{itemize}

\begin{theorem}
  \marginnote{\scriptsize \cite[стр. 47]{papadimitriou}}
  Ако $L$ се разрешава от недетерминистичната машина на Тюринг $\N$ за време $f(n)$, то
  $L$ се разрешава от трилентова детерминистична машина на Тюринг $\M$ за време $\mathcal{O}(c^{f(n)})$, където константата $c$ зависи от $\N$.
\end{theorem}

\section{Двупосочни автомати или защо писането е важно}
\begin{definition}
  Двапосочен автомат е машина на Тюринг
  \[\mathcal{M}=\langle \Sigma,\Gamma,Q,s,\Delta,F,B\rangle,\]
  за която
  $\$,\#\in \Gamma\setminus\Sigma$ и  всеки преход е от вида $t=\langle (p,a),(q,a,d)\rangle$, тоест буквите на лентата не се променят.
\end{definition}
\begin{definition}
  Език на двупосочен автомат $\mathcal{M}$ е:
  \begin{equation*}
    L_{2way}(\mathcal{M})=\{\alpha \in \Sigma^*\,|\,\exists f\in F( \langle \varepsilon,s,\#\alpha\$\rangle \Rightarrow_M^* \langle \#\alpha\$,f,\varepsilon\rangle\}.
  \end{equation*}
\end{definition}
\begin{theorem}
  Класът от езиците, разпознавани от двупосочни автомати е точно класът от регулярни езици.
\end{theorem}

\section{Критерий за разрешимост}

\marginnote{\scriptsize \cite{hopcroft}}
Нека $\Ss$ е множество от полуразрешими езици над фиксирана азбука $\Sigma$.
Например, 
\[\Ss = \{L \subseteq \Sigma^\star \mid L\text{ е регулярен език}\}.\]
Ще казваме, че $\Ss$ е свойство на полуразрешимите езици.
$\Ss$ е {\bf тривиално свойство}, ако $\Ss = \emptyset$ или $\Ss$ съдържа точно всички полуразрешими езици.
Нека разгледаме изброимото множество от машини на Тюринг, които разпознават езиците от $\Ss$.
Ще представим това множество като език от кодовете на тези машини на Тюринг, т.е.
\[\texttt{Ind}(\Ss) = \{\code{\M} \mid \text{$\M$ е машина на Тюринг и } \L(\M) \in \Ss\}.\]

\begin{theorem}[Райс]
  \index{Райс}
  \marginnote{\scriptsize \cite[стр. 62]{papadimitriou}}
  За всяко нетривиално свойство $\Ss$ на полуразрешимите езици, $\texttt{Ind}(\Ss)$ е неразрешимо.
\end{theorem}


\section{Критерий за полуразрешимост}

\marginnote{\scriptsize \cite{hopcroft}}
\begin{lemma}
  Нека $\Ss$ е свойство на полуразрешимите езици.
  Ако съществува безкраен език $L_0 \in \Ss$, който няма крайно подмножество в $\Ss$,
  то $\texttt{Ind}(\Ss)$ не е полуразрешим език.  
\end{lemma}

\begin{lemma}
  Нека $L_1$ е език в $\Ss$ и нека $L_2$ е полуразрешим език, като $L_1 \subset L_2$ и $L_2 \not\in\Ss$.
  Тогава $\texttt{Ind}(\Ss)$ не е полуразрешим език.
\end{lemma}

\begin{theorem}[Райс-Шапиро]
  Нека $\texttt{Ind}(\Ss)$ е полуразрешим език. Тогава е изпълнено, че:
  \[L \in \texttt{Ind}(\Ss) \iff (\forall L_0)[L_0\text{ е краен и }L_0 \subseteq L \implies L_0 \in \Ss].\]
\end{theorem}

\section{Проблем на Пост за съответствието}

\begin{lemma}
  \marginnote{\scriptsize \cite[стр. 193]{hopcroft}}
  Съществува алгоритъм, който свежда MPCP към PCP.
\end{lemma}

\begin{theorem}[Пост]
  Проблемът за съответствието на Пост е неразрешим при азбука $\Sigma$ с поне два символа.
\end{theorem}

\begin{proposition}
  Езикът
  \[L = \{\code{G} \mid G \text{ е еднозначна безконтекстна граматика}\}\]
  е неразрешим.
\end{proposition}

\begin{proposition}
  Езикът
  \[L = \{\code{G_1}\sharp\code{G_2} \mid \mathcal{L}(G_1) \cap \mathcal{L}(G_2) \neq \emptyset\}\]
  е неразрешим.
\end{proposition}


\section{Неразрешими езици}

\begin{proposition}
  Езикът
  \[L = \{\code{G_1}\sharp\code{G_2} \mid \mathcal{L}(G_1) \cap \mathcal{L}(G_2) = \emptyset\}\]
  не е полуразрешим.
\end{proposition}

\begin{proposition}
  Езикът
  \[L = \{\code{G} \mid \L(G) = \Sigma^\star\}\]
  не е полуразрешим.
\end{proposition}

\begin{corollary}
  Езикът
  \[L = \{\code{G_1}\sharp\code{G_2} \mid \mathcal{L}(G_1) = \mathcal{L}(G_2)\}\]
  не е полуразрешим.
\end{corollary}

\begin{theorem}[Грейбах]
  \marginnote{\scriptsize \cite[стр. 205]{hopcroft}}
  Нека $\mathcal{C}$ е клас от езици, за който съществува ефективно кодиране $\code{L}$ на езиците в $\mathcal{C}$ и който е:
  \begin{itemize}
  \item 
    ефективно затворен относно обединение;
  \item
    ефективно затворен относно конкатенация с регулярен език;
  \item
    "$= \Sigma^\star$" е неразрешим за достатъчно голяма $\Sigma$.
  \end{itemize}
  Нека $P$ е нетривиално свойство на $\mathcal{C}$, което е изпълнено за всеки регулярен език и ако $L \in P$,
  то $L/_a \in P$, където
  \[L/_a = \{\omega \mid \omega a \in L\}.\]
  Тогава езикът $\{\code{L} \mid P(L)\ \&\ L \in \mathcal{C}\}$ е неразрешим.
\end{theorem}

\begin{corollary}
  Езикът
  \[L = \{\code{G} \mid \L(G) \text{ е регулярен}\}\]
  не е полуразрешим.
\end{corollary}

\section{Контекстносвободни езици}
\begin{theorem}
  \marginnote{\scriptsize \cite[стр. 131]{hopcroft}}
Класът на контекстносвободните езици е затворен относно:
\begin{enumerate}
\item обединение, конкатенация, звезда на Клини.
\item сечение с регулярни езици.
\item образи на хомоморфизми.
\item образи на регулярни релации.
\end{enumerate}
\end{theorem}
\begin{definition}
  \marginnote{\scriptsize На англ. Dyck. Теоремата е формулирана като задача в \cite[стр. 142]{hopcroft}.}
  Език на Дик над езика $B_n=\{(_i,)_i\,|\, 1\le i\le n\}$ е множеството от всички
  думи, които представляват правилно разположени скоби.
\end{definition}
\begin{theorem}
Класът от контекстносвободни езици е точно класът от езици от вида:
\begin{equation*}
h(D_n \cap R),
\end{equation*}
където $D_n$ е език на Дик, $R$ е регулярен език, а $h:B_n^*\rightarrow\Sigma^*$ е хомоморфизъм.
\end{theorem}
\begin{definition}
За азбука $\Sigma=\{a_1,a_2,\dots,a_n\}$ и дума $w\in \Sigma^*$ с $|w|_i$ бележим броя букви $a_i$ в $w$.
Дефинираме $\|w\|=(|w|_1,|w_2,\dots,|w|_n)\in \mathbb{N}^n$.
\end{definition}
\begin{definition}
За вектор $u\in \mathbb{N}^n$ и множество от вектори $V\subseteq \mathbb{N}^n$ с $u+ V$ и $V^*$ бележим множествата от вектори:
\begin{eqnarray*}
u+V = \{u+v\,|\, v\in V\} \text{ и } V^*=\{\sum_{i=1}^k d_iv_i\,|\, k\in \mathbb{N}, d_i\in \mathbb{N}\text{ и } v_i\in V\}.
\end{eqnarray*}
\end{definition}
\begin{theorem}[на Парих] За всеки контекстносвободени език $L\subseteq \{a_1,a_2,\dots,a_n\}^*$ има
естествено число $k$, вектори $u_1,u_2,\dots,u_k\in \mathbb{N}^n$ и крайни множества $V_1,V_2,\dots,V_k\subseteq \mathbb{N}^n$,
за които:
\begin{equation*}
\{\|w\|\,|\, w\in L\} = \bigcup_{i=1}^k (u_i + V_i^*).
\end{equation*}
\end{theorem}
Пучително е да се разгледа частния случай на еднобуквена азбука. Тогава, тъй като $w=a_1^{|w|_1}$ и $\|w\|=(|w|_1)$,
може да отъждествим $w$ с $\|w\|$. Освен това в този случай може да предполагаме, че $|V_i|=1$ за всяко $V_i$ от теоремата
на Парих (може да вземем най-малкото общо кратно в по-големите множества и да добавим повече вектори $u$). Тогава
$V_i=\{v_i\}$ и изразите $u_i+V_i^*=\{u_i+dv_i \,|\, d\in \mathbb{N}\}$ представляват аритметични прогресии. 

Тоест, ако се абстрахираме от реда на буквите, контекстносвободните езици представляват крайни обединения на аритметични
прогресии.


\section{$\texttt{PSPACE}$ и $\texttt{NPSPACE}$ проблеми}

\begin{proposition}
  Езикът
  \[L = \{\code{\A} \mid \A \text{ е НКА и }\L(\A) = \Sigma^\star\}\]
  е $\texttt{PSPACE}$-пълен.
\end{proposition}

\begin{theorem}[Савич 1970]
  \[\texttt{NPSPACE}(f(n)) \subseteq \texttt{PSPACE}(f^2(n)).\]
\end{theorem}

\begin{corollary}
  $\texttt{NPSPACE} = \texttt{PSPACE}$.
\end{corollary}

\begin{theorem}
  Езикът
  \[L = \{ \code{\A_1} \sharp \code{\A_2} \mid \A_1,\A_2\text{ са НКА и }\L(\A_1) = \L(\A_2)\}\]
  е $\texttt{PSPACE}$-пълен.
\end{theorem}

\begin{theorem}
Проблемът ($\texttt{INT}$):
\begin{alltt}
Вход: \(n\in\mathbb{N}, A\sb{i}=\langle\Sigma,Q\sb{i},s\sb{i},\delta\sb{i},F\sb{i}\rangle\) - ДKА
Въпрос: \(\bigcap\sb{i}\sp{n}L(A\sb{i})=\Sigma\sp{*}\)?
\end{alltt}
е $\texttt{PSPACE}$-пълен.
\end{theorem}

\begin{theorem}
Проблемът ($\texttt{MIN(NFA}\rightarrow\texttt{NFA)}$):
\begin{alltt}
Вход: \(k\in\mathbb{N}, A=\langle\Sigma,Q,s,\delta,F\rangle\) - НКА
Въпрос: има ли НКА с език \(L(A)\) и не повече от \(k\) състояния?
\end{alltt}
е $\texttt{PSPACE}$-пълен.
\end{theorem}

\begin{theorem}[Immerman-Szelepcs\'enyi]
  \[\texttt{NPSPACE}(S(n)) = \texttt{co-NPSPACE}(S(n)).\]
\end{theorem}

\begin{corollary}
  Допълнението на всеки контекстнозависим език е контекстно зависим.
\end{corollary}


\section{$\texttt{NP}$ проблеми}

% \begin{theorem}
%   Ако $L \in \texttt{NP}$, то $L \in \texttt{EXP}$.
% \end{theorem}

\begin{theorem}
  \marginnote{\scriptsize \cite[стр. 262]{papadimitriou-lewis}}
  % \marginnote{\scriptsize Дори не е полуразрешим}
  Домино проблемът е неразрешим.
\end{theorem}
\begin{hint}
  Свеждаме ефективно езика
  \[\{\code{\M} \mid \M\text{ работи безкрайно дълго при вход }\varepsilon\}\]
  към домино проблема.
\end{hint}

\begin{theorem}
  \marginnote{\scriptsize \cite[стр. 310]{papadimitriou-lewis}}
  Ограниченият домино проблем е $\texttt{NP}$-пълен
\end{theorem}

\begin{theorem}[Кук]
  \marginnote{\scriptsize \cite[стр. 312]{papadimitriou-lewis}}
  $\texttt{SAT}$ проблемът е $\texttt{NP}$-пълен.
\end{theorem}
\begin{hint}
  Ограниченият домино проблем се свежда полиномиално към $\texttt{SAT}$.
\end{hint}

\begin{theorem}
  \marginnote{\scriptsize \cite[стр. 313]{papadimitriou-lewis}}
  $\texttt{3-SAT}$ проблемът е $\texttt{NP}$-пълен.
\end{theorem}
\begin{hint}
  $\texttt{SAT}$ се свежда полиномиално към $\texttt{3-SAT}$.
\end{hint}

За един неориентиран граф $G = (V,E)$,
казваме, че множеството $C \subseteq V$ {\bf покрива върховете} на $G$, ако
\[(\forall (u,v) \in E)[u \in C\ \lor\ v \in C].\]
$\texttt{Vertex Cover}$ е проблемът да се определи дали по даден неориентиран граф $G$ и $k \in \Nat$
съществува покритие $C$ на върховете на $G$, за което $|C| = k$.

\begin{theorem}
  \marginnote{\scriptsize \cite[стр. 331]{hopcroft}}
  $\texttt{Vertex Cover}$ проблемът е $\texttt{NP}$-пълен.
\end{theorem}
\begin{hint}
  $\texttt{3-SAT}$ се свежда полиномиално към $\texttt{Vertex Cover}$.
\end{hint}


\subsection*{$\texttt{NP}$-пълни проблеми в теория на езиците}

\begin{definition}
Казваме, че недетреминиран краен автомат $A=\langle \Sigma,Q,\{s\},\Delta,F\rangle$ е еднозначен,
ако $\Delta\subseteq Q\times \Sigma\times Q$ и за всяка дума $w\in L(A)$ има точно един успешен път с етикет $w$ в $A$.
\end{definition}

\begin{lemma}
  Ако $A_i=\langle \Sigma,Q_i,\{s_i\},\Delta_i,F_i\rangle$ за $i=1,2$ са еднозначни НКА, то следните са еквивалентни:
  \begin{enumerate}
  \item $\exists w\in L(A_1)\triangle L(A_2) (|w|\le |Q_1|+|Q_2|)$.
  \item $L(A_1)\triangle L(A_2)\neq\emptyset$.
  \end{enumerate} 
\end{lemma}

\begin{theorem}
Проблемът ($\texttt{MIN(UFA}\rightarrow\texttt{UFA)}$):
\begin{alltt}
Вход: \(k\in\mathbb{N}, A=\langle\Sigma,Q,s,\delta,F\rangle\) - еднозначен НКА
Въпрос: има ли еднозначен НКА с език \(L(A)\) и не повече от \(k\) състояния?
\end{alltt}
е $\texttt{NP}$-пълен.
\end{theorem}

\begin{theorem}[Ladner]
  \marginnote{\scriptsize \cite[стр. 330]{papadimitriou}}
  Ако $\texttt{P} \neq \texttt{NP}$, то съществува $\texttt{NP}$ проблем, който не е $\texttt{P}$ проблем и не е $\texttt{NP}$-пълен проблем.
\end{theorem}

\section{Машини на Тюринг с оракул}

\begin{theorem}[Baker-Gill-Solovay]
  \marginnote{\scriptsize \cite[стр. 340]{papadimitriou}}
  Съществуват оракули $A$ и $B$, за които $\texttt{P}^A \neq \texttt{NP}^A$ и $\texttt{P}^B = \texttt{NP}^B$.
\end{theorem}

\section{Детерминирани стекови автомати и $LR(k)$-граматики}
\begin{definition}
Стеков автомат $A=\langle \Sigma,\Gamma,Q,s,\Delta,Z,F\rangle$ е детерминиран, ако са в сила следните:
\begin{enumerate}
\item $\Delta\subseteq (Q\times(\Sigma\cup \{\varepsilon\})\times \Gamma)\times (Q\times \Gamma^*)$ е графика
на функция 
\begin{equation*}
\delta:Q\times(\Sigma\cup\{\varepsilon\})\times \Gamma\rightarrow Q\times \Gamma^*
\end{equation*}
\item и за всяко състояние $p\in Q$ и стеков символ $X\in \Gamma$:
\begin{equation*}
! \delta(p,\varepsilon,X) \Rightarrow \neg \exists a\in \Sigma( ! \delta(p,a,X)).
\end{equation*}
\end{enumerate}
В този случай ще пишем $A=\langle \Sigma,\Gamma,Q,s,\delta,Z,F\rangle$.
\end{definition}
\begin{definition}
За стеков автомат $A=\langle \Sigma,\Gamma,Q,s,\Delta,Z,F\rangle$ и преход $t=\langle (p,a,X),(q,\beta)\rangle\in \Delta$
казваме, че:
\begin{enumerate}
\item $t$ е \emph{pop} преход, ако $\beta=\varepsilon$,
\item $t$ е \emph{peek} преход, ако $\beta=X$,
\item $t$ е \emph{push} преход, ако $\beta=YX$ за някое $Y\in \Gamma$.
\end{enumerate}
$A$ е в нормална форма, ако всеки преход на $A$ е pop, peek или push.  
\end{definition}
\begin{theorem}
За всеки (детерминиран) стеков автомат $A$ ефективно може да получим еквивалентен 
(детерминиран) стеков автомат $A'$ в нормална форма.
\end{theorem}
\begin{definition}
За детерминиран стеков автомат $A=\langle \Sigma,\Gamma,Q,s,\delta,Z,F\rangle$ казваме, че $A$ зацикля върху вход $w\in \Sigma^*$, ако
за всяко $n$ има изпълнение:
\begin{equation*}
(s,w,Z)\Rightarrow^{(n)}_A (p_n,w_n,\gamma_n).
\end{equation*}
Казваме, че $A$ е ацикличен, ако $A$ не зацикля върху никой свой вход.
\end{definition}
\begin{theorem}
Проблемът дали детерминиран стеков автомат $A=\langle \Sigma,\Gamma,Q,s,\delta,Z,F\rangle$ е ацикличен
е разрешим за полиномиално време.
\end{theorem}
\begin{theorem}
За всеки детерминиран стеков автомат $A=\langle \Sigma,\Gamma,Q,s,\delta,Z,F\rangle$ ефективно може да получим еквивалентен ацикличен детерминиран
стеков автомат $A'$.
\end{theorem}
\begin{theorem}
За всеки ацикличен детерминиран стеков автомат $A=\langle \Sigma,\Gamma,Q,s,\delta,Z,F\rangle$, съществува константа $c=c(A)$, за която за всяка дума
$w\in \Sigma^*$ и всяко изпълнение:
\begin{equation*}
(s,w,Z) \Rightarrow_A^{(n)} (p_n,w_n,\gamma_n) 
\end{equation*}
е в сила, че $n\le c(|w|+1)$.
\end{theorem}
\begin{theorem}
За всеки детерминиран стеков автомат $A=\langle \Sigma,\Gamma,Q,s,\delta,Z,F\rangle$ ефективно може да намерим детерминиран стеков автомат $\overline{A}$ с език
$L(\overline{A})=\Sigma^*\setminus L(A)$. 
\end{theorem}
\begin{theorem}
За всеки детерминиран стеков автомат $A_S=\langle \Sigma,\Gamma,Q_S,s_S,\delta_S,Z,F_S\rangle$ и детерминиран краен автомат $A_D=\langle \Sigma,Q_D,s_D,\delta_D,F_D\rangle$ ефективно може да намерим:
\begin{enumerate} 
\item детерминиран стеков автомат $A$ с език:
\begin{equation*}
L(A) = L(A_S) \cap L(A_D)
\end{equation*}
\item детерминиран стеков автомат $A$ с език: 
\begin{equation*}
L(A) = \{\alpha \,|\, \exists \beta\in L(A_D) (\alpha\circ \beta\in L(A_S))\}.
\end{equation*}
\end{enumerate}
\end{theorem}
\begin{corollary}
Нека $\Sigma$ е азбука и $\$$ е символ извън $\Sigma$. Език $L\subseteq \Sigma^*$ се разпознава от детерминиран стеков автомат (с финални състояния) точно когато
$L\$$ се разпознава от детерминиран стеков автомат с празен стек.
\end{corollary}

\begin{definition}
За естествено число $k\in \mathbb{N}$ дефинираме $first_k:\Sigma^*\rightarrow \Sigma^{\le k}$ като:
\begin{equation*}
first_k(w) =\begin{cases} w\text{ ако } |w|\le k\\
u, \text{ за което } |u|=k \text{ и } w\in u\Sigma^*.
\end{cases}
\end{equation*}
\end{definition}
\begin{definition}
За контекстносвободна граматика $G=\langle \Sigma,{\cal N},S,R\rangle$ десен елемнтарен извод е:
\begin{equation*}
\alpha A w\Rightarrow_{rm} \alpha \beta w,
\end{equation*}
 където $w\in \Sigma^*$ и $A\rightarrow \beta\in R$. (Най-)Десен извод в $G$ е:
 \begin{equation*}
 \alpha_0\Rightarrow_{rm}\alpha_1\dots \Rightarrow_{rm} \alpha_n
 \end{equation*}
 за някое $n\ge 0$.  Стандартно използваме $\alpha_0\Rightarrow_{rm}^{(n)} \alpha_n$, за да подчертаем
 дължината на извода и $\alpha_0\Rightarrow_{rm}^{*} \alpha_n$, когато тя не ни интересува.
\end{definition}
\begin{definition}
За естествено число $k\in \mathbb{N}$ и контекстносвобдна граматика $G=\langle \Sigma,{\cal N},S,R\rangle$ казваме,
че $G$ е $LR(k)$ граматика, ако винаги, когато са изпълнени следните три условия:
\begin{enumerate}
\item $S\Rightarrow^*_{rm} \alpha A w\Rightarrow_{rm} \alpha \beta w$,
\item $S\Rightarrow^*_{rm} \alpha' A' w'\Rightarrow_{rm} \alpha' \beta' w'=\alpha\beta x$,
\item $first_k(w)=first_k(x)$,
\end{enumerate}
е в сила, че $\alpha A x= \alpha' A' w'$, в частност $\alpha=\alpha'$, $\beta=\beta'$ и $x=w'$.
\end{definition}
\begin{theorem}
За всеки детерминиран стеков автомат $A$, който разпознава с празен стек, има $LR(0)$-граматика $G$, за която
$L(A)=L(G)$. 
\end{theorem}
\begin{theorem}
Ако $\$$ е символ извън $\Sigma$ и $G=\langle \Sigma\cup \{\$\},{\cal N},S,R\rangle$ е $LR(0)$-граматика с език $L(G) \subseteq \Sigma^* \{\$\}$,
то има $LR(1)$-граматика $G_1$ с език $L(G_1)=L(G)\{\$\}^{-1}$. 
\end{theorem}
\begin{corollary}
Ако $A$ е детерминиран стеков автомат, то има $LR(1)$-граматика $G$ с език $L(A)=L(G)$. (тук автоматът разпознава с финални състояния!)
\end{corollary}

\begin{theorem}
За всяко $k\in \mathbb{N}$ проблемът дали $G=\langle \Sigma,{\cal N},S,R\rangle$ е $LR(k)$-граматика е разрешим. 
\end{theorem}

\begin{theorem}
За всяко $k\in \mathbb{N}$ и всяка $LR(k)$-граматика $G$ има детерминиран стеков автомат $A$ с език $L(A)=L(G)$.
\end{theorem}

\begin{theorem}
Проблемът:
\begin{alltt}
Вход: \(G=\langle \Sigma,{\cal{N}},S,R\rangle\)
Изход: да, ако има \(k\), за което \(G\) е \(LR(k)\)
	       не, иначе.
\end{alltt}
е неразрешим.
\end{theorem}


\section{Задачи}


\begin{problem}
  \marginnote{\scriptsize \cite[стр. 184]{papadimitriou}}
  Докажете, че $\texttt{2-SAT}$ проблемът е $\texttt{PTIME}$.
\end{problem}

\begin{problem}
  Докажете директно, че $\texttt{SAT}$ е $\texttt{NP}$-труден проблем
  като кодирате историята на едно изчисление на недетерминистична машина на Тюринг
  с формула в конюнктивна нормална форма.
\end{problem}

\begin{problem}
  % \marginnote{\cite[стр. 367]{hopcroft}}
  \marginnote{\scriptsize \cite[стр. 53]{garey-johnson}}
  $\texttt{Exact Cover}$ се нарича проблемът дали при дадено множество $S$ и негови подмножества $S_1,S_2,\dots,S_k$,
  съществува $T \subseteq \{1,2,\dots,k\}$, такова че 
  за всяко $x \in S$ има точно един индекс $i \in T$, за който $x \in S_i$.  
  Докажете, че $\texttt{Exact Cover}$ е $\texttt{NP}$-пълен проблем.
\end{problem}

\begin{problem}
  \marginnote{\scriptsize \cite[стр. 333]{hopcroft}}
  Докажете, че $\texttt{Hamilton Cycle}$ е $\texttt{NP}$-пълен проблем.
\end{problem}
\begin{hint}
  $\texttt{3-SAT}$ се свежда полиномиално към $\texttt{Hamilton Cycle}$.
\end{hint}

\begin{problem}
  \marginnote{\scriptsize \cite[стр. 60]{garey-johnson}}
  Нека имаме крайно множество $A$ и функция $s:A \to \mathbb{N}^+$.
  Проблемът за съществуването на $A' \subseteq A$ със свойството, че
  \[\sum_{a\in A'}s(a) = \sum_{a \in A\setminus A'} s(a)\]
  се нарича $\texttt{PARTITION}$.
  Докажете, че $\texttt{PARTITION}$ е $NP$-пълен проблем.
\end{problem}


\begin{problem}
  \emph{Двупосочен автомат} наричаме машина на Тюринг
  \[\mathcal{M}=\langle \Sigma,\Gamma,Q,s,\Delta,F,B\rangle,\] за която:
\begin{itemize}
\item $\Gamma=\Sigma\cup \{B,\#,\$\}$, като $B,\#,\$\not\in \Sigma$,
\item За всеки прехода $\langle (p,a),(q,b,--)\rangle\in \Delta$ е в сила, че $a=b\neq B$.
\end{itemize}
\emph{Език} на двупосочен автомат $M$ наричаме:
\begin{equation*}
{\cal L}(M)=\{\alpha\in \Sigma^*\,|\,\exists f\in F\exists \gamma\in \Gamma^*( (\varepsilon,s,\#\alpha\$\rangle)\Rightarrow^*_M (\gamma,f,\varepsilon))\}.
\end{equation*}
\begin{enumerate}
\item Да се докаже, че за всеки двупосочен автомат $M_1$ има двупосочен автомат $M_2$ над същата азбука, за който:
\begin{equation*}
{\cal L}(M_2) = \{\alpha\in \Sigma^* \,|\, \exists f\in F\exists \beta,\gamma\in \Gamma^*((\varepsilon,s,\#\alpha\$\rangle)\Rightarrow^*_M (\beta,f,\gamma))\}.
\end{equation*}
\item Да се опише конструкция, която по даден двупосочен автомат $M$ построява краен автомат $A$ с азбука $\Sigma$, за който:
\begin{equation*}
{\cal L}(M)={\cal L}(A).
\end{equation*}
\item Докажете, че описаната от Вас конструкция е коректна. 
\item Оценете броя на състоянията на построения от Вас автомат като функция на броя
на състоянията на изходния двупосочен автомат.
\end{enumerate}
\end{problem}
\begin{problem}
Дадена е азбука $\Sigma=\{a_1,a_2,\dots,a_n\}$ с $n\ge 2$ символа. За дума $w\in \Sigma^*$ с $|w|_i$ означаваме броя букви $a_i$ в $w$,
а с $\|w\|\in \mathbb{N}^n$ -- вектора $(|w|_1,|w|_2,\dots,|w|_n)$. За език $L\subseteq \Sigma^*$, ${\cal I}(L)=\{\|w\| \,|\, w\in L\}$.
\begin{enumerate}
\item Нека $u\in \mathbb{N}^n$ и $V\subseteq \mathbb{N}^n$ е множество с $m$ елемента $v_1,v_2,\dots,v_m$. Да се докаже, че има регулярен език $L(u,V)$, за който:
\begin{equation*}
{\cal I}(L(u,V)) = \{u +\sum_{i=1}^m d_i v_i\,|\, d_1,d_2,\dots,d_m\in \mathbb{N}\}.
\end{equation*}
\item Нека $A=\langle \Sigma,Q,S,\Delta,F\rangle$ е краен автомат. Опишете конструкция, която по $A$ намира естествено число $N$, вектори $u_1,u_2,\dots,u_N\in \mathbb{N}^n$ и крайни множества $V_1,V_2,\dots,V_N\subseteq \mathbb{N}^n$, за които:
\begin{equation*}
{\cal I}({\cal L}(A)) = \bigcup_{i=1}^N {\cal I}(L(u_i,V_i)).
\end{equation*} 
\item Докажете, че конструкцията Ви е коректна.
\end{enumerate}
\end{problem}
\begin{problem}
Разглеждаме следния проблем:
\begin{alltt}
Вход:\(M\) еднолентова машина на Тюринг.
Изход:\(k\in\mathbb{N}\) и \(M\sb{D}\) -- \(k\)-лентова детерминирана машина на Тюринг, 
\hspace{5cm}за която \(L(M\sb{D})=L(M)\).
\end{alltt}
\begin{enumerate}
\item Опишете конструкция, която решава горния проблем и има следното свойство: има полином $p(n)$, че за всяка машина на Тюринг
с пространствена сложност $Space_M(n) \in \mathcal{O}(s(n))$ е в сила, че $Space_{M_D}(n) \in \mathcal{O}(p(n)(s(n)+1))$.
\item Докажете, че Вашата конструкция е коректна.
\item Оценете степента на полинома $p(n)$.
\end{enumerate}
\end{problem}

\begin{problem}
Нека $A=\langle \Sigma,Q,s,\delta,F\rangle$ е тотален краен детерминиран автомат. С $L(p)$ означаваме езика на автомата
$A_p=\langle \Sigma,Q,p,\delta,F\rangle$. 
\begin{enumerate}
%\item Опишете $O(|\Sigma||Q|^2)$ процедура, която намира всички двойки $(p,q)\in Q\times Q$, за които $L(p)\subseteq L(q)$.
\item Опишете  процедура с времева сложност $\mathcal{O}(|\Sigma||Q|^3)$, която намира всички двойки $(p,q)\in Q\times Q$, за които $L(p)\subseteq L(q)$.
\item Докажете, че Вашата процедура е коректна.
\item Докажете, че $L(p)\subseteq L(q)$ точно когато:
\begin{equation*}
\forall \alpha\in \Sigma^*((|\alpha|\le 2|Q|\, \&\, \alpha\in L(p) )\Rightarrow \alpha\in L(q)).
\end{equation*}
\end{enumerate}
\end{problem}

\bibliographystyle{amsalpha}
\bibliography{mesi}


\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: