\documentclass[xcolor=svgnames]{beamer} %handout

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english, russian]{babel}

\usepackage{amsmath,amsfonts,graphicx}
\usepackage{beamerleanprogress}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows,chains,fit,shapes,automata,positioning,trees}
\usepackage{mathrsfs}
%\usepackage{graphics}
\usepackage{multicol}  
\usepackage{verbatim}       

\deftranslation[to=russian]{Example}{Пример}
\deftranslation[to=russian]{Definition}{Определение}
\deftranslation[to=russian]{Theorem}{Теорема}
\deftranslation[to=russian]{Lemma}{Лемма}

\title{LR-анализ}

%\subtitle{немного о теории, и о том как она\\ становится практикой}

\author[Александр Рубцов]{Александр Рубцов}

%\date{27 июня 2016}

\institute{ \href{mailto:alex@rubtsov.su}{\textcolor{Maroon!70}{alex@rubtsov.su}} }
%\email{alex@rubtsov.su}
%  {Лаборатория Теоретической Информатики НИУ ВШЭ \\ \vspace{1em} Московский Физико-Технический Институт}

%%%%%%%%%%%%%%%%%%%%  GENERAL MACROSES %%%%%%%%%%%%%%%%%%%%  

	%%%%%%%% 	Letters		%%%%%%%%%
	%Обозначения ``ажуром''
	\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\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\then\Rightarrow
	\let\rendmarker\vartriangleleft
	\let\vk\varkappa
	\let\ph\varphi
	\let\Ld\Lambda
	\let\es\varnothing

	\def\R{{\cal R}}
	\def\A{{\cal A}}
	\def\B{{\cal B}}
	\def\D{{\cal D}}
	\def\F{{\cal F}}
	\def\T{{\cal T}}

	\def\CA{{\mathscr A}}
	\def\CL{{\mathscr L}}
	\def\CM{{\mathscr M}}


	\let\w\omega

	\def\C{{\mathbf{C}}}

	%%%%%%%% 	Complexity classes	%%%%%%%%%
	\def\L{{\mathbf{L}}}
	\def\NL{{\mathbf{NL}}}
	\def\PP{{\mathbf{P}}}
	\def\NP{{\mathbf{NP}}}
	\def\REG{{\mathsf REG}}
	\def\Rat{{\mathsf{Rat}}}
	\def\CFL{{\mathsf{CFL}}}
	\def\AFL{{\mathsf{AFL}}}
	\def\DCFL{{\mathsf{DCFL}}}
	\def\DSA{{\mathsf{DSA}}}
	\def\SA{{\mathsf{SA}}}

	\def\PSPACE{{\mathbf{PSPACE}}}
	\def\DTIME{{\ensuremath{\mathbf{DTIME}}}}
	\def\NTIME{{\ensuremath{\mathbf{NTIME}}}}
	\def\NSPACE{{\ensuremath{\mathbf{NSPACE}}}}
	\def\DSPACE{{\ensuremath{\mathbf{DSPACE}}}  }


	\def\DFA{{\rm DFA}}                      
	\def\NFA{{\rm NFA}}                       



	%%%%%%%% 	Rational Cones	  %%%%%%%% 	

	\def\Lin{\ensuremath{\mathbf{Lin}}}
	\def\Qrt{\ensuremath{\mathbf{Qrt}}}


	%%%%%%%% 	Reductions		%%%%%%%%%
	\let\leq\leqslant
	\let\geq\geqslant
	\def\nlog{\rm nlog}

	\def\leGen#1#2{\mathop{\leq^{\mathrm{#2}}_{\mathrm{#1}}}}
	\def\lem{\leGen{m}{}}
	\def\lelog{\leGen{log}{}}
	\def\leP{\leGen{P}{}}
	\def\lea{\leGen{a}{}}
	\def\len{\leGen{na}{}}
	\def\lerat{\mathop{\leq_{\mathrm{rat}}}}
	\def\ledrat{\mathop{\leq_{\mathrm{drat}}}}



	\def\lem{\mathop{\leq_{\mathrm{m}}}}
	\def\leT{\mathop{\leq_{\mathrm{T}}}}

	%%%%%%%%%%%%%%%%%% Yields and Ders %%%%%%%%%%%%%%%%%% 

	%\usepackage{mathtools} %  для xhookrightarrow
	\makeatletter
