chapter-1.tex

\chapter{Способы задания и распознавания формальных языков}
\label{Chapter1}

\section{Алфавит и слова}
\label{Chapter1Alphabet}

Алфавитом будем называть любое множество символов. Предполагается,
что термин <<символ>> имеет достаточно ясный интуитивный смысл и не
нуждается в дальнейшем пояснении. Алфавит, вообще говоря, не обязан
быть ни конечным, ни даже счетным, но везде далее мы будем
предполагать его конечным. Термины <<буква>> и <<знак>> используются
как синонимы термина <<символ>> для обозначения элемента алфавита.
Термин <<буква>> будет для нас основным.

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

Слово называется пустым, если оно не содержит ни одной буквы. Это слово обозначается символом $\eps$.

\begin{myexample}
Латинский алфавит: множество, состоящее из 26 прописных и 26 строчных латинских букв; \emph{begin} --- слово в этом алфавите.
\end{myexample}

\begin{myexample}
Бинарный (или двоичный) алфавит: множество $(0;1)$; $001001$ --- слово в этом алфавите.
\end{myexample}

Определим две операции над словами:

\begin{enumerate}%
    \item
Если $\alpha$ и $\beta$ --- слова, то слово $\alpha\beta$ называется \mydef{конкатенацией} (\mydef{сцеплением}) $\alpha$ и $\beta$. Например, если $\alpha= \text{вино}$, $\beta=\text{град}$, то $\alpha\beta=\text{виноград}$. Для любого слова $\alpha$ всегда $\alpha\eps=\eps\alpha=\alpha$.

    \item
\mydef{Обращением} слова $\alpha$ называется слово $\alpha^R$, которое отличается от $\alpha$ только порядком следования входящих в него букв, т.е. если
 $a_1$, $a_2$, \ldots , $a_n$ --- буквы и $\alpha=a_1 \ldots a_n$, то $\alpha^R=a_n\ldots a_1$. Ясно, что
$\eps^R=\eps$. Например, если $\alpha= \text{нос}$, то $\alpha^R=\text{сон}$.
\end{enumerate}


Пусть $\alpha$, $\beta$ и $\gamma$ --- произвольные слова в некотором алфавите $\Sigma$. Назовем $\alpha$ \mydef{префиксом} слова $\alpha\beta$, а $\beta$ --- \mydef{суффиксом} слова $\alpha\beta$. Слово $\beta$ назовем подсловом слова $\alpha\beta\gamma$. Префикс и суффикс являются подсловами. Заметим, что пустое слово является префиксом, суффиксом и подсловом любого слова. Если $\alpha\neq\beta$ и $\alpha$ --- префикс слова $\beta$, то $\alpha$ называется собственным префиксом слова $\beta$; аналогично определяются собственные суффиксы и подслова.

Слова вида $aa$\ldots$a$ ($n$ букв) будем записывать короче: $a^n$.
Например:
\[aabbba=a^2b^3a, \qquad \eps=a^0.\]

\mydef{Длиной} слова будем называть число букв в нем. Длину слова $\alpha$ будем обозначать $|\alpha|$. Например, $|aab|=3,$ $|\eps|=0$.

\begin{myproblem}
Выясните, сколько букв в русском алфавите.
\end{myproblem}

\begin{myproblem}
Найдите все префиксы, суффиксы и подслова слова \emph{арбуз}.
\end{myproblem}

\section{Языки и операции над языками}
\label{Chapter1LangsOps}

\mydef{Языком} над алфавитом $\Sigma$ называется произвольное множество слов, записанных буквами из $\Sigma$. Под это определение, конечно, подходит почти любое известное понятие языка. Например, английский и русский языки, различные алгоритмические языки и т.~д.

Рассмотрим простейшие примеры языков над некоторым алфавитом $\Sigma$:
\begin{itemize}
    \item пустое множество $\es$;
    \item множество $\{\eps\}$, состоящее из одного пустого слова;
    \item множество $\{a\}$, где $a\in\Sigma$, состоящее из одного однобуквенного слова.
\end{itemize}
Отметим, что $\es$ и $\{\eps\}$ --- два различных языка.

Обозначим через $\Sigma^*$ множество, содержащее все слова в алфавите $\Sigma$, включая $\eps$. Пусть $\Sigma^+=\Sigma^* - \{\eps\}$. Например, если $\Sigma$ --- бинарный алфавит $\{0,1\}$, то
\[
    \Sigma^* = \{ \eps; 0; 1; 00; 01; 10; 11; 000; 001; \ldots \}.
\]
Каждый язык $L$ в алфавите $\Sigma$ является подмножеством множества $\Sigma^*$ и содержит язык $\es$. Отметим, что слово
``\emph{liFe}'', составленное из английских букв, не является словом английского языка, а слово <<жызнь>>, составленное из русских букв, не является словом русского языка.

\begin{myexample}
Рассмотрим язык $L_{1}$, содержащий все слова из нуля или более букв $a$. Тогда $L_1=\{a^i\mid i\ge0\}=\{a\}^*$.
\end{myexample}

В тех случаях, когда это не может привести к путанице, мы будем обозначать множество, состоящее из одного элемента, самим элементом. В соответствии с этим соглашением $a^*=\{a\}^*$.

Если язык $L$ таков, что произвольное слово из $L$ не может являться собственным префиксом (суффиксом) никакого другого слова из $L$, то говорят, что $L$ обладает префиксным (суффиксным) свойством. Например, язык $a^*$ не обладает префиксным свойством, а язык $\{a^ib \mid i \ge 0\}$ этим свойством обладает. В некотором смысле слова из языка, обладающего префиксным свойством, не продолжимы вправо, а слова из языка, обладающего суффиксным свойством, не продолжимы влево.

Рассмотрим некоторые операции над языками. Из того, что язык является множеством, вытекает, что операции объединения, пересечения и разности применимы к произвольным языкам. Операцию конкатенации можно применять к языкам так же, как и к словам: а именно, если $L_1$ --- язык в алфавите $\Sigma_1$, а $L_2$ --- язык в алфавите $\Sigma_2$, то язык $L_1L_2$, называемый конкатенацией (а также сцеплением или произведением) языков $L_1$, и $L_2$. определяется равенством:
\[
	L_1L_2 = \{xy \mid x\in L_1, y\in L_2\} \quad  (\subset\{\Sigma_1\cup\Sigma_2\}^*).
\]

Итерации языка 2 определяются следующим образом:
\begin{enumerate}
\item $L^0 = \{\eps\}$,
\item $L^n = LL^{n-1}$ для $n\ge1$,
\item $L^* = \bigcup_{n \ge 0} L^n$ --- полная итерация,
\item $L^+ = \bigcup_{n \ge 1}L^{n}$ --- позитивная итерация.
\end{enumerate}

Отметим, что
\[
	L^+ = LL^* = L^*L, \qquad  L^* = L^+\cup\{\eps\}.
\]

Пусть $\Sigma_1$ и $\Sigma_2$ --- алфавиты. Рассмотрим произвольное
отображение $h\colon \Sigma_1 \to \Sigma_2^*$ и расширим его до
отображения $\Sigma_1^*$ в $\Sigma_2^*$, полагая
\[
    h(\eps)=\eps, \quad h(xa)=h(x)(a)
\]
для всех $x\in\Sigma_1^*$ и $a\in\Sigma_1$. Легко
показать, что новое отображение определено корректно. Для него мы
сохраним символ $h$. Отображение $h\colon  \Sigma_1^*\to\Sigma_2^*$
называется \mydef{гомоморфизмом}.

Применяя гомоморфизм $h$ к языку $L$, мы получаем новый язык $h(L)$, который представляет собой множество слов $\{h(\omega)\mid\omega\in L\}$.

\begin{myexample}
Рассмотрим алфавиты $\Sigma_1=\{0;1\}$ и $\Sigma_2=\{a;b\}$. Пусть
\[
    L=\{0^n1^n\mid n\ge1 \}.
\]
Предположим, мы хотим заменить каждое вхождение буквы $0$ в словах из языка $L$ на букву $a$, а каждое вхождение буквы $1$ --- на $bb$. Тогда можно определить гомоморфизм $h$ так, что $h(0)=a, h(1)=bb$. В этом случае $h(L)=\{a^nb^{2n}\mid n\ge1 \}$.
\end{myexample}

Пусть $\Sigma_1$ и $\Sigma_2$ --- алфавиты, $L$ --- язык над алфавитом $\Sigma_2$. Рассмотрим произвольный гомоморфизм $h\colon \Sigma_1^*\to\Sigma_2^*$ . \mydef{Прообразом} языка $L$ называется язык
\[h^{-1}(L) = \bigcup_{y\in L}h^{-1}(y) = \{x\mid h(x)\in L\}\  (\subset\Sigma_1^*).\]

\begin{myexample}
Пусть $h\colon \{0;1\}^*\to\{a;b\}^*$ --- гомоморфизм, для которого
\[h(0)=h(1)=a.\] Тогда $h^{-1}(a)=\{0;1\},~h^{-1}(b)=\es$. Пусть
$L_1=\{b\}^*, L_2=\{a\}^*$. Тогда $h^{-1}(L_1)=\{\eps\}$, $h^{-1}(L_2)=\{0;1\}^*$.
\end{myexample}

\begin{myexample}
Пусть $h\colon \{0;1\}^*\to\{a;b\}^*$ --- гомоморфизм, для которого
$h(0)=a$, $h(1)=\eps$. Тогда $h^{-1}(\eps)=1^*,~h^{-1}(a)=\{1^i01^j\mid i,j\ge0\}$.
\end{myexample}

\begin{myproblem}
Верно ли, что $L^+=L^*-\{\eps\}$.
\end{myproblem}

\begin{myproblem}
Какие из следующих языков обладают префиксным (суффиксным) свойством?
\begin{itemize}
    \item $\es$;
    \item $\{\eps\}$;
    \item $\{a^nb^n\mid n\ge1 \}$;
    \item $L^*$, если $L$ обладает префиксным (суффиксным) свойством;
    \item $\{\omega\mid \omega\in\{a,b\}^*$ и число символов $a$ в $\omega$ равно числу символов $b\}$.
\end{itemize}
\end{myproblem}

\begin{myproblem}
Пусть $h\colon \{0;1;2\}^*\to\{a;b\}^*$ --- гомоморфизм, определённый равенствами $h(0)=a$, $h(1)=bb$ и $h(2)=\eps$. Опишите языки $h(\{012\}^*)$, $h(\{0;1;2\}^*)$, $h^{-1}(\{ab\}^*)$.
\end{myproblem}


\begin{myproblem}
Докажите или опровергните следующие утверждения:
\begin{gather*}
h^{-1}(h(L))=L, \\
h(h^{-1}(L))=L.
\end{gather*}
\end{myproblem}

\section{Грамматики}
\label{Chapter1Grammars}

\mydef{Грамматика} --- это математическая система, определяющая язык.
В грамматике $G$, определяющей язык $L$, используются два конечных непересекающихся множества символов: множество нетерминальных символов, которое часто будет обозначаться буквой $N$, и множество терминальных символов, обозначаемое обычно $\Sigma$. Из терминальных символов образуются слова языка $L$, а нетерминальные символы играют вспомогательную роль. Ядром грамматики является конечное множество $P$ правил образования, которые описывают процесс порождения слов языка.

Дадим теперь точное определение грамматики. \mydef{Грамматикой} называется четверка $G=(N,\Sigma,P,S)$, где $N$ --- конечное множество нетерминальных символов (алфавит нетерминалов), $\Sigma$ --- не пересекающееся с $N$ конечное множество терминальных символов (алфавит терминалов), $P$ --- конечное подмножество множества

\[
	(N\cup\Sigma)^*N(N\cup\Sigma)^* \times (N\cup\Sigma)^*.
\]
Пара $(\alpha,\beta)\in P$, где $\alpha\in(N\cup\Sigma)^*N(N\cup\Sigma)^*$,$\beta\in(N\cup\Sigma)^*$, называется \mydef{правилом} или \mydef{продукцией} и записывается в виде $\alpha\to\beta$. $S$ --- выделенный символ из $N$, называемый \mydef{начальным} или
\mydef{стартовым} символом.

\begin{myexample}
\label{example11}
Рассмотрим грамматику $G=(\{A;S\},\{0;1\},P,S)$, где $P$ состоит из продукций
\[	S \to 0A1,  \qquad
	S \to 01A01,\qquad
	S \to 00A1, \qquad
	A \to \eps.
\]
Нетерминальными символами в этой грамматике являются буквы $A$ и $S$, терминальными --- 0 и 1, а $S$ --- начальный символ.
\end{myexample}

Продукции с одинаковыми правыми частями будем иногда записывать в одну строчку через символ |, например, две первых продукции из примера~\ref{example11} будем записывать так:
\begin{equation}
\begin{array}{l}
	S \to 0A1 \mid 01A01.
\end{array}
\end{equation}

Грамматика определяет язык рекурсивным образом. Рекурсивность проявляется в определении особого рода слов, называемых выводимыми словами грамматики $G=(N,\Sigma,P,S)$: $S$ --- выводимое слово; если $\alpha\beta\gamma$ --- выводимое слово и $(\beta\to\delta)\in P$, то $\alpha\delta\gamma$ --- тоже выводимое слово; никакие другие слова нe являются выводимыми. Выводимое слово грамматики $G$. не содержащее нетерминальных символов, называется терминальным словом, порождаемым грамматикой $G$.

Язык $L(G)$, порождаемый грамматикой $G$, определяется как множество всех терминальных слов, порождаемых грамматикой $G$.

Пусть $G=(N,\Sigma,P,S)$ --- некоторая грамматика. Если $\alpha\beta\gamma\in(N\cup\Sigma)^*$ и $(\beta\to\delta)\in P$, то будем говорить, что слово $\alpha\delta\gamma$ непосредственно выводимо из $\alpha\beta\gamma$ и записывать это так: $\alpha\beta\gamma\to_G\alpha\delta\gamma$. В тех случаях, когда из контекста ясно, о какой грамматике идет речь, нижний индекс $G$ будем опускать. Через $\to^k$ будем обозначать $k$-ю степень отношения $\to$, т.е. будем записывать $\alpha\to^k\beta$, если существует последовательность $k+1$ слов $\alpha_0$, $\alpha_1$, $\ldots$ , $\alpha_k$, для которых $\alpha=\alpha_0$, $\alpha_{i-1}\to\alpha_i$ при $1\le i\le k$ и $\alpha_k=\beta$. Эта последовательность слов называется выводом длины $k$ слова $\beta$ из слова $\alpha$ в грамматике $G$. Транзитивное замыкание отношения $\to$ обозначим через $\to^+$; $\varphi\to^+\psi$  читается так: слово $\psi$ выводимо из $\varphi$ нетривиальным образом. Рефлексивное и транзитивное замыкание отношения $\to$ обозначим через $\to^*$; $\varphi\to^*\psi$ читается так: $\psi$ выводимо из $\varphi$. Отметим, что $\alpha\to^+\beta$ тогда и только тогда, когда $\alpha\to^i\beta$ для некоторого $i\ge 1$, а $\alpha\to^*\beta$ тогда и только тогда, когда $\alpha\to^i\beta$ для некоторого $i\ge 0$.
Таким образом, $L(G) = \{\omega\mid\omega\in\Sigma^*, S\to^*\omega\}$.

\begin{myproblem}
Рассмотрим грамматику $G=(\{A;S\},\{0;1\},P,S)$, где $P$ состоит из продукций:
\[
    S  \to 0A1,\qquad
    0A \to 00A1,\qquad
    A  \to \eps.
\]
Доказать, что $L(G)=\{0^n1^n\mid n\ge 1\}$.
\end{myproblem}

Приведем существенные для дальнейшего примеры грамматик.
\begin{myexample}
\label{exampleDigitsGrammar}
Пусть $G=(\{\emph{Ц}\}$,
$\{0;1;\ldots;9\}$,
${\emph{Ц} \to 0\mid1\mid\dots\mid9}$,
$\emph{Ц})$.
В грамматике $G$ единственный нетерминальный символ. Ясно, что $L(G)=\{0;1;\ldots;9\}$.
\end{myexample}

\begin{myexample}
\label{exampleArithmGrammar}
Пусть $G_0=(\{E;T;F\},~\{a;+;*;(;)\},P,E)$, где $P$ состоит из продукций:
\[	E  \to E+T \mid T,\qquad
	T  \to T*F \mid F,\qquad
	F  \to (E) \mid a.
\]
Пример вывода в этой грамматике:
\begin{multline*}
	E \To
    E+T \To 
    T+T \To \\
    F+T \To 
    a+T \To 
    a+T*F \To 
    a+F*F \To \\
    a+a*F \To 
    a+a*a.
\end{multline*}
Можно доказать, что язык $L(G_0)$ --- это множество арифметических выражений, построенных из пяти символов $+$, $*$, $a$, $($, $)$.
\end{myexample}

\begin{myexample}
\label{exampleAnBnCnGrammar}
Рассмотрим грамматику $G=(\{B;C;S\},\{a,b,c\},P,S)$, где $P$ состоит из продукций:
\begin{align*}
	S  &\to aSBC \mid abC,&
	CB &\to BC,&
	bB &\to bb,\\
	bC &\to bc,&
	cC &\to cc.&&
\end{align*}
Пример вывода в этой грамматике:
\[
	S \To 
    aSBC \To
    aabCBC \To 
    aabBCC \To
    aabbCC \To 
    aabbcC \To
    aabbcc.
\]
Можно формально доказать, что эта грамматика порождает язык $\{a^nb^nc^n\mid n \ge1\}$.
\end{myexample}

\begin{myexample}
\label{exampleFreeGrammar}
Пусть $G=(\{A;B;C;D;S\},\{a;b\},P,S)$, где $P$ состоит из продукций:
\begin{align*}
	S  &\to CD, &
    Ab &\to bA, &
	C  &\to aCA \mid bCB \mid \eps, &
    Ba &\to aB, \\
	AD &\to aD, &
    Bb &\to bB, &
	BD &\to bD, &
    Aa &\to aA,\\
	D  &\to \eps. &&&
\end{align*}
Пример вывода в этой грамматике:
\begin{multline*}
	S \To
    CD \To 
    aCAD \To
    abCBAD \To 
    abBAD \To \\
    abBaD \To
    abaBD \To 
    ababD \To 
    abab.
\end{multline*}
Покажем, что $L(G)=\{\omega\omega\mid\omega\in\{a,b\}^*\}$, т.е. язык $L(G)$ состоит из слов четной длины, составленных из букв $a$ и $b$, причем первая половина каждого слова совпадает со второй половиной.

Сначала докажем, что $\{\omega\omega\mid\omega\in\{a,b\}^*\}\subseteq L(G)$. Для этого надо проверить, что каждое слово вида $\omega\omega$ можно вывести из $S$. Непосредственно проверяется, что в $G$ возможны следующие выводы:
\begin{enumerate}
	\item $S \To CD$
	\item $C \To^n~c_1c_2\ldots c_nCX_nX_{n-1}\ldots X_1 \To c_1c_2\ldots c_nX_nX_{n-1}\ldots X_1$,  где для всех $i$ $c_i=a$ тогда и только тогда, когда $X_i=A$, и $c_i=b$ тогда и только тогда, когда $X_i=B$;
	\item
\begin{multline*}
    X_n\ldots X_2X_1D \To X_n\ldots X_2c_1D \To^{n-1} c_1X_n \ldots X_2D \To \\
     c_1X_n\ldots X_3c_2D \To^{n-2} c_1c_2X_n \ldots X_3D \To \dots \To \\
     c_1c_2\ldots c_{n-1}X_nD \To c_1c_2\ldots c_{n-1}c_nD \To c_1c_2\ldots c_{n-1}c_n.
\end{multline*}
\end{enumerate}

В 2) из $C$ выводится слово, составленное из букв $a$ и $b$, за которым следует его зеркальное отражение, составленное соответственно из букв $A$ и $B$.

В 3) нетерминалы $A$ и $B$ перемещаются к правому концу слова, где $A$ становится терминалом $a$, а $B$ становится терминалом $b$, вступая в контакт с нетерминалом $D$. Нетерминалы $A$ и $B$ могут превратиться в терминалы единственным способом --- только передвинувшись к правому концу слова. При этом слово, составленное из букв $A$ и $B$, будет обращено и совпадет, таким образом, со cловом с буквами $a$ и $b$, выведенным из $C$ в выводе 2).

Комбинируя выводы 1), 2) и 3), получаем для $n\ge 0$
\[
	S \To^*~c_1c_2\ldots c_nc_1c_2\ldots c_n,
\]
где $c_i\in\{a,b\}$ для $1\le i\le n$. Итак, $\{\omega\omega\mid\omega\in\{a,b\}^*\}\subseteq L(G)$.

Теперь докажем, что $L(G)\subseteq\{\omega\omega\mid\omega\in\{a,b\}^*\}$. Для этого надо проверить, что из $S$ выводятся только те терминальные слова, которые имеют вид $\omega\omega$. Зададим два гомоморфизма:

\[
	g\colon\{a;b;A;B\}^* \to \{a;b;A;B\}^*, \qquad
    h\colon\{a;b;A;B\}^* \to \{a;b;A;B\}^*,
\]
удовлетворяющие условиям:
\begin{align*}
    g(a)&=a, &
    g(b)&=b,  &
    g(A)&=g(B)=\eps, \\
    h(A)&=A,  &
    h(B)&=B,  &
    h(a)&=h(b)=\eps.
\end{align*}
Применяя метод математической индукции по параметру $m$ и анализируя множество продукций $P$, легко доказать следующее вспомогательное утверждение: если $S \To^m \alpha$, то $\alpha$ представимо в виде
\[
    c_1c_2\ldots c_nU\beta V,
\]
где $c_i\in\{a;b\}$, $U\in\{C;\eps\}$, $V\in\{D;\eps\}$, а $\beta$ такое слово длины $n$ из языка $\{a;b;A;B\}^*$, что
\[
    g(\beta)=c_1c_2\ldots c_i, \qquad
    h(\beta)=X_nX_{n-1}\ldots X_{i+1},
\]
где
\[
    X_j =
        \begin{cases}
            A, \text{ если $c_{j}=a$;} \\
            B, \text{ если $c_{j}=b$.}
        \end{cases}
\]
Из этого утверждения вытекает, что все слова из $L(G)$ имеют вид
\[
    c_1c_2\ldots c_nc_1c_2\ldots c_n,
\]
где $c_i\in\{a,b\}$, поэтому $L(G)\subseteq\{\omega\omega\mid\omega\in\{a,b\}^*\}$.

Итак, равенство $L(G)=\{\omega\omega\mid\omega\in\{a,b\}^*\}$ доказано.
\end{myexample}

\begin{myproblem}
Докажите, что язык $L(G_0)$ из примера~\ref{exampleArithmGrammar} совпадает со множеством всех арифметических выражений, построенных из пяти символов:
\[
    +, \quad *, \quad a, \quad (, \quad ).
\]
\end{myproblem}

\begin{myproblem}
Докажите, что грамматика из примера~\ref{exampleAnBnCnGrammar} порождает язык \[\{a^nb^nc^n\mid n\ge 1\}.\]
\end{myproblem}

\section{Классификация грамматик}
\label{Chapter1GrammarsClasses}

В соответствии с подходом Хомского грамматики классифицируют по структуре их продукций. Грамматика $G=(N,\Sigma,P,S)$ называется:
\begin{enumerate}
    \item \mydef{праволинейной}, если каждая продукция из $P$
    имеет вид
    $A \to xB$ или $A \to x$, где $A,B \in N$, $x\in\Sigma^*$;

    \item \mydef{контекстно-свободной} (или \mydef{бесконтекстной}),
    если каждая продукция из
    $P$ имеет вид $A \to \alpha$, где $A \in N$,
    $\alpha\in(N\cup\Sigma)^*$;

    \item \mydef{контекстно-зависимой} (или \mydef{неукорачивающейся}),
    если каждая продукция из $P$ имеет вид
    $\alpha\to\beta$, где $|\alpha| \le |\beta|$.
\end{enumerate}

Грамматика, не удовлетворяющая ни одному из указанных ограничений,
называется грамматикой общего вида (или без ограничений). Далее мы
будем пользоваться сокращениями ПЛ, КС и КЗ для терминов
«праволинейный», «кон\-текс\-тно"/свободный» и «контекстно"/зависимый»
соответственно.

Грамматика примера~\ref{exampleDigitsGrammar} --- праволинейная. Такой же является и грамматика $G=(\{S\},\{0;1\},\{S\to0S\mid1S\mid\eps\},S)$ с языком $\{0,1\}^*$.

Примером КС-грамматики служит грамматика из примера~\ref{exampleArithmGrammar}. Ясно, что
каждая ПЛ-грамматика является контекстно-свободной.

В примере ~\ref{exampleAnBnCnGrammar} грамматика является контекстно-зависимой.

КЗ-грамматика не допускает продукций вида $A\to\eps$, называемых
$\eps$"/продукциями. Поэтому КС-грамматика, содержащая
$\eps$"/продукции, не является КЗ-грамматикой.

Если язык $L$ порождается грамматикой типа $i$, то $L$ называется
языком типа $i$. Таким образом, язык $L(G)$ примера~\ref{exampleDigitsGrammar} ---
праволинейный, язык $L(G_0)$ примера~\ref{exampleArithmGrammar} --- контекстно-свободный, а
язык $L(G)$ примера~\ref{exampleAnBnCnGrammar} --- контекстно-зависимый. Язык, порожденный
грамматикой примера~\ref{exampleFreeGrammar}, --- это язык без ограничений.

Если язык задан какой-то грамматикой, это еще не значит, что его нельзя породить менее мощной грамматикой. Например, КС-грамматика
\[
	G=(\{A;S\}, \{0;1\}, \{S\to AS \mid \eps; A \to 0 \mid 1 \}, S)
\]
порождает язык $\{0;1\}^*$, который, как отмечено выше, можно
получить и с помощью ПЛ"/грамматики.

Определенные выше четыре типа грамматик и языков называют
\mydef{иерархией Хомского}.

\begin{myproblem}
Постройте ПЛ-грамматику для языка, состоящего из идентификаторов, которые могут быть произвольной длины, но должны начинаться с буквы (как в Алголе).
\end{myproblem}

\begin{myproblem}
Постройте ПЛ-грамматику для языка, состоящего из идентификаторов, которые должны содержать от одного до шести символов и начинаться с буквы $I$, $J$, $K$, $L$, $M$ или $N$(как идентификаторы целых переменных в Фортране).
\end{myproblem}
\begin{myproblem}
Постройте КС-грамматику, порождающую язык
\[
	(a_1a_2 \ldots a_na_n \ldots a_2a_1 \mid
    	a_i\in\{0,1\}, 1\le i\le n\}.
\]
\end{myproblem}

\section{Распознаватели}
\label{Chapter1Parsers}

В~\ref{Chapter1Grammars} было отмечено, что грамматика --- это математическая
система, определяющая язык. Второй метод, обеспечивающий
задание языка конечными средствами, состоит в использовании
\mydef{распознавателей}. Распознаватель это очень схематизированный
алгоритм, определяющий некоторое множество. В нём можно
выделить три основные части: \mydef{входную ленту} ВЛ,
\mydef{управляющее устройство} с конечной памятью УУ, \mydef{вспомогательную} или \mydef{рабочую память} РП.

Входная лента (ВЛ) --- это линейная последовательность ячеек,
причем каждая
ячейка содержит точно одну букву из некоторого конечного входного
алфавита. Самую левую и самую правую ячейки могут занимать особые
концевые маркеры; причем маркер может стоять только на правом конце
ленты, или маркеров может не быть совсем.

Входная головка в каждый данный момент читает одну входную ячейку.
За один шаг работы распознавателя входная головка может
сдвинуться на одну
ячейку влево, остаться неподвижной или сдвинуться на одну ячейку
вправо. Распознаватель, который никогда не передвигает свою входную
головку влево, называется  односторонним. Обычно предполагается, что
входная головка только читает, т.е. в ходе работы распознавателя
буквы на входной ленте не меняются. Но можно рассматривать и такие
распознаватели, входная головка которых и читает, и пишет.

Рабочей памятью (РП) распознавателя может быть любого типа хранилище
информации. Предполагается, что алфавит памяти конечен и хранящаяся в
памяти информация образована только из букв этого алфавита.
Предполагается также, что в любой момент времени можно конечными
средствами описать содержимое и структуру памяти, хотя с течением
времени объем памяти может становиться сколь угодно большим.

Ядром распознавателя является управляющее устройство с конечной памятью
(УУ), под которым можно понимать программу, управляющую поведением
распознавателя. УУ представляет собой конечное множество состояний
вместе с функцией, которое описывает, как меняются состояния в
соответствии с текущим входным символом и текущей информацией,
извлеченной из памяти. УУ определяет также, в каком направлении
сдвинуть входную головку и какую информацию поместить в память.

Распознаватель работает, проделывая некоторую последовательность
\mydef{шагов} (или \mydef{тактов}). В начале такта читается
текущий входной символ и исследуется память. После этого с
распознавателем происходит следующее:
\begin{enumerate}
    \item входная головка сдвигается на одну ячейку влево, одну ячейку вправо
или сохраняется в исходном положении;

    \item в память помещается некоторая информация;

    \item изменяется состояние управляющего устройства.
\end{enumerate}

Поведение распознавателя удобно описывать в терминах
\mydef{конфигураций}
распознавателя, которые описывают состояние УУ, содержимое ВЛ
вместе с положением входной головки и, наконец, содержимое
РП. Во множестве всех состояний выделяют начальное состояние
и множество заключительных
состояний. Конфигурация называется \mydef{начальной},
если УУ находится в начальном состоянии, входная головка
читает самую левую
букву на ВЛ, и РП имеет заранее установленное начальное
содержимое. Конфигурация называется \mydef{заключительной}, если УУ находится в
заключительном состоянии, а входная головка читает правый концевой
маркер или, если маркер отсутствует, сошла с правого конца входной
ленты. (Иногда требуют, чтобы РП в заключительной конфигурации тоже
удовлетворяла некоторым условиям.)

Говорят, что распознаватель \mydef{допускает} входное слово $\omega$,
если, начиная с начальной конфигурации, в которой слово $\omega$
записано на входной ленте, распознаватель может проделать
последовательность шагов, заканчивающуюся заключительной
конфигурацией. Язык, определяемый распознавателем, --- это множество
входных слов, которые он допускает.

Для каждого класса грамматик из иерархии Хомского существует
естественный класс распознавателей, определяющий тот же класс языков.
Некоторые из таких распознавателей будут изучаться далее.

\section{Упражнения}
\label{Chapter1Exs}

Для каждой грамматики, встречающейся в заданиях, следует указать её тип (в
иерархии Хомского). Написать грамматику, порождающую:
\begin{enumerate}
 \item язык $\Sig^{\ast}$, где (a) $\Sig = \{0, 1\}$; (b) \Sig{}~— произвольный
 (конечный) алфавит;

 \item некоторый конечный язык $L = \{\omega_i\}^n_{i=1}$;

 \item $\{a^{+}b^{+}\}, \{a^nb^n \mid n \in \N\}, \{a^nb^na^m \mid m, n \in
     \N\}$; $\{ a^nb^nc^n \mid n \in \N \}$;

 \item множество правильных скобочных последовательностей («язык Дика») с
     одним типом скобок;
 \item множество правильных скобочных последовательностей («язык Дика») с
     двумя типами скобок;
  \item арифметическую прогрессию $\{a + nd \mid n \in \NO\}$, $d > 0$, $0
    \leqslant a < d$ (имея в виду изоморфизм моноидов $(\NO, +) \cong
    (\{|\}^{\ast}, {\cdot})$, где ${\cdot}$ означает операцию конкатенации);
   \item язык, являющийся объединением конечного числа арифметических прогрессий.
\end{enumerate}