intro.tex

\addchap{Введение}
\label{Intro}
В настоящее время в связи с бурным развитием информационных технологий и расширением сферы их применения в теоретической информатике возникают новые и развиваются старые направления. Всё это находит своё отражение в формировании учебных дисциплин по направлению <<Фундаментальная информатика и информационные технологии>>. 

Целью изучения дисциплины <<Теория конечных автоматов и формальных языков>> является выработка у студентов компетенций, связанных с теоретическими понятиями, идеями, методами, моделями, алгоритмами, применяемыми при разработке и сопровождении проблемно-ориентированных языков. Эта дисциплина содержит сведения, необходимые для научно-исследовательской и практической работы в области системного программирования, использования и развития языков программирования.

К основным задачам дисциплины относятся: 
\begin{itemize}
\item освоение математических основ теории формальных языков; изучение классов формальных языков и конечных способов задания потенциально бесконечных множеств; овладение методами разбора слов, принадлежащих языку, определения эквивалентности выводов, установление однозначности грамматик;
\item освоение математических основ теории регулярных языков и выражений; изучение свойств регулярных выражений; 
\item овладение методами построения регулярных выражений для языков, заданных неформально и в виде формальных грамматик; освоение методов перехода от грамматики к регулярному выражению и наоборот;
\item освоение математических основ теории детерминированных и недетерминированных конечных автоматов; изучение общей схемы автомата-распознавателя; освоение метода редукции недетерминированного автомата к детерминированному; овладение методами построения конечного автомата по регулярной грамматике; изучение свойств праволинейных, регулярных и автоматных языков;
\item освоение понятия конечного автомата со спонтанными переходами; овладение методами построения конечного автомата по праволинейной грамматике и вычисления языка конечного автомата с помощью последовательного исключения состояний; изучение понятий отношения эквивалентности на множестве конечных автоматов, недостижимых состояний автомата;
\item изучение задачи минимизации детерминированного конечного автомата; освоение понятий различимых и неразличимых состояний и метода построения системы отношений неразличимости состояний конечного автомата; 
\item овладение методами определения регулярности языка; изучение алгоритмических проблем регулярных языков;
\item освоение математических основ теории контекстно-свободных (КС) языков; изучение понятий дерева вывода в КС-грамматике; овладение методами проверки КС-грамматики на непустоту, построения по КС-грамматике стабилизационного множества, построения приведенной КС-грамматики; изучение нормальных форм Хомского и Грейбах КС-языков; освоение метода определения принадлежности цепочки языку, заданному КС-грамматикой;
\item освоение математических основ теории автоматов с магазинной памятью (МП-автоматов); изучение понятия недетерминизма для МП-автоматов, расширенной формы МП-автомата (РМП-автомат), автомата, допускающего язык опустошением магазина (МП$\eps$-автомат); овладение методами перехода от МП-автомата к МП$\eps$-автомату и наоборот; 
\item овладение методом построения МП$\eps$-автомата по КС-грамматике; овладение методом перехода от МП$\eps$-автомата к КС-грамматике. 
\end{itemize}

Исчерпывающее изложение элементов теории формальных языков и конечных автоматов имеется в ставшей редкостью замечательной монографии А. Ахо и Дж. Ульмана~\cite{AU}, материалы которой в современной форме представлены в~\cite{Hop}. Настоящий учебник содержит систематическое изложение значительной части материала курса <<Теория конечных автоматов и формальных языков>> в объёме, достаточном для успешного его освоения. При изложении материала мы пытались придерживаться канонов монографии А. Ахо и Дж. Ульмана~\cite{AU}, опуская, однако, более глубокие аспекты рассматриваемой теории, на которые не достает времени в рамках данного курса. По курсу <<Теория автоматов и формальных языков>> можно порекомендовать ряд хороших книг, названия некоторых содержатся в списке литературы. 

Учебник состоит из введения, восьми глав, списка литературы и четырёх приложений. В главе~\ref{Chapter1} идет речь о способах задания и распознавания формальных языков; в главе~\ref{Chapter2} исследуются регулярные языки; в главах~\ref{Chapter3} и~\ref{Chapter4} изучаются разные типы конечных автоматов и доказывается совпадение классов конечно-автоматных, регулярных и праволинейных языков; в главе~\ref{Chapter5} изучается булева алгебра регулярных языков, свойства замкнутости операций над регулярными множествами и алгоритмические проблемы регулярных языков; в главах~\ref{cfg-intro} и~\ref{normal-cfg} исследуются контекстно-свободные грамматики и языки; в главе~\ref{Chapter8FSMSM} устанавливается связь между контекстно"/свободными языками и конечными автоматами с магазинной памятью. Каждая глава снабжена набором упражнений для лучшего понимания и усвоения материала. В учебнике имеется четыре приложения, которые содержат алгоритмы для контекстно"/свободных грамматик, задания к курсовой работе и варианты к ним, пример выполнения одного варианта курсовой работы. Мы благодарны Артёму Коненко за исходные коды последнего.

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

Нумерация всех утверждений имеет вид: $\alpha.\beta.\gamma$, где $\alpha$ --- номер главы, $\beta$ --- номер раздела главы, $\gamma$ --- номер утверждения в разделе. Формулировки теорем, лемм и утверждений заканчиваются символом $_\square$, а доказательства заканчиваются символом $\blacksquare$. Формулировки упражнений заканчиваются символом $\square$, а окончания примеров помечаются символом $\blacksquare$.

В тексте не выделяются и не нумеруются определения, однако некоторые важные понятия, появляющиеся по ходу изложения, набраны \mydef{курсивом}.

Мы благодарны С.~Борисову и И.~Сороканюку за помощь в наборе текста. О всех найденных в тексте ошибках и опечатках следует сообщать по адресу электронной почты a.pelenitsyn@gmail.com.