\documentclass{article}
\usepackage{epsfig}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% General formatting parameters %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\parskip=.080in
\setlength{\evensidemargin}{0.in}
\setlength{\oddsidemargin}{0.in}
\setlength{\textwidth}{6.612in}
\setlength{\topmargin}{0.in}
\setlength{\textheight}{8.8in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\topsep}{0in}
\setlength{\itemsep}{0in}
\renewcommand{\baselinestretch}{1.2}
\newcommand{\smallsection}[1]{{\smallskip\bf #1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% Non-mathematical macros %%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\larry}{{$\calL^3$}}
\newcommand{\marek}{\mbox{${\cal M}\!{\cal C}\!h$}}
\newcommand{\ie}{{\em i.e.}}
\newcommand{\etal}{\mbox{\em et al.\/} }
\newcommand{\tH}{{\rm th}}
\newcommand{\eg}{{\em e.g.}}
\newcommand{\etc}{{\em etc.}}
\newcommand{\case}[1]{{\smallskip\noindent{\bf Case #1:\/}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% Caligraphic letters %%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\calA}{{\cal A}}
\newcommand{\calB}{{\cal B}}
\newcommand{\calC}{{\cal C}}
\newcommand{\calD}{{\cal D}}
\newcommand{\calE}{{\cal E}}
\newcommand{\calF}{{\cal F}}
\newcommand{\calG}{{\cal G}}
\newcommand{\calH}{{\cal H}}
\newcommand{\calI}{{\cal I}}
\newcommand{\calJ}{{\cal J}}
\newcommand{\calK}{{\cal K}}
\newcommand{\calL}{{\cal L}}
\newcommand{\calM}{{\cal M}}
\newcommand{\calN}{{\cal N}}
\newcommand{\calO}{{\cal O}}
\newcommand{\calP}{{\cal P}}
\newcommand{\calQ}{{\cal Q}}
\newcommand{\calR}{{\cal R}}
\newcommand{\calS}{{\cal S}}
\newcommand{\calT}{{\cal T}}
\newcommand{\calU}{{\cal U}}
\newcommand{\calV}{{\cal V}}
\newcommand{\calW}{{\cal W}}
\newcommand{\calX}{{\cal X}}
\newcommand{\calY}{{\cal Y}}
\newcommand{\calZ}{{\cal Z}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% Delimiters %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\angled}[1]{{\left\langle #1\right\rangle}}
\newcommand{\barred}[1]{{\left|#1\right|}}
\newcommand{\braced}[1]{{\left\{#1\right\}}}
\newcommand{\brackd}[1]{{\left[#1\right]}}
\newcommand{\parend}[1]{{\left(#1\right)}}
\newcommand{\spaced}[1]{{\ #1\ }}
\newcommand{\dummydot}{{\/\cdot\/}}
\newcommand{\mytimes}{{\!\times\!}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% something-ed letters %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\barx}{{\bar{x}}}
\newcommand{\bary}{{\bar{y}}}
\newcommand{\cstar}{{c^\ast}}
\newcommand{\phistar}{{\phi^\ast}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Strategy and problems names %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\adv}{{\it adv}}
\newcommand{\MSS}{{\rm MSS}}
\newcommand{\PRP}[1]{{#1\!-\!\mbox{\rm PRP}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Sets and constants %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Domain}{\mbox{\sf Dom\,}}
\newcommand{\reals}{{\rm I\!R}}
\newcommand{\naturals}{ \mbox{\rm I\hspace{-3pt}N} }
\newcommand{\Det}{{\mbox{\sf Det}}}
\newcommand{\distrib}{{\rm I\!D}}
\newcommand{\half}{{\scriptstyle{1\over 2}}}
\newcommand{\Rand}{{\mbox{\sf Rand}}}
\newcommand{\nats}{{\rm I\!N}}
\newcommand{\posreals}{{\rm I\!R^+}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Functions and Operators %%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\becomes}{\mbox{$:=$}}
\newcommand{\bdistrib}{{\rm I\!B}}
\newcommand{\cost}{\mbox{\it cost\/}}
\newcommand{\To}{{\Rightarrow}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% Environments %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}
\newtheorem{observation}{Observation}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{fact}{Fact}
\newenvironment{proof}{{\it Proof:\/}}{$\Box$\vskip 0.1in}
\newenvironment{example}[1]{{%
        \vskip 0.1in \noindent
        {\bf Example~{#1}:\ }%
    }}%
    {$\Diamond$\vskip 0.1in}
\newenvironment{claim}[1]%
  {{\vskip 0.1in\noindent \bf Claim~#1:\ }}%
  {\vskip 0.1in}

\newcommand{\sfparagraph}[1]%
   {\vskip 0.1in\noindent{\sf #1}}

\newenvironment{mydescription}%
        {%
           \begin{list}{}%
             {%
                \setlength{\topsep}{0pt}%
                \setlength{\parsep}{0pt}%
                \setlength{\partopsep}{0pt}%
                \setlength{\itemsep}{0pt}%
                \setlength{\itemindent}{0pt}%
                \setlength{\labelwidth}{0.2in}%
                \setlength{\leftmargin}{0.3in}%
                \setlength{\rightmargin}{0.3in}%
            }%
        }%
        {\end{list}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\margincomment}[1]%
    {{%
      \marginpar{{\tiny\begin{minipage}{0.5in}
                       \begin{flushleft}
                          {#1}
                       \end{flushleft}
                       \end{minipage}
                }}
    }}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% maly %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\maly}[1]{{\scriptscriptstyle#1}}
\newcommand{\malyz}{{\maly{0}}}
\newcommand{\malyone}{{\maly{1}}}
\newcommand{\malytwo}{{\maly{2}}}
\newcommand{\smallX}{{\scriptscriptstyle X}}
\newcommand{\smallY}{{\scriptscriptstyle Y}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%% fill-in blanks %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\u{\_\_}
\def\uu{\u\u}
\def\uuu{\uu\uu}
\def\uuuu{\uuu\uuu}
\def\uuuuu{\uuuu\uuuu}
\def\uuuuuu{\uuuuu\uuuuu}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\spcd}[1]{{\ #1\ }}
\newcommand{\romn}[1]{{\mbox{\rm #1}}}
\newcommand{\spacedromn}[1]{\spcd{\romn{#1}}}

\newcommand{\leftbracedtwo}[2]{\left\{\begin{array}{l}
                                        #1 \\ #2
                                    \end{array}\right.
                           }

\renewcommand{\labelenumi}{\arabic{enumi}. }
\renewcommand{\labelenumii}{(\roman{enumii})}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
%\thispagestyle{empty}
%\setcounter{page}{0}
\subsection*{Computer Science 456/656.  Context-Sensitive Grammars}

A context sensitive grammar, like all the grammars we have introduced
in this course consists of the following parts:

\begin{enumerate}
\item
$\Sigma$, the alphabet of {\em terminals}.
\item
$V$, the alphabet of {\em variables}.
\item
$S\in V$, the {\em start symbol}.
\item
$\calR$, a finite set of rules, or productions.
\end{enumerate}

Terminals and variables together are called {\em grammar symbols}.
What makes the grammar context-sensitive is the set of restictions on
the productions.  You might find different definitions in various places.

Each production has a left-hand side and a right-hand side.
Each production is of the form:
$$\alpha A\beta \to \alpha\gamma\beta$$
where $A$ is a variable, $\alpha$, $\beta$, and $\gamma$ are
strings of grammar symbols, and $\gamma\ne\varepsilon$, except as stated
below.

A grammar with only productions of the form described above
cannot generate the empty string, and thus not every context-free language
would be a context-sensitive language.  In order to prevent
this, we allow one more production, namely $S\to\varepsilon$,
but we make the additional restriction that $S$ cannot appear on the right hand
side of any production.  With this slight ``tweak" to the definition,
every context-free language is context-sensitive.

\subsection*{Example}
The language $\braced{a^nb^nc^n}$ is generated by
the following context-free grammar (modified from a Wikipedia page).

\noindent
1. $S\to\varepsilon$\\
2. $S\to T$\\
3. $S\to aTBC$\\
4. $T\to aTBC$\\
5. $S\to aBC$\\
6. $T\to aBC$\\
7. $CB\to HB$\\
8. $HB\to HC$\\
9. $HC\to BC$\\
10. $aB\to ab$\\
11. $bB\to bb$\\
12. $bC\to bc$\\
13. $cC\to cc$



\end{document}
