\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage[labelformat=empty]{caption}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage{placeins}

\title{Формальные языки - практикум 2}
\author{Вихрев Евгений, группа 797}
\date{Декабрь 2018}

\begin{document}

\maketitle

{\large Правила данной граматики $ \Gamma $: }
\begin{enumerate}[start=0]
\item $ S' \rightarrow S $
\item $ S \rightarrow SC $
\item $ S \rightarrow C $
\item $ C \rightarrow cD $
\item $ D \rightarrow aDb $
\item $ D \rightarrow \varepsilon $
\end{enumerate}

{\large Построим по данной граматике ($ \Gamma $) LR-Таблицу: }

\begin{enumerate}[start=0]
\item $ Initial \  state $ \\
    $S' \rightarrow \cdot S , \ \$ $ \\
    $S  \rightarrow \cdot SC , \ \$ | c $ \\
    $S  \rightarrow \cdot C , \ \$ | c $ \\
    $C  \rightarrow \cdot cD , \ \$ | c $ \\
\item $ Goto(0, S) $ \\
    $S' \rightarrow S \cdot , \ \$ $ $\ - \ accept $ \\
    $S  \rightarrow S \cdot C , \ \$ | c $ \\
    $C  \rightarrow \cdot cD , \ \$ | c $ \\
\item $ Goto(0, C) $ \\
    $S  \rightarrow C \cdot , \ \$ | c $ $\ - \ reduce(2) $ \\
\item $ Goto(0, c), \ Goto(1, c) $ \\
    $C  \rightarrow c \cdot D , \ \$ | c $ \\
    $D  \rightarrow \cdot aDb , \ \$ | c $ \\
    $D  \rightarrow \cdot , \ \$ | c $ $\ - \ reduce(5) $ \\
\item $ Goto(1, C) $ \\
    $S  \rightarrow SC \cdot , \ \$ | c $ $\ - \ reduce(1) $ \\
\item $ Goto(3, D) $ \\
    $C  \rightarrow cD \cdot , \ \$ | c $ $\ - \ reduce(3) $ \\
\item $ Goto(3, a) $ \\
    $D  \rightarrow a \cdot Db , \ \$ | c $ \\
    $D  \rightarrow \cdot aDb , \ b $ \\
    $D  \rightarrow \cdot , \ b $ $\ - \ reduce(5) $ \\
\item $ Goto(6, D) $ \\
    $D  \rightarrow aD \cdot b , \ \$ | c $ \\
\item $ Goto(7, b) $ \\
    $D  \rightarrow aDb \cdot , \ \$ | c $ $\ - \ reduce(4) $ \\
\item $ Goto(6, a), \ Goto(9, a) $ \\
    $D  \rightarrow a \cdot Db , \ b $ \\
    $D  \rightarrow \cdot aDb , \ b $ \\
    $D  \rightarrow \cdot , \ b $ $\ - \ reduce(5) $ \\
\item $ Goto(9, D) $ \\
    $D  \rightarrow aD \cdot b , \ b $ \\
\item $ Goto(10, b) $ \\
    $D  \rightarrow aDb \cdot , \ b $ $\ - \ reduce(4) $ \\
\end{enumerate}

\begin{table}[h!]
\caption{{\large LR-Таблица}}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
  & S & C & D & a & b & c & \$ \\
\hline
0 & S1 & S2 & & & & S3 & \\
\hline
1 & & S4 & & & & S3 & acc \\
\hline
2 & & & & & & r2 & r2 \\
\hline
3 & & & S5 & S6 & & r5 & r5 \\
\hline
4 & & & & & & r1 & r1 \\
\hline
5 & & & & & & r3 & r3 \\
\hline
6 & & & S7 & S9 & r5 & & \\
\hline
7 & & & & & S8 & & \\
\hline
8 & & & & & & r4 & r4 \\
\hline
9 & & & S10 & S9 & r5 & & \\
\hline
10 & & & & & S11 & & \\
\hline
11 & & & & & r4 & & \\
\hline
\end{tabular}
\end{center}
\end{table}

\FloatBarrier
{\large Для примера разберём слово $ caaabbbc \in \Gamma $: }
\begin{enumerate}
    \item $ caaabbbc\$ \ : \ 0 $ \ - \ initial
    \item $ aaabbbc\$ \ : \ 0c3 $ \ - \ shift 3 by 'c'
    \item $ aabbbc\$ \ : \ 0c3a6 $ \ - \ shift 6 by 'a'
    \item $ abbbc\$ \ : \ 0c3a6a9 $ \ - \ shift 9 by 'a'
    \item $ bbbc\$ \ : \ 0c3a6a9a9 $ \ - \ shift 9 by 'a'
    \item $ bbbc\$ \ : \ 0c3a6a9a9D10 $ \ - \ reduce 5 and shift 10 by 'D'
    \item $ bbc\$ \ : \ 0c3a6a9a9D10b11 $ \ - \ shift 11 by 'b'
    \item $ bbc\$ \ : \ 0c3a6a9D10 $ \ - \ reduce 4 and shift 10 by 'D'
    \item $ bc\$ \ : \ 0c3a6a9D10b11 $ \ - \ shift 11 by 'b'
    \item $ bc\$ \ : \ 0c3a6D7 $ \ - \ reduce 4 and shift 7 by 'D'
    \item $ c\$ \ : \ 0c3a6D7b8 $ \ - \ shift 8 by 'b'
    \item $ c\$ \ : \ 0c3D5 $ \ - \ reduce 4 and shift 7 by 'D'
    \item $ c\$ \ : \ 0C2 $ \ - \ reduce 3 and shift 2 by 'C'
    \item $ c\$ \ : \ 0S1 $ \ - \ reduce 2 and shift 1 by 'S'
    \item $ \$ \ : \ 0S1c3 $ \ - \ shift 3 by 'c'
    \item $ \$ \ : \ 0S1c3D5 $ \ - \ reduce 5 and shift 5 by 'D'
    \item $ \$ \ : \ 0S1C4 $ \ - \ reduce 3 and shift 7 by 'D'
    \item $ \$ \ : \ 0S1 $ \ - \ reduce 1 and shift 1 by 'S'. Accept!
\end{enumerate}
{\large Автомат, как и ожидалось, перешёл по слову $ caaabbbc $ в accept. }
\\
\FloatBarrier
\\
{\large Теперь разберём слово $ caacabbb \notin \Gamma $: }
\begin{enumerate}
    \item $ caacabbb\$ \ : \ 0 $ \ - \ initial
    \item $ aacabbb\$ \ : \ 0c3 $ \ - \ shift 3 by 'c'
    \item $ acabbb\$ \ : \ 0c3a6 $ \ - \ shift 6 by 'a'
    \item $ cabbb\$ \ : \ 0c3a6a9 $ \ - \ shift 9 by 'a'
    \item $ abbb\$ \ : \ 0c3a6a9 $ \ - \ Error!
\end{enumerate}
{\large Видно что $ caacabbb \notin \Gamma $ состояния accept не достигается. }

\end{document}