\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{{[}deleted{]}}
\pdfinfo{
  /Title (nrw.pdf)
  /Creator (Cheatography)
  /Author ({[}deleted{]})
  /Subject (Nrw 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}{A3A3A3}
\definecolor{LightBackground}{HTML}{F3F3F3}
\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{Nrw Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{{[}deleted{]}} via \textcolor{DarkBackground}{\uline{cheatography.com/24231/cs/5910/}}}
\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}{[}deleted{]} \\
  \uline{cheatography.com/deleted-24231} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Published 30th October, 2015.\\
   Updated 13th May, 2016.\\
   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}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{DefinitIons}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Finite Automaton(FA)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}5-tuple(Q,Σ,δ,q,F) where \{\{nl\}\} i)Q = states \{\{nl\}\} ii)Σ = input alphabet \{\{nl\}\} iii)δ:QxΣ -\textgreater{} Q = transitions \{\{nl\}\} iv)qϵQ = start state \{\{nl\}\} v)F = accept states} \tn 
% Row Count 5 (+ 5)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Regular Language(RL)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}Is recognized by some FA and is closed under the operations: \{\{nl\}\} i)∪\{\{nl\}\} ii)∘\{\{nl\}\} iii)*\{\{nl\}\} iv)∩\{\{nl\}\} v)Complementation} \tn 
% Row Count 9 (+ 4)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Deterministic Finite Automaton(DFA)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}FA where there is only one state that can be transitioned to from the current state and current input symbol.} \tn 
% Row Count 13 (+ 4)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Nondeterministic Finite Automaton(NFA)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}FA where there is one or more states that can be transitioned to from the current state and current input symbol.} \tn 
% Row Count 17 (+ 4)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Power Set}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}The set of all subsets of a language. \{\{nl\}\} Has size 2\textasciicircum{}|A|\textasciicircum{}.} \tn 
% Row Count 20 (+ 3)
% Row 5
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Regular Expression(RE)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}Is one of the following: \{\{nl\}\} i)a such that aϵΣ \{\{nl\}\} ii)ε \{\{nl\}\} iii)∅ \{\{nl\}\} iv)S∪T where S,T are RE \{\{nl\}\} v)S∘T where S,T are RE \{\{nl\}\} vi)S* where S is a RE} \tn 
% Row Count 25 (+ 5)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Generalized NFA(GNFA)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}5-tuple(Q,Σ,δ,q,a) where\{\{nl\}\} i)Q =states \{\{nl\}\} ii)Σ = input alphabet \{\{nl\}\} iii)δ:(Q-\{a\})x(Q-\{q\}) -\textgreater{} R = transitions\{\{nl\}\} iv)qϵQ = start state \{\{nl\}\} v)aϵQ = accept state\{\{nl\}\}\{\{nl\}\} {\bf{Also must meet the following conditions}}:\{\{nl\}\} i)Start state has transitions arrows going out, but none coming into itself\{\{nl\}\} ii)There is only one accept state with transition arrows coming in, but none going out from itself\{\{nl\}\} iii)Except for the start and accept states, only one arrow goes from every state to every other state, including an arrow to itself} \tn 
% Row Count 38 (+ 13)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{CFL Definitions}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Context Free Languages(CFL)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}Languages described by context free grammars and pushdown automata. They include all RL.\{\{nl\}\}Any language that can be generated by a CFG.} \tn 
% Row Count 4 (+ 4)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Context Free Grammar(CFG)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}4-tuple(V,Σ,R,S), where: \{\{nl\}\}i)V = set of variables \{\{nl\}\}ii)Σ = set of terminals, disjoint from V \{\{nl\}\}iii)R = set of rules, with each rule being a variable and a string of variables and terminals \{\{nl\}\}iv)SϵV = start variable} \tn 
% Row Count 10 (+ 6)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Ambiguity}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}A string is ambiguous if there is more than one way to generate the string. If a CFG has an ambiguous string, then the grammar is ambiguous.\{\{nl\}\}If an ambiguous CFG generates a CFL that can only be generated by ambiguous grammars, then it is {\bf{inherently ambiguous}}.} \tn 
% Row Count 17 (+ 7)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Leftmost Derivation}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}At each step of string derivation, the leftmost variable is replaced.} \tn 
% Row Count 20 (+ 3)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Chomsky Normal Form(CNF)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}Every rule is of the form A-\textgreater{}BC or A-\textgreater{}a, where a is a terminal and A,B,C are variables. We allow S-\textgreater{}e, where S is the start variable.} \tn 
% Row Count 24 (+ 4)
% Row 5
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Pushdown Automaton(PDA)}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}6-tuple(Q,Σ,Γ,δ,q,F), where \{\{nl\}\}i)Q = states \{\{nl\}\}ii),Σ, = input alphabet \{\{nl\}\}iii)Γ = stack alphabet\{\{nl\}\}iv)δ:QxΣxΓ -\textgreater{} P(QxΓ) = transition function\{\{nl\}\}v)qϵQ = start state\{\{nl\}\}vi)FϵQ = accept states \{\{nl\}\}\{\{nl\}\}By definition, they are nondeterministic.} \tn 
% Row Count 31 (+ 7)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Theorems, Lemmas, Corallaries for RL}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Every NFA has an equivalent DFA} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{A language is regular iff some NFA recognizes it} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{If a language is described by a RE, then it is regular} \tn 
% Row Count 4 (+ 2)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{If a language is regular, it is described by a RE} \tn 
% Row Count 5 (+ 1)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{A language is regular iff some RE describes it} \tn 
% Row Count 6 (+ 1)
% Row 5
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Pigeonhole Principle}}: If we stuff n items into less than n holes, at least one hole must have more than one item in it} \tn 
% Row Count 9 (+ 3)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{There is an algorithm that can determine if two FA are equivalent} \tn 
% Row Count 11 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Pumping Lemma for RL}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Let A be a RL. Then there exists a number p(pumping length of A), such that any string from the language A having length at least p can be broken into three pieces, s=xyz such that:} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}i)∀ i≥0, xy\textasciicircum{}i\textasciicircum{}z is an element of A \{\{nl\}\} ii)|y|\textgreater{}0 \{\{nl\}\} iii)|xy|≤p} \tn 
% Row Count 6 (+ 6)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Theorem, Lemmas, Corallaries for CFL}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Any CFL can be generated by a CFG in Chomsky Normal Form.} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{A language is context free(CFL) iff some PDA recognizes it.} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{If a language is context free(CFL), then some PDA recognizes it.} \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{If a PDA recognizes some language, then the language is contex free(CFL).} \tn 
% Row Count 8 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Every regular language is context free.} \tn 
% Row Count 9 (+ 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}{Pumping Lemma for CFL}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{If A is a CFL, then there is a number p(pumping length of A) where, if s is any string in A with length at least p, then s may be divided into 5 pieces, s = uvxyz where:} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}i)∀ i≥0, uv\textasciicircum{}i\textasciicircum{}xy\textasciicircum{}i\textasciicircum{}z is an element of A \{\{nl\}\} ii)|vy|\textgreater{}0 \{\{nl\}\} iii)|vxy|≤p} \tn 
% Row Count 6 (+ 6)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Contradictions by condition}}:} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}ii)At least one of v and y cannot be the empty string \{\{nl\}\} iii)Can be used in showing some languages are not CFL} \tn 
% Row Count 10 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


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

\end{document}