%	\newcommand{\xRightarrow}[2][]{\ext@arrow 0359\Rightarrowfill@{#1}{#2}}
	\makeatother

	\def\yield{\xRightarrow{\phantom{\scriptstyle *\; }}}
	\def\yields{\xRightarrow{{\scriptstyle *\; }}}
	%\def\yieldsR{\xRightarrow[{\scriptscriptstyle R}]{{\scriptstyle *}}}

	\def\ders{ \vdash^{\!\!\! {}^{ *}}}
	\def\der{ \vdash }
	\let\derives\ders
	\let\derive\der

	\def\yieldL{\yield_{ \!\!{}_{\scriptscriptstyle L}}}
	\def\yieldsL{\yields_{ \!\!{}_{\scriptscriptstyle L}}}
	\def\yieldR{\yield_{ \!\!{}_{\scriptscriptstyle R}}}
	\def\yieldsR{\yields_{ \!\!{}_{\scriptscriptstyle R}}}


	%%%%%%%%%%%%%%%%%% EoF Yields and Ders %%%%%%%%%%%%%%%%%%
	%%%%%%%% 	Other		%%%%%%%%%
	\def\wbeg{\triangleleft}
	\def\wend{\triangleright}
	\def\bydef{\mathrel{\stackrel{\scriptscriptstyle\text{def}}{=}}}

	\def\sia{\sim_\mathrm{a}}
	\def\sian{\sim_\mathrm{na}}
	\def\tP{\tilde P}
	\let\la\langle
	\let\ra\rangle
	\def\ba{\bar a}
	\def\bb{\bar b}
	\def\bc{\bar c}
	\def\bx{\bar x}
	\def\bz{\bar 0}
	\def\bu{\bar 1}
	\def\hD{h^{\mathrm{DFA}}}
	\def\hN{h^{\mathrm{NFA}}}
	
	
	\def\FST{{\mathsf{FST}}}
	\def\DFST{{\mathsf{DFST}}}
	
	\def\Id{\mathrm{Id}}
	
	         
	\def\DPDA{{\mathsf{DPDA}}}
	\def\first{\mathrm{ FIRST} }
	\def\follow{\mathrm{ FOLLOW} }
%	\def\I{\mathrm{I}}
	\def\LL{{\mathrm{LL}}}
	\def\LR{{\mathrm{LR}}}
	\def\KC{{ K\!C}}
	\def\shift{\textcolor{structure.fg!75}{S: }}
	\def\Shift{\textcolor{structure.fg!75}{S }}
	\def\reduce{\textcolor{Maroon!75}{R: }}
	\def\accept{\textcolor{LimeGreen!75}{ACC }}

	\def\PAL{{\mathsf{PAL}}}
	
	

\tikzset{hide on/.code={\only<#1>{\color{white}}}}

%\def\hlabel#1{#1}	
\def\hlabel#1{}

\begin{document}
%	\definecolor{qqqqff}{rgb}{0.,0.,1.}
%	\definecolor{ffqqtt}{rgb}{1.,0.,0.2}
%	\definecolor{wwzzqq}{rgb}{0.4,0.6,0.}

\maketitle



\section{LR-грамматики}

\begin{frame}{LR-анализ}
	\begin{center}
		\begin{tikzpicture}[level 1/.style={sibling distance=7em},level 2/.style={sibling distance=3em}, lrs/.style={ color=gray}] %, level distance=6em
		   \node (root) {$S$}
		    child [hide on = 16] {node  (S1)   { $S_1$} %at (-1,0) %{\onslide<3->{\textcolor{gray}{\huge .}}}
				child [hide on = 6-16] {node (e1) {$\eps$}}
			}
			child [hide on = 16] {node (a1) {$a$}} %at (-1.3,0)
			child [hide on = 16] {node (S2) {$S_2$}
				child [hide on = 14-16]  {node (S3) {$S_3$}
					child [hide on = 10-16] {node  (e2) {$\eps$}}
				}
				child [hide on = 14-16]  {node (a2) {$a$}} 
				child [hide on = 14-16] {node (S4) {$S_4$}
					child [hide on = 12-16] {node (e3) {$\eps$}}
				} 
				child [hide on = 14-16] {node  (b1) {$b$}}		    
			} 
			child [hide on = 16]  {node (b2) {$b$}};
			
			\node<2-15,18->  [lrs, left =  2 mm of root]  { [ {\onslide<2-15>{\huge .}} };
			\node<2-15,18->  [lrs, right = 2 mm of root]  {  {\huge {\only<16>{.}},} \$ ] };
			
			
			
			\node<3-15,18->  [lrs, left = -2 mm of S1]  { [  {\onslide<3-5>{\huge .}} };
				\node<6>[lrs, below left = -3.2 mm and -2 mm of a1] {\huge .};
				\node<7-13>[lrs, below left = -3.2 mm and -2 mm  of S2] {\huge .};
				\node<14>[lrs, below left = -3.2 mm and -2 mm  of b2] {\huge .};
			\node<3-15,18->  [lrs, right = -2mm of b2]  {  {\huge {\only<15>{.}},} \$ ] };
			
			
			\node<8-13,18->   [lrs, left = -2 mm of S3]  { [ {\onslide<8-9>{\huge .}} };
				\node<10>[lrs, below left = -3.2 mm and -2 mm of a2] {\huge .};
				\node<11>[lrs, below left = -3.2 mm and -2 mm of S4] {\huge .};
				\node<12>[lrs, below left = -3.2 mm and -2 mm of b1] {\huge .};				
			\node<8-13,18->  [lrs, below right  = -5.6 mm and -2 mm of b1, ]  {   {\huge {\only<13>{.}},} $b$ ] };			
			
			
			\node<4-5,18->  [lrs, left = -2 mm of e1]  { [ {\huge .} };
			\node<4-5,18->  [lrs, right = -2mm of e1]  {  {\huge ,} $a$ ] };			
			
			
			\node<9,18->  [lrs, left = -2 mm of e2]  { [ {\huge .} };
			\node<9,18->  [lrs, right = -2mm of e2]  {  {\huge ,} $a$ ] };
			
			\node<11,18->  [lrs, left = -2 mm of e3]  { [ {\huge .} };
			\node<11,18->  [lrs, right = -2mm of e3]  {  {\huge ,} $b$ ] };
			
			
			
			
			
		\end{tikzpicture} 
	

	
\vspace{3em}
	\only<1>{ {\Large	aabb\$}}
	\only<2-4>{{\Large	.a a b b \$}}
	\only<5-6>{{\Large	.\emph{a} a b b \$}}
	\only<7-8, 10>{{\Large	a .a b b \$}}		
	\only<9>{{\Large	a .\emph{a} b b \$}}		
	\only<11>{{\Large	a  a .\emph{b} b \$}}			
	\only<12>{{\Large	a  a .b b \$}}		
	\only<13>{{\Large	a  a b .\emph{b} \$}}		
	\only<14>{{\Large	a  a b .b \$}}		
	\only<15>{{\Large	a  a b b .\emph{\$}}}
	\only<16->{{\Large	a  a b b \$}}			
	\end{center}

\onslide<6-17>{ $S_1 \to \eps$ }
\onslide<10-17>{ \quad $S_3 \to \eps$ }
\onslide<12-17>{ \quad $S_4 \to \eps$ }
\onslide<14-17>{ \quad $S_2 \to S_3aS_4b$ }
\onslide<16-17>{ \quad $S \to S_1aS_2b$ }
\vspace{-1.5em}
\onslide<18>{ $$ \textcolor{orange!50}{[\quad S}\,\textcolor{blue!50}{[\quad S_1}\textcolor{gray!50}{[\eps,a]}\quad \textcolor{blue!50}{(}a\textcolor{blue!50}{)}\quad \textcolor{blue!50}{S_2}\,\textcolor{Maroon!50}{[\;\; S_3}\textcolor{gray!50}{[\eps,a]}\;\; \textcolor{Maroon!50}{(}a\textcolor{Maroon!50}{)}  \;\; \textcolor{Maroon!50}{S_4}\textcolor{gray!50}{[\eps,b]}\;\; \textcolor{Maroon!50}{(}b\textcolor{Maroon!50}{)}\;\; \textcolor{Maroon!50}{,b]}\quad \textcolor{blue!50}{(}b\textcolor{blue!50}{)} \textcolor{blue!50}{,\$]} \quad\textcolor{orange!50}{,\$]}  $$}
\end{frame}

\section{Автомат Кнута}

\begin{frame}{Автомат Кнута}
		
		\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto,initial text= , every state/.style={rectangle}]
		  %\draw[help lines] (0,0) grid (3,2);
		  \node[state,initial]  (q_0)                      {$[S^\prime \to \cdot S,\$]$};
		  \node[state]          (q_1) [ right = of q_0] {$\hlabel{1:}[S \to \cdot SaSb,\$]$};
		  \node[state]					(q_2) [above = 2cm of q_0] {$\hlabel{2:}[S \to \cdot\eps,\$]$};
		  \node[state]          (q_3) [ above = 2cm of q_1] {$\hlabel{3:}[S \to \cdot SaSb,a]$};
		  \node[state]					(q_4) [right =  of q_1] {$\hlabel{4:}[S \to \cdot\eps,a]$};		
		 	\node[state]  				(q_5) [below = 2cm of q_0] {$\hlabel{5:}[S^\prime \to S\cdot,\$]$};
			\node[state]          (q_6) [below = 2cm of q_1] {$\hlabel{6:}[S \to S\cdot aSb,\$]$};
			\node[state]          (q_7) [right = 4cm of q_3] {$\hlabel{7:}[S \to S\cdot aSb,a]$};
			\node[state]          (la) [below right  = 2cm and 1cm of q_5] {$\hlabel{la:}[A \to \alpha\cdot B\beta,u]$};
			\node[state]          (lb) [right = 4cm of la] {$\hlabel{lb:}[B \to \cdot\gamma,v]$};
 			\coordinate[right of=q_7]  (d1);
 			\coordinate[right of=q_6]  (d2);
			\node 				  (lc) [right = 3cm of lb] {$ v \in \first(\beta u) $};
		  \path[->] 
			(q_0)	edge	 	node	{$\eps$}	(q_1)
						edge							 	node	{$\eps$}	(q_2)%[bend left]
						edge			node	{$S$}	(q_5) %[bend right=60]
		 	(q_1)	edge			node	{$\eps$} (q_3)
						edge			node	{$\eps$} (q_4)
						edge			node	{$S$} (q_6)
			(q_3)	edge	[loop above]		node	{$\eps$} ()
						edge			node	{$\eps$} (q_4)
						edge			node	{$S$} (q_7)
			(la)		edge	node {$\eps$} (lb);
			\draw [->,shorten >=0pt] (q_7) to[bend left] node[auto] {$a$} (d1);
			\draw [->,shorten >=0pt] (q_6) to[bend left] node[auto] {$a$} (d2);
		\end{tikzpicture}

\end{frame}


\begin{frame}{Детерминизация}
	
		\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto,initial text= , every state/.style={rectangle}]
		  %\draw[help lines] (0,0) grid (3,2);
		  \node[state,initial,text width=2.5cm]  (q_0)                      {$[S^\prime \to \cdot S,\$]$\\ $[S \to \cdot SaSb,\$]$ $[S \to \cdot\eps,\$]$ $[S \to \cdot SaSb,a]$ $ [S \to .\eps,a]$ };
		  \node[state,text width=2.5cm]  (q_1) [right = 4cm of q_0]              {$[S^\prime \to S\cdot,\$]$\\ $[S \to S\cdot aSb,\$]$ $[S \to S\cdot aSb,a]$  };
		 \coordinate[right of=q_1]  (d1); 
		 \path[->] 
			(q_0)	edge	 	node	{$S$}	(q_1);					
			\draw [->,shorten >=0pt] (q_1) to node[auto] {$a$} (d1);
		\end{tikzpicture}
	
	
\end{frame}


\begin{frame}{Детерминизация}
\hspace*{-3em}	\begin{tikzpicture}[scale=0.5, >=stealth',shorten >=1pt,auto,node distance=4cm, every text node part/.style={align=center}, every state/.style={rectangle}, initial text=]
	  \node[initial,state]  (i0)  { \textcolor{Maroon}{ I$_0$} \\ $S \rightarrow  \cdot \epsilon, \$ $ \\ $S \rightarrow  \cdot \epsilon, a$ \\ $S \rightarrow  \cdot SaSb, \$ $ \\ $S \rightarrow  \cdot SaSb, a$ \\ $S' \rightarrow  \cdot S, \$ $};
	  \node[state]  (i1)  [above  right = -0.5cm and 2cm ]   { \textcolor{Maroon}{I$_{1}$} \\ $S \rightarrow  S \cdot a S b, \$ $ \\ $S \rightarrow  S \cdot a S b, a$ \\ $S' \rightarrow  S \cdot , \$ $}; %at (8,1)
	  \node[state]  (i2)  [below of=i0]  { \textcolor{Maroon}{I$_{2}$} \\ $S \rightarrow  \cdot , a$ \\ $S \rightarrow  \cdot , b$ \\ $S \rightarrow  \cdot SaSb, a$ \\ $S \rightarrow  \cdot SaSb, b$ \\ $S \rightarrow  S a \cdot S b, \$ $ \\ $S \rightarrow  S a \cdot S b, a$};
	  \node[state]  (i3)  [below = 1 cm of i1]  {\textcolor{Maroon}{I$_{3}$} \\ $S \rightarrow  S \cdot a S b, a$ \\ $S \rightarrow  S \cdot a S b, b$ \\ $S \rightarrow  S a S \cdot b, \$ $ \\ $S \rightarrow  S a S \cdot b, a$};
	  \node[state]  (i4)  [below right = -2cm and 0.8cm of i1]  {\textcolor{Maroon}{I$_{4}$} \\ $S \rightarrow  \cdot , a$ \\ $S \rightarrow  \cdot , b$ \\ $S \rightarrow  \cdot SaSb, a$ \\ $S \rightarrow  \cdot SaSb, b$ \\ $S \rightarrow  S a \cdot S b, a$ \\ $S \rightarrow  S a \cdot S b, b$};
	  \node[state]  (i5)  [below = 0.5cm of i3]  {\textcolor{Maroon}{I$_{5}$} \\ $S \rightarrow  SaSb \cdot , \$ $ \\ $S \rightarrow  SaSb \cdot , a$};
	  \node[state]  (i6)  [below of=i4]  {\textcolor{Maroon}{I$_{6}$} \\ $S \rightarrow  S \cdot a S b, a$ \\ $S \rightarrow  S \cdot a S b, b$ \\ $S \rightarrow  S a S \cdot b, a$ \\ $S \rightarrow  S a S \cdot b, b$};
	  \node[state]  (i7)  [above right = 0.5cm and 0.5cm of i6]  {\textcolor{Maroon}{I$_{7}$} \\ $S \rightarrow  SaSb \cdot , a$ \\ $S \rightarrow  SaSb \cdot , b$};
	  \path[->,dashed] (i0) edge [anchor=center] node {S \\ } (i1);
	  \path[->] (i1) edge [bend right=11, above] node {a} (i2);
	  \path[->,dashed] (i2) edge [anchor=center, above] node {S} (i3);
	  \path[->] (i3) edge [right] node {b} (i5);
	  \path[->] (i3) edge [anchor=center, pos=0.3, above] node {a} (i4);
	  \path[->,dashed] (i4) edge [right] node {S} (i6);
	  \path[->] (i6) edge [pos=0.3,above] node {b} (i7);
	  \path[->] (i6) edge [bend left, pos=0.4, left] node {a} (i4);
	\end{tikzpicture}
\end{frame}

\section{LR(1)-анализ}

\begin{frame}{$\LR(1)$-анализатор}
\begin{center}	
	\begin{tabular}{| c | c | c | c || c |}
	  \hline
	  \textbf{State} & \textbf{a} & \textbf{b} & \textbf{\$}  & \textbf{S} \\ \hline
	  I$_{0}$ & \shortstack{\reduce S $\rightarrow$  $\epsilon$} & \shortstack{} & \shortstack{\reduce S $\rightarrow$  $\epsilon$} & \shortstack{I$_{1}$} \\ \hline
	  I$_{1}$ & \shortstack{\shift I$_{2}$} & \shortstack{} & \shortstack{\reduce S' $\rightarrow$  S} & \shortstack{} \\ \hline
	  I$_{2}$ & \shortstack{\reduce S $\rightarrow$  $\epsilon$} & \shortstack{\reduce S $\rightarrow$  $\epsilon$} & \shortstack{} & \shortstack{I$_{3}$} \\ \hline
	  I$_{3}$ & \shortstack{\shift I$_{4}$} & \shortstack{\shift I$_{5}$} & \shortstack{} & \shortstack{} \\ \hline
	  I$_{4}$ & \shortstack{\reduce S $\rightarrow$  $\epsilon$} & \shortstack{\reduce S $\rightarrow$  $\epsilon$} & \shortstack{} & \shortstack{I$_{6}$} \\ \hline
	  I$_{5}$ & \shortstack{\reduce S $\rightarrow$  SaSb} & \shortstack{} & \shortstack{\reduce S $\rightarrow$  SaSb} & \shortstack{} \\ \hline
	  I$_{6}$ & \shortstack{\shift I$_{4}$} & \shortstack{\shift I$_{7}$} & \shortstack{} & \shortstack{} \\ \hline
	  I$_{7}$ & \shortstack{\reduce S $\rightarrow$  SaSb} & \shortstack{\reduce S $\rightarrow$  SaSb} & \shortstack{} & \shortstack{} \\ \hline
	\end{tabular}
	
	\bigskip
	
	\pause

	
	
\only<2-6>{\begin{tabular}{|c|c|c|c|}
		\hline
		Стэк & Вход & Действие & Разбор \\ \hline		
		$I_0$ & $abab\$$ & \reduce S $\rightarrow$  $\epsilon$ &\\ \hline\noalign{\pause}
		$I_0SI_1$ & $abab\$$ &\shift I$_{2}$ & 2\\ \hline\noalign{\pause}
		$I_0SI_1aI_2$ & $bab\$$ &  \reduce S $\rightarrow$  $\epsilon$ & 2\\ \hline\noalign{\pause}
		$I_0SI_1aI_2SI_3$ & $bab\$$ & \shift I$_{5}$  & 22\\ \hline \noalign{\pause}
		$I_0SI_1aI_2SI_3bI_5$ & $ab\$$ & \reduce S $\rightarrow$  SaSb  & 22\\ \hline
	\end{tabular}}
	\only<7>{\begin{tabular}{|c|c|c|c|}
			\hline
			Стэк & Вход & Действие & Разбор \\ \hline		
			$I_0 \textcolor{Maroon}{SI_1aI_2SI_3bI_5}$ & $ab\$$ & \reduce S $\rightarrow$  SaSb  & 22\\ \hline
			$I_0SI_1$ & $ab\$$ &\shift I$_{2}$  & 221\\ \hline
			$I_0SI_1aI_2$ & $b\$$ &\reduce S $\rightarrow$  & 221\\ \hline
			$I_0SI_1aI_2SI_3$ & $b\$$ &\shift I$_{2}$  & 2212\\ \hline
			$I_0SI_1aI_2SI_3bI_5$ & $\$$ &\reduce S $\rightarrow$  SaSb  & 22121\\ \hline
%			$I_0SI_1$ & $\$$ & \accept  & 22121\\ \hline
		\end{tabular}}
		
	\only<8>{\begin{tabular}{|c|c|c|c|}
			\hline
			Стэк & Вход & Действие & Разбор \\ \hline					
			$I_0SI_1$ & $ab\$$ &\shift I$_{2}$  & 221\\ \hline
			$I_0SI_1aI_2$ & $b\$$ &\reduce S $\rightarrow$  & 221\\ \hline
			$I_0SI_1aI_2SI_3$ & $b\$$ &\shift I$_{2}$  & 2212\\ \hline
			$I_0SI_1aI_2SI_3bI_5$ & $\$$ &\reduce S $\rightarrow$  SaSb  & 22121\\ \hline
			$I_0SI_1$ & $\$$ & \textcolor{LimeGreen}{Accept}  & 22121\\ \hline
		\end{tabular}}

\end{center}	
	
\end{frame}

\end{document}

\begin{tikzpicture}[shorten >=1pt,node distance=5 em,on grid,auto,initial text=]
  %\draw[help lines] (0,0) grid (3,2);
  \node[state,initial]  (q_0)                      {$[S^\prime \to .S,\$]$};
  \node[state]          (q_1) [ right = of q_0] {$ S \to . SaSb3,\$ $};
%		 	\node[state]          (q_2) [ below = of q_0] {$ S \to . \eps,\$ $};
 % \node[state,accepting](q_3) [below right=of q_1] {$q_3$};
  \path[->] 
	(q_0)	edge	[loop below]	node	{0}	()
			edge	[bend left] 	node	{1}	(q_1)
 	(q_1)	edge	[bend left]		node	{$\eps$} (q_0);
\end{tikzpicture}

\section{Как теория становится практикой OLD}		%In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory 

\begin{frame}{Формальные грамматики}

\begin{block}{Контекстно-свободные грамматики}
   \begin{itemize}
   	\item  $ S \to NP\, VP \mid NP\, V\text{, что } S$ 
	\item $ VP \to V\, NP$ 
	\item  $ NP \to \text{мама} \mid \text{папа} $\quad  $ V \to \text{любить} \mid  \text{знать} $ %\text{целовать} \mid \text{ездить} \mid
   \end{itemize}
  

\end{block}\pause

\begin{center}
	\begin{tikzpicture}
	   \node {$S$} 
	    child {node {$NP$}
			child {node {Папа}}
		} 
	    child {node {$VP$} 
	      child {node {$V$}
				child { node {любит}}	   
		  } 
	      child {node {$NP$}
				child { node {маму}}
		  } 
	    };


	\end{tikzpicture} 
\end{center}


	
\end{frame}



\begin{frame}{Eшё пример} 

\begin{center}
	 \begin{tikzpicture}
		   \node {$S$} 
			  child {node {$NP$} 
					child{ node {Мама} }
				}
		      child {node {$V$} 
					child{ node{знает} }
			   }
			  child {node {, что} }
		 	  child {node {$S$} 
		      	 child {node {$NP$}
						child {node {папа}}
					} 
				    child {node {$VP$} 
				      child {node {$V$}
							child { node {любит}}	   
					  } 
				      child {node {$NP$}
							child { node {маму}}
					  } 
				    }
			  };

			   
				  
		\end{tikzpicture}
  	
\end{center}	
\end{frame}

\begin{frame}{Проблемы}
	
	\begin{example}
		Люблю целую еду
	\end{example}\pause
	     
	\begin{example}
		Проблема равенства языков, порождаемых двумя контекстно-свободными грамматиками неразрешима.
	\end{example}
	
\end{frame}

\begin{frame}{Достижения}
	\begin{multicols}{2}

	  \begin{center}  	
		\begin{tikzpicture}[scale=0.6]
			\node {$E$} %root
				child{ node   {$T$}
				 	child{ node {$T$}
						child{ node{$F$}
							child{ node {$a$} }
						}
					}
					child{ node {$*$} }
					child{ node {$F$}
						child{ node {$($}  }
						child{ node {$E$}  
							child{ node{$E$}
								child{ node{$T$}
									child{ node{$F$}
										child{ node {$a$} }										
									}
								}
							}
							child{ node{$+$} }
							child{ node{$T$}
								child{ node{$F$}
									child{ node {$a$} }										
								}
							}
						}
						child{ node {$)$}  }
					}
			};
		\end{tikzpicture}
     \end{center}
		\begin{center}
			 \begin{align*}
			 	E &\to E+T\\
			 	E &\to T\\
			 	T &\to T*F\\
				T &\to F\\
			 	F &\to (E)\\
			 	F &\to a
			\end{align*}
		
				\end{center}	
	\end{multicols}
\end{frame}
  








\end{document}

