\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{Vipera}
\pdfinfo{
  /Title (automata-cfg-and-pda.pdf)
  /Creator (Cheatography)
  /Author (Vipera)
  /Subject (Automata - CFG \& PDA Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{2F61A3}
\definecolor{LightBackground}{HTML}{F2F5F9}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{Automata - CFG \& PDA Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{Vipera} via \textcolor{DarkBackground}{\uline{cheatography.com/128346/cs/25668/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}Vipera \\
  \uline{cheatography.com/vipera} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Published 12th December, 2020.\\
   Updated 12th December, 2020.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{3}

\begin{tabularx}{5.377cm}{x{3.18528 cm} x{1.79172 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{CFG Definition}}  \tn
% Row 0
\SetRowColor{LightBackground}
Context-Free Grammar: & {\bf{G = (V,T,S,P)}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\bf{V:}} Set of variables & \{S\} \tn 
% Row Count 3 (+ 1)
% Row 2
\SetRowColor{LightBackground}
{\bf{T:}} Set of terminal symbols & \{a,b\} \tn 
% Row Count 5 (+ 2)
% Row 3
\SetRowColor{white}
{\bf{S:}} Start variable & S \tn 
% Row Count 6 (+ 1)
% Row 4
\SetRowColor{LightBackground}
{\bf{P:}} Set of productions & \{S→aSb, S→ε\} \tn 
% Row Count 8 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{{\bf{ONLY ONE}} variable → String of variables {\bf{and}} terminals}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.64241 cm} x{3.33459 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Union of Two Languages}}  \tn
% Row 0
\SetRowColor{LightBackground}
Example: & L=\{0\textasciicircum{}n\textasciicircum{}1\textasciicircum{}n\textasciicircum{}|n≥0\} U \{1\textasciicircum{}n\textasciicircum{}0\textasciicircum{}n\textasciicircum{}|n≥0\} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
Break problem in two & {\bf{S\textasciicircum{}1\textasciicircum{}}}→0S\textasciicircum{}1\textasciicircum{}1|ε \{\{nl\}\}{\bf{S\textasciicircum{}2\textasciicircum{}}}→1S\textasciicircum{}2\textasciicircum{}0|ε \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
Merge & {\bf{S→S\textasciicircum{}1\textasciicircum{}|S\textasciicircum{}2\textasciicircum{}}} \{\{nl\}\}S\textasciicircum{}1\textasciicircum{}→0S\textasciicircum{}1\textasciicircum{}1|ε \{\{nl\}\}S\textasciicircum{}2\textasciicircum{}→1S\textasciicircum{}2\textasciicircum{}0|ε \tn 
% Row Count 7 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.51041 cm} x{1.09848 cm} x{1.96811 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{3}{x{5.377cm}}{\bf\textcolor{white}{Simplifications of CFG}}  \tn
% Row 0
\SetRowColor{LightBackground}
Substitution\{\{nl\}\}{\emph{(B →y\textasciicircum{}1\textasciicircum{})}} & A→xBz\{\{nl\}\}B→y\textasciicircum{}1\textasciicircum{} & \{\{nl\}\}A→xBz|xy\textasciicircum{}1\textasciicircum{}z \tn 
% Row Count 3 (+ 3)
% Row 1
\SetRowColor{white}
 & A→xBBz\{\{nl\}\}B→y\textasciicircum{}1\textasciicircum{} & \{\{nl\}\}A→xBBz|xBy\textasciicircum{}1\textasciicircum{}z\{\{nl\}\}|xy\textasciicircum{}1\textasciicircum{}Bz|xy\textasciicircum{}1\textasciicircum{}y\textasciicircum{}1\textasciicircum{}z \tn 
% Row Count 6 (+ 3)
% Row 2
\SetRowColor{LightBackground}
Removing ε\{\{nl\}\}{\emph{(B →ε)}} & A→xBz\{\{nl\}\}B→ε & \{\{nl\}\}A→xBz|xz \tn 
% Row Count 9 (+ 3)
% Row 3
\SetRowColor{white}
Unit Production\{\{nl\}\}{\emph{(A →B)}} & A→B\{\{nl\}\}B→bb & A→bb\{\{nl\}\}B→bb \tn 
% Row Count 12 (+ 3)
% Row 4
\SetRowColor{LightBackground}
Useless Productions & A→aA \seqsplit{(infinite)} & ∴ remove \tn 
% Row Count 14 (+ 2)
% Row 5
\SetRowColor{white}
 & \seqsplit{Unreachable} from S & ∴ remove \tn 
% Row Count 16 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\SetRowColor{LightBackground}
\mymulticolumn{3}{x{5.377cm}}{{\emph{Step 1:}} Remove Nullable Variables \newline {\emph{Step 2:}} Remove Unit-Production \newline {\emph{Step 3:}} Remove Useless Variables}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{DFA to CFG}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{1. Create variable {\bf{R\textasciicircum{}i\textasciicircum{}}} for every state {\bf{q\textasciicircum{}i\textasciicircum{}}}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{2. Create rule {\bf{R\textasciicircum{}i\textasciicircum{} → aR\textasciicircum{}j\textasciicircum{}}} for every transition {\bf{δ(q\textasciicircum{}i\textasciicircum{},a) → q\textasciicircum{}j\textasciicircum{}}}} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{3. For accept states {\bf{q\textasciicircum{}i\textasciicircum{}}} create rule {\bf{R\textasciicircum{}i\textasciicircum{} → ε}}} \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{4. For initial state {\bf{q\textasciicircum{}0\textasciicircum{}}} make {\bf{R\textasciicircum{}0\textasciicircum{}}} the start variable} \tn 
% Row Count 8 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.54287 cm} x{3.43413 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Conversion to Chomsky Normal Form}}  \tn
% Row 0
\SetRowColor{LightBackground}
Step 0:\{\{nobreak\}\} & If start symbol (S) is on the right hand side, change start symbol\{\{nl\}\}{\emph{S\textasciicircum{}0\textasciicircum{}→S}} \tn 
% Row Count 4 (+ 4)
% Row 1
\SetRowColor{white}
Step 1:\{\{nobreak\}\} & Remove Nullable variables ({\emph{A→ε}}) and Unit productions ({\emph{A→B}}) \tn 
% Row Count 7 (+ 3)
% Row 2
\SetRowColor{LightBackground}
Step 2:\{\{nobreak\}\} & For every symbol {\emph{a}} add {\emph{T\textasciicircum{}a\textasciicircum{}→a}} \tn 
% Row Count 9 (+ 2)
% Row 3
\SetRowColor{white}
Step 3:\{\{nobreak\}\} & Replace A→C\textasciicircum{}1\textasciicircum{}C\textasciicircum{}2\textasciicircum{}...C\textasciicircum{}n\textasciicircum{} with\{\{nl\}\}A→C\textasciicircum{}1\textasciicircum{}V\textasciicircum{}1\textasciicircum{}\{\{nl\}\}V\textasciicircum{}1\textasciicircum{}→C\textasciicircum{}2\textasciicircum{}V\textasciicircum{}2\textasciicircum{}\{\{nl\}\}...\{\{nl\}\}V\textasciicircum{}n-2\textasciicircum{}→C\textasciicircum{}n-1\textasciicircum{}C\textasciicircum{}n\textasciicircum{} \tn 
% Row Count 13 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{Chomsky form only has productions in forms \newline A→BC \newline A→a}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.94103 cm} x{3.03597 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Greibach Normal Form}}  \tn
% Row 0
\SetRowColor{LightBackground}
All Productions have form: & A→aV\textasciicircum{}1\textasciicircum{}V\textasciicircum{}2\textasciicircum{}..V\textasciicircum{}k\textasciicircum{} : k≥0 \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{5.377cm}}{Example} \tn 
% Row Count 3 (+ 1)
% Row 2
\SetRowColor{LightBackground}
S→abSb\{\{nl\}\}S→aa & S→aT\textasciicircum{}b\textasciicircum{}ST\textasciicircum{}b\textasciicircum{}\{\{nl\}\}S→aT\textasciicircum{}a\textasciicircum{}\{\{nl\}\}T\textasciicircum{}a\textasciicircum{}→a\{\{nl\}\}T\textasciicircum{}b\textasciicircum{}→b \tn 
% Row Count 6 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{PDA}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Transitions: {\bf{a, b → c}} means when input is a, remove {\emph{b}} from stack and add {\emph{c}}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{If the automaton attempts to pop from empty stack then it halts and rejects input.} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{A string is accepted if there is a computation such that:\{\{nl\}\}All the input is consumed\{\{nl\}\}The last state is an accepting state\{\{ac\}\}} \tn 
% Row Count 7 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.63781 cm} x{2.33919 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{PDA Formalities}}  \tn
% Row 0
\SetRowColor{LightBackground}
PDA Representation & {\bf{M=(Q,Σ,Γ,δ,q0,z,F)}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\bf{Q:}} States & \{q0,q1,q2\} \tn 
% Row Count 3 (+ 1)
% Row 2
\SetRowColor{LightBackground}
{\bf{Σ:}} Input Alphabet & \{a,b\} \tn 
% Row Count 5 (+ 2)
% Row 3
\SetRowColor{white}
{\bf{Γ:}} Stack Alphabet & \{a,b,\$\} \tn 
% Row Count 7 (+ 2)
% Row 4
\SetRowColor{LightBackground}
{\bf{δ:}} Transition Functions & δ(q,a,w1)=\{(q2,w2)\} \tn 
% Row Count 9 (+ 2)
% Row 5
\SetRowColor{white}
{\bf{q0:}} Initial State & q0 \tn 
% Row Count 10 (+ 1)
% Row 6
\SetRowColor{LightBackground}
{\bf{z:}} Stack Start Symbol & \$ \tn 
% Row Count 12 (+ 2)
% Row 7
\SetRowColor{white}
{\bf{F:}} Accept States & \{q2\} \tn 
% Row Count 13 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{CFG to PDA}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Start with PDA of q0 →\textasciicircum{}ε,ε→S\textasciicircum{}→q1 →\textasciicircum{}ε,\$→\$\textasciicircum{}→q2} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{For each CFG production {\emph{A→w}} add {\bf{ε,A→w}}} \tn 
% Row Count 3 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{For each CFG terminal {\emph{a}} add {\bf{a,a→ε}}} \tn 
% Row Count 4 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{"Easy" PDA to CFG}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{\{\{ac\}\}For the pair of transitions:\{\{nl\}\}ⓟ→\textasciicircum{}a,ε→t\textasciicircum{}→ⓡ   ⓢ→\textasciicircum{}b,t→ε\textasciicircum{}→ⓠ} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Add the production: A\textasciicircum{}pq\textasciicircum{}→aA\textasciicircum{}rs\textasciicircum{}b\{\{nl\}\}For each state {\bf{p}} add: A\textasciicircum{}pp\textasciicircum{}→ε\{\{nl\}\}For each state-triple (p,q,r) add: A\textasciicircum{}pr\textasciicircum{}→A\textasciicircum{}pq\textasciicircum{}A\textasciicircum{}qr\textasciicircum{}} \tn 
% Row Count 5 (+ 3)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{\{\{ac\}\}For initial state and accept state:\{\{nl\}\}→⓪   \&   🅐} \tn 
% Row Count 7 (+ 2)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Add the production: S→A\textasciicircum{}0a\textasciicircum{}} \tn 
% Row Count 8 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Easy}} PDAs: \newline • Have only 1 accept state \newline • When accepting a string, the stack is empty (only inital symbol) \newline • Each transition pushes {\bf{or}} pops}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.4885 cm} x{2.4885 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{PDA to "Easy" PDA}}  \tn
% Row 0
\SetRowColor{LightBackground}
1. The PDA has a single accept state & Create new accept state and make ε,ε→ε transitions from old accept states to the new \tn 
% Row Count 5 (+ 5)
% Row 1
\SetRowColor{white}
2. Use new initial stack symbol \# & New initial state, that transitions to a new state with ε,ε→@ (auxiliary symbol) that transitions to the old initial state with ε,ε→\$ \tn 
% Row Count 13 (+ 8)
% Row 2
\SetRowColor{LightBackground}
3. On acceptance the stack contains only  stack symbol \# & Old accept state transitions to new  to new accept state with ε,@→ε, ανδ self loops with ε,x→ε where ∀x∈Γ-\{@,\#\} \tn 
% Row Count 20 (+ 7)
% Row 3
\SetRowColor{white}
4. Transitions can't push {\bf{and}} pop & Replace any\{\{nl\}\} ⓘ→\textasciicircum{}σ,a→b\textasciicircum{}→ⓙ \{\{nl\}\}with\{\{nl\}\} ⓘ→\textasciicircum{}σ,a→ε\textasciicircum{}→ⓚ→\textasciicircum{}ε,ε→b\textasciicircum{}→ⓙ\{\{ac\}\} \tn 
% Row Count 26 (+ 6)
% Row 4
\SetRowColor{LightBackground}
5. 4. Transitions can't neither push nor pop & Replace any\{\{nl\}\} ⓘ→\textasciicircum{}σ,ε→ε\textasciicircum{}→ⓙ \{\{nl\}\}with\{\{nl\}\} ⓘ→\textasciicircum{}σ,ε→∂\textasciicircum{}→ⓚ→\textasciicircum{}ε,∂→ε\textasciicircum{}→ⓙ\{\{ac\}\} \tn 
% Row Count 32 (+ 6)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}