 \documentclass[12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{verbatim}
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}

%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\theoremstyle{definition}
\newtheorem{Example}{Пример}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\emptyset
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\abstractname{}

\let\yield\Rightarrow
\def\yields{\Rightarrow^*}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\let\w\omega

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}
\def\first{\mathrm{ FIRST} }
\def\follow{\mathrm{ FOLLOW} }
\def\LL{{\mathrm{LL}}}
\def\LR{{\mathrm{LR}}}
\def\id{{\mathrm{id}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{xparse}
\usepackage{ifthen}
\usepackage{bm} %%% bf in math mode
\usepackage{color}
%\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{Gray555}{HTML}{555555}
\definecolor{Gray444}{HTML}{444444}


\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\newcounter{prvar}


\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prpfrom[#1]{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem~(№#1 из задания).  }\setcounter{subproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem . }\setcounter{subproblem}{0}}

\def\prpvar{\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;({\rm\Rnum{\theprvar}}).  }\setcounter{subproblem}{0} }
\def\prpv{\medskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0} }
\def\prv{\medskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}. \setcounter{subproblem}{0} }

\def\prpstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^{^\dagger}$\negthickspace. }\setcounter{subproblem}{0}}
\def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}{\sf \thesubproblem .} }
\def\prsubr{\medskip\noindent\stepcounter{subproblem}{\sf \thesubproblem)} }
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}{$\mathsf{\thesubproblem^*}$\negthickspace.} }
\def\prsubrstar{\medskip\noindent\stepcounter{subproblem}{\sf $\mathsf{\thesubproblem^*}$)  } }

\newcommand{\bracketspace}[1]{\phantom{(}\!\!{#1}\!\!\phantom{)}}

\DeclareDocumentCommand{\Prpvar}{ O{null} O{} }{
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem 
% 	\ifthenelse{\equal{#1}{null}}{  }{ {\sf $\bm\langle$\bracketspace{#1}$\bm\rangle$}}
%	~\!\!(\bracketspace{{\rm\Rnum{\theprvar}}}).  }\setcounter{subproblem}{0} 
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{0} 
%
	\,{\sf $\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}}.

}
%\DeclareDocumentCommand{\Prpvar}{ O{level} O{meta} m }{\prpvar}


\DeclareDocumentCommand{\Prp}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача \theproblem 
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}
%\DeclareDocumentCommand{\Prp}{ O{level} O{meta} }

\DeclareDocumentCommand{\Prps}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^* $
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}

\DeclareDocumentCommand{\Prpd}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^\dagger$ 
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}


\def\prend{
	\bigskip
	\bigskip
}


\def\quotient{\backslash\negthickspace\sim}
\usepackage{enumitem}

\begin{document}
\centerline{\LARGE Задание 10}

\medskip

\begin{center}
	{\Large  КС-языки: замкнутость и LL-анализ}
\end{center}

\bigskip



{\bf Ключевые слова }\footnote{минимальный необходимый объем понятий и навыков по
этому разделу)}:{\em  язык, контекстно-свободный язык, магазинный автомат, грамматика, метод математической индукции. %примеры нерегулярных языков;
%поиск подстрок, алгоритм Кнута- Морисса- Пратта.

%языки скобочных выражений (языки Дика). 
}

\section{Лемма о накачке}

Одна из целей изучения леммы о накачке для регулярных языков -- упрощение понимания леммы о накачке для КС-языков, где она уже жизненно необходима. Сформулируем лемму.

\begin{Lemma}
	Для любого КС-языка $L$ существует константа $p$, такая что для любого слова $w$ из языка $L$, такого что $|w| \geq p$ существует разбиение слова $w = xuyvz$, причём
	\begin{itemize}
		\item $|uyv| \leq p$
		\item $|uv|\geq 1$
		\item $\forall i \geq 0: w_i = xu^iyv^iz \in L$
	\end{itemize}
\end{Lemma} 

\begin{Example} 
	Язык $L = a^nb^nc^n$ не является КС-языком.
\end{Example}
\begin{proof}
	Предположим, что $L\in \CFL$, тогда для некоторого числа $p$ выполнена лемма о накачке. Рассмотрим слово $w = a^pb^pc^p$ (заметим, что число $p$ является параметром, а не каким-то конкретным числом). Тогда подслово $uyv$ из разбиения слова $w$, существующего по лемме о накачке, либо состоит из одинаковых букв ($a^l$ или $b^l$ или $c^l$) или имеет вид $a^lb^r$ или $b^lc^r$. Три различные буквы подслово $uyv$ содержать не может, поскольку его длина ограниченна числом $p$. Но тогда $uv$ -- слово, в котором нет одной из трёх букв. Пусть это будет буква $c$ для определённости. Взяв $i = 0$, получаем, что по лемме о накачке $w_0 = a^{n-k}b^{n-m}c^n \in L $, при этом $k+m \geq 1$, откуда следует, что слово $w_0$ не принадлежит языку $L$. 
\end{proof}

\upr Покажите, что КС-языки замкнуты относительно объединения.

\upr Покажите, что КС-языки не замкнуты относительно пересечения.

\upr Покажите, что КС-языки не замкнуты относительно дополнения.
\prend
%\prp Покажите, что КС-языки замкнуты относительно пересечения с регулярными. То есть, если $L \in \CFL, R \in \REG$, то $L \cap R \in \CFL $.

%\prpstar Решите предыдущую задачу используя представление КС-языка не МП-автоматом, а грамматикой.

%\smallskip
%\noindent \textbf{Указание:} пусть регулярный язык задан конечным автоматом, тогда постройте грамматику $G^\prime$ для языка $L \cap R$, используя грамматику $G$, порождающую язык $L$, которая будет иметь нетерминалы вида $[qXp]$, где $q \in Q_\A$, $X \in N_G$.

%\prp Докажите, что язык $\{ w\,|\, |w|_a = |w|_b = |w|_c \} \subseteq \{a,b,c\}^*$ не является КС-языком.

%\prp Докажите, что дополнительный язык к языку $U = \{ a^nb^nc^n \mid n=0,1,\ldots \}$  является КС-языком.
%\prp Верно ли, что язык $\Sigma^*\setminus \{ a^nb^nc^n \mid n\geq 0  \}$ совпадает с языком $\{a^ib^jc^k \mid i\neq j \lor i \neq k \}^*$.

\prp Постройте КС-грамматику, порождающую язык $\Sigma^*\setminus \{ a^nb^nc^n \mid n\geq 0  \}$. % совпадает с языком $\{a^ib^jc^k \mid i\neq j \lor i \neq k \}^*$.

\prend

\prp Верно ли, что язык $\{ a^nb^mb^nc^m \,|\, n, m \geq 0 \}$ является КС-языком? В случае положительного ответа построить КС-грамматику или МП-автомат для данного языка.
\prend

\prp  Пусть $A, B \in \CFL,\, R \in \REG$. Верны ли следующие утверждения (для произвольных $A, B, R$):$$\prsubr\; A\setminus R \in \CFL; \qquad\qquad \prsubr\; R\setminus A \in \CFL; 		\qquad\qquad \prsubr\; A^R \in \CFL?$$
%\prend

\prp Докажите, что язык $\{ wtw^R \mid |w|=|t| \} \subseteq \{a,b\}^*$ не является КС-языком.
\prend


\begin{comment}
	


\prp Являются ли следующие языки над алфавитом $\Sigma=\{a,b\}$ КС-языками? Регулярными языками?

\prsub $L_{x} = \{ xy : |x| < |y|, \text{ x содержит букву $b$ }  \}$.

\prsub $L_{y} = \{ xy : |x| < |y|, \text{ y содержит букву $a$ }  \}$.
\prend

\prdag Докажите, что КС-языки замкнуты относительно операции подстановки. То есть, если $L $ -- КС-язык над алфавитом $\Sigma = \{\sigma_1,\ldots \sigma_n\}$, а $L_{\sigma_1},L_{\sigma_2}, \ldots, L_{\sigma_n}$ -- КС-языки, над алфавитом $\Delta$, то язык $$ \bigcup\limits_{w \in L} L_{w_1}\cdot L_{w_2} \cdot\ldots \cdot L_{w_n}, \text{ где } w_i \in \Sigma$$  является КС-языком.
\end{comment} 

%\prp Докажите, что язык $\{ w\,|\, w = uu, u \in \Sigma^* \}, \Sigma = \{a,b\}$,  не является КС-языком\footnote{Так как дополнение к этому языку -- язык
%неквадратов является КСЯ, то это означает, что в отличие от регулярных языков множество КСЯ не замкнуто относительно дополнения.}.

\section{Функция $\first$}
При построении (детерминированных) анализатаров по грамматике, нам потребуется определять множество первых $k$ символов слов, выводимых из цепочки $\alpha \in (N\cup T)^*$. Для этого мы будем использовать функцию $\first_k$, которая определена через функцию $\first_1$ или просто $\first$. Таким образом умение вычислять функцию $\first$ является ключевым при построении анализаторов.

Формально, 
$$
	\first_k(\alpha) = \{ w[1,k]\, |\, \alpha \yield w, |w| > k  \} \cup \{ w\,|\, \alpha \yield w, |w| < k\}
$$

Если $\alpha \yield \eps$, то пустое слово лежит в $\first_k (\alpha)$.

Приведём процедуру вычисления функции $\first(\alpha)$. 

\emph{\textbf{Идея алгоритма:}} Если $\alpha = X_1X_2\ldots X_n$ начинается с терминала $\sigma$, то первым символом может быть только этот терминал, таким образом, мы сразу получаем ответ $\sigma$. Если же $\alpha$ начинается с нетерминала, то $\first(\alpha) = \first(X_1)$, если из нетерминала $X_1$ не выводится пустое слово, и $\first(\alpha) = \first(X_1)\cup \first(X_2X_3\ldots X_n)$, если $X_1 \yield \eps$. 


Таким образом, мы описали вычисление функции $\first$ на множестве терминалов и цепочек, начинающихся с терминалов, осталось описать вычисление функции на множестве нетерминалов, как видно вычисление функции $\first$ на множестве сентенциальных форм сводится к вычислению функции на отдельных нетерминалах.


Пусть мы вычисляем функцию $\first(X)$ для нетерминала $X$. Рассмотрим все правила вида $X \to \beta$. Очевидно, что $\first(\beta)$ является подмножеством $\first(X)$, но просто добавляя множество $\first(\beta)$ к $\first(X)$ мы получим порочный круг, в случае правил вида $ X \to Xa$. Как нам избежать порочного круга при вычислении множества $\first(X)$? 


Определим множества $F_i(Y),\ Y \in N$. При $i = 0$ для любого нетерминала $Y$, множество $F_i(Y) = \es$, или $ \{\eps\}$, если есть правило $Y\to \eps$. На $i-$ом шаге алгоритма будем вычислять множества $F_i(X)$ следующим образом. В начале шага $F_i(X)$ включает себя множество $F_{i-1}(X)$ Если есть правило $X \to \beta = Y_1Y_2\ldots Y_n$ и $Y_1$ -- терминал или $\beta$ -- пустое слово, то добавим к множеству $F_i(X)$ элемент $Y_1$ (быть может пустое слово). Если же $Y_1$ -- нетерминал, и при этом пустое слово не лежит в $F_{i-1}(Y_1)$, то добавим к множеству $F_i(X)$ множество $F_{i-1}(Y_1)$ и вычислим множество $F_{i}(Y_1)$. Если же $\eps \in F_{i-1}(Y_1)$, то добавим к $F_i(X)$ множество $F_i(Y_1)\setminus\{\eps\}$ и повторим описанную операцию для $\beta = Y_2\ldots Y_n$.

Алгоритм останавливается, как только для каждого нетерминала $Y$, множества $F_i$ и $F_{i-1}$ совпадают.

\begin{flushleft}
	
\emph{\textbf{Алгоритм}:} 
\end{flushleft}
\setlist[1]{itemsep=-3pt}
\begin{itemize}
	\item[ ] \emph{Шаг 0.}  Для каждого терминала $\sigma$ положим $F_i(\sigma) = \sigma$ для любого $i$. Для каждого нетерминала $Y$, если есть правило $Y\to \eps$,  положим $F_0(Y) = \{\eps\}$, иначе положим $F_0(Y) = \es$.
	\item[ ] \emph{Шаг i.} Добавить к множеству $F_i(X)$ множество $F_{i-1}(X)$. Для каждого правила $X \to \beta = Y_1\ldots Y_n$ выполнить:
	\item[ ] \quad $j = 1$
	\item[ ] \quad Пока $\eps \in F_{i-1}(Y_j)$ и $j\leq n$
	\item[ ] \qquad добавить $F_{i-1}(Y_j)\setminus\{\eps\}$ к $F_i(X)$, 
	\item[ ] \qquad увеличить $j$.
	\item[ ] \quad Если $\eps \in F_{i-1}(Y_1)\cap F_{i-1}(Y_2)\cap\ldots \cap F_{i-1}(Y_n)$, добавить $\eps$ к $F_i(X)$,
	\item[ ] \emph{Остановка.} $F_i(Y) = F_{i-1}(Y)$ для любого $Y$ из $N$. Положить $\first(X) = F_i(X)$.
\end{itemize}





\upr Доказать корректность данного алгоритма.

\section{Функция $\follow$}

Помимо префикса порождаемого цепочкой $\beta$ нас будет интересовать также и множество слов, которые могут следовать после слова, выведенного из цепочки $\beta$. Запишем сначала формальное определение функции $\follow_k$.

$$
	\follow_k(\beta) = \{ w\,|\, S \yield \alpha\beta\gamma, w \in \first_k(\gamma) \}.
$$

Неформально, в множестве $\follow_k(\beta)$ содержатся те слова, которые могут следовать за словом, выведенным из $\beta$, в цепочке $\alpha\beta\gamma$, выводимой из аксиомы. Длина этих слов ограничена $k$, что означает, что если $\gamma \yield w$ и длина слова $w$ меньше $k$, то $w$ лежит в множестве $\follow_k(\beta)$, а если же  длина слова $w$ больше $k$, то в множестве $\follow_k(\beta)$ лежит префикс $w$ длины $k$. 

Аналогично функции $\first$, мы будем обозначать $\follow_1$ как $\follow$.

Мы будем часто пользоваться функцией $\follow_k$ в теоретических целях и для обозначения объектов, однако на практике мы будем вычислять функцию $\follow$ только на множестве нетерминалов.



Приведём алгоритм для вычисления функции $\follow$.

\textbf{\emph{Идея алгоритма:}} Если в грамматике есть правило $A \to \alpha X\beta$, то за словом, выведенным из нетерминала $X$ следует слово выведенное из $\beta$, таким образом множество $\follow(X) $ включает в себя множество $ \first(\beta)$. Если, при этом из цепочки $\beta$ выводимо пустое слово, то за словом, выводимым из нетерминала $X$ следует слово из множества $\follow(A)$, поскольку из вывода

$$ S \yields \gamma A w \yield \gamma \alpha X \beta w \yield  \gamma \underbrace{\alpha X}_{A} w  $$

следует, что если элемент $\first(w) $ лежит в множестве $ \follow(A)$, то элемент $\first(w) $ лежит так же в множестве $ \follow(X)$. Таким образом, по определению функции $\follow$, если в грамматике есть правило $\A \to \alpha X \beta$ и при этом из цепочки $\beta $ выводимо пустое слово, то множество $\follow(X) $ включает в себя множество $ \follow (A)$. В частности, возможно что $\beta = \eps$, поэтому при наличии в грамматике правила $A \to \alpha X$, справедливо $\follow(X) \supseteq \follow (A)$.

В итоге, мета-алгоритм сводится к следующим шагам:

\begin{itemize}
	\item Вычислить множества $\first$ для грамматики $G$;
	\item Для правил $A \to \alpha X \beta$ добавить $\first(\beta)\setminus\{\eps\}$ к $\follow(X)$;
	\item Для правил $A \to \alpha X \beta$, таких что, $\eps \in \first(\beta)$ добавить $\follow(A)$ к $\follow(X)$.
\end{itemize}

\upr Доказать корректность данного мета-алгоритма. То есть, что все элементы множеств $\follow$ будут найдены и ничего лишнего найдено не будет.

\begin{Remark}
	По хорошему, возникает проблема с тем, лежит ли пустое слово в $\follow(X)$. Эта проблема решается следующим образом: ко всем словам, порождаемым $G$ добавляется маркер конца слова, и если этот маркер оказывается в $\follow(X)$, то пустое слово принадлежит $\follow(X)$. Для этого по грамматике $G$ строится пополненная грамматика $G^\prime$, которая содержит правило $S^\prime \to S\$$, где $\$$ -- маркер конца слова. Все остальные правила грамматики $G^\prime$ взяты из грамматики $G$. На практике, функция $\follow$ используется в анализаторах, на вход которым и так подаётся пополненная грамматика, поэтому решать проблему наличия пустого слова в множестве $\follow(X)$ не надо. 	
\end{Remark}

Теперь опишем сам алгоритм. Идея алгоритма схожа с индуктивным вычислением множеств $\first$.

\newpage

\emph{\textbf{Алгоритм}:} 

\setlist[1]{itemsep=-3pt}
\begin{itemize}
	\item[ ] \emph{Шаг 0.}  Для каждого нетерминала $Y$ положим $F_0(Y) = \es$. Вычислим значение функции $\first$ для грамматики $G$. 
	\item[ ] \emph{Шаг i.}  Положить множество $F_i(X)$ равным множеству $F_{i-1}(X)$. Для каждого правила $A \to \alpha X \beta$ добавить $\first(\beta)\setminus\{\eps\}$ к $F_i(X)$; Если $\eps \in \first(\beta)$ добавить $F_{i-1}(A)$ к $F_{i}(X)$.
	\item[ ] \emph{Остановка.} Как только $F_i(Y) = F_{i-1}(Y)$ для любого $Y$ из $N$. Положить $\follow(X) = F_i(X)$.
\end{itemize}



\prp Грамматика $\mathsf{Expr} = \langle \{E,T,F,E^\prime,F^\prime\}, \{\id, +, \times, (, ) \}, P, E \rangle$ имеет множество правил $P:$  
%\vspace{-1ex}
$$ E \to TE^\prime;\quad E^\prime \to +TE^\prime \mid \eps;\quad T \to FT^\prime;$$ 
%\vspace{-3ex}
$$ T^\prime \to \times FT^\prime \mid \eps;\qquad F \to (E) \mid \id.  $$
Вычислите функции $\first$ и $\follow$ для всех нетерминалов грамматики $\mathsf{Expr}$.



\end{document}