app-coursew-tasks.tex

\renewcommand{\theAlgoEnv}{\Alph{chapter}.\arabic{AlgoEnv}}

\chapter{Задание к курсовой работе}
\begin{itemize}
\item[1.] Для языка $L$, выбранного в соответствии с вариантом, выполнить следующее задание:
\begin{itemize}
\item[(i)] Построить ПЛ-грамматику $G$, порождающую $L$;
\item[(ii)] Доказать вложения $L\subseteq L(G)$, $L(G)\subseteq L$;
\item[(iii)] Путем решения системы линейных уравнений с регулярными коэффициентами построить регулярное выражение, описывающее $L$;
\item[(iv)] Построить НКА или $e$-НКА $M^{ND}$, распознающий язык $L$, предъявить его граф;
\item[(v)] Построить ДКА $M^{D}$ путем детерминизации $M^{ND}$, предъявить его граф;
\item[(vi)] Доказать, что $L(M^{ND})=L(M^{D})=L$;
\item[(vii)] Минимизировать полученный конечный автомат, распознающий язык $L$, или доказать его минимальность;
\item[(viii)] Методом последовательного исключения состояний выписать регулярные выражения для $L(M^{ND})$, $L(M^{D})$;
\item[(ix)] Постоить ДКА $\overline{M^D}$, распознающий дополнение $\overline{L}$ к языку $L$, записать $\overline{L}$ в виде регулярного выражения;
\item[(x)] На произвольно выбранном языке программирования написать программу, позволяющую распознать принадлежность вводимой строки языку $L$.
\end{itemize}

\item[2.] Для множества слов $A$ над алфавитом $\Sigma$, заданных в соответствии с вариантом, выполнить следующее задание:
\begin{itemize}
\item[(i)] Для каждого слова $w_i\in A$ построить НКА $M^{ND}_i$, распознающий наличие в произвольной строке $s\in\Sigma^\ast$ подстроки $w_i$;
\item[(ii)] Для каждого НКА $M^{ND}_i$ построить соответствующий ДКА $M^D_i$;
\item[(iii)] На произвольно выбранном языке программирования написать программу, позволяющую подсчитать количество вхождений каждого слова из множества $A$ во входную строку $s\in\Sigma^\ast$ (при этом программно реализовать хотя бы один автомат $M^{ND}_i$ и хотя бы один автомат $M^D_j$).
\end{itemize}

\pagebreak

\item[3.] Для языков $L_1$, $L_2$, выбранных в соответствии с вариантом, выполнить следующее задание:
\begin{itemize}
\item[(i)] Вычислить регулярное выражение, определяющее язык $L_1\cap L_2$;
\item[(ii)] Вычислить регулярное выражение, определяющее язык $L_1\Delta L_2$;
\item[(iii)] Определить: совпадают ли языки $L_1$ и $L_2$, является ли $L_1$ дополнением $L_2$;
\item[(iv)] Построить $e$-НКА, распознающий один из языков $L_1^R$ или $L_2^R$;
\item[(v)] Вычислить регулярное выражение по построенному $e$-НКА;
\item[(vi)] Построить $e$-НКА, распознающий один из языков $L_1L_2$, $L_1\cup L_2$ или $L_1^\ast$;
\item[(vii)] Детерминизировать один из построенных $e$-НКА;
\item[(viii)] На произвольно выбранном языке программирования написать программу, реализующую какой-либо $e$-НКА и какой-либо ДКА из этого пункта.
\end{itemize}