\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.pdf)
  /Creator (Cheatography)
  /Author (Vipera)
  /Subject (Automata 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}{9E2020}
\definecolor{LightBackground}{HTML}{F8F1F1}
\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 Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{Vipera} via \textcolor{DarkBackground}{\uline{cheatography.com/128346/cs/25093/}}}
\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 11th 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{2.38896 cm} x{2.58804 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{DFA (Deterministic Finite Automaton)}}  \tn
% Row 0
\SetRowColor{LightBackground}
Automaton Representation & {\bf{M=(Q,Σ,δ,q0,F)}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\bf{Q:}} Set of states & \{q0,q1,q2\} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
{\bf{Σ:}} input alphabet & \{a,b\} \& ε ∉ Σ \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
{\bf{δ:}} transition function & δ(q,x)=q' \tn 
% Row Count 8 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{{\bf{q0:}} initial state} \tn 
% Row Count 9 (+ 1)
% Row 5
\SetRowColor{white}
{\bf{F:}} set of accepting states & \{q2\} \tn 
% Row Count 11 (+ 2)
% Row 6
\SetRowColor{LightBackground}
Language of Automaton & L(M)=\{ w∈Σ* : δ*(q0,w)∈F\} \tn 
% Row Count 13 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{Languages are regular if a DFA exists for that language. \newline DFA: Each state has one transition for evrey alphabet}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.38896 cm} x{2.58804 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{NFA (Non-deterministic Finite Automaton)}}  \tn
% Row 0
\SetRowColor{LightBackground}
Formal Definition & {\bf{M=(Q,Σ,Δ,S,F)}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\bf{Q:}} Set of states & \{q0,q1,q2\} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
{\bf{Σ:}} input alphabet & \{a,b\} \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
{\bf{Δ:}} transition function & Δ(q,x)=\{q1,q2,...\} (include ε) \tn 
% Row Count 8 (+ 2)
% Row 4
\SetRowColor{LightBackground}
{\bf{S:}} initial states & \{q0\} \tn 
% Row Count 10 (+ 2)
% Row 5
\SetRowColor{white}
{\bf{F:}} set of accepting states & \{q2\} \tn 
% Row Count 12 (+ 2)
% Row 6
\SetRowColor{LightBackground}
Language of Automaton & L(M) = \{w1,w2,...,wn\} \tn 
% Row Count 14 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{NFA: Each state can have different transition with the same language output}  \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}{NFA to DFA Conversion}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{1. Set initial state of NFA to initial state of DFA} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{2. Take the states in the DFA, and compute in the NFA what the union Δ of those states for each letter in the alphabet and add them as new states in the DFA.\{\{nl\}\}{\emph{For example if (q0,a) takes you to \{q1,q2\} add a state \{q1,q2\}. If there isn't one, the add state null}}} \tn 
% Row Count 8 (+ 6)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{3. Set every DFA state as accepting if it contains an accepting state from the NFA} \tn 
% Row Count 10 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{The language for the NFA (M) and DFA (M') are equivalent \{\{nl\}\} L(M)=L(M')}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.44333 cm} x{3.53367 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Properties of Regex}}  \tn
% Row 0
\SetRowColor{LightBackground}
L1 ∪ L2 & Initial state has two ε transitions, one to L1 and one to L2 \tn 
% Row Count 3 (+ 3)
% Row 1
\SetRowColor{white}
L1L2 & L1 accept state tranitions (ε) to L2 initial state \tn 
% Row Count 5 (+ 2)
% Row 2
\SetRowColor{LightBackground}
L1* & New initial state transitions to L1 initial state. New accept state transitions (ε) from L1 accept state. Initial to accept state transition transitions (ε) and vice versa. \tn 
% Row Count 12 (+ 7)
% Row 3
\SetRowColor{white}
L1\textasciicircum{}R\textasciicircum{} (reverse) & Reverse all transitions. Make initial state accepting state and vice versa. \tn 
% Row Count 15 (+ 3)
% Row 4
\SetRowColor{LightBackground}
!(L1) Complement & Accepting states become non-accepting and vice versa \tn 
% Row Count 17 (+ 2)
% Row 5
\SetRowColor{white}
L1 ∩ L2 & !( !(L1) ∪ !(L2) ) \tn 
% Row Count 18 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{P.S. To turn multiple states to one accept state in an NFA, just add a new accept state, and add transition to the old accept states with language ε.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.83689 cm} x{2.14011 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Intersection DFA1 ∩ DFA2}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{Transitions}}\{\{nl\}\}M\textasciicircum{}1\textasciicircum{}: q1→\textasciicircum{}a\textasciicircum{}→q2 \{\{nl\}\} M\textasciicircum{}2\textasciicircum{}: p1→\textasciicircum{}a\textasciicircum{}→p2 & DFA M: (q1,p1)→\textasciicircum{}a\textasciicircum{}→(q2,p2) \tn 
% Row Count 4 (+ 4)
% Row 1
\SetRowColor{white}
{\bf{Initial State}}\{\{nl\}\}M\textasciicircum{}1\textasciicircum{}: q0 \{\{nl\}\} M\textasciicircum{}2\textasciicircum{}: p0 & DFA M: (q0,p0) \tn 
% Row Count 7 (+ 3)
% Row 2
\SetRowColor{LightBackground}
{\bf{Accept State}}\{\{nl\}\}M\textasciicircum{}1\textasciicircum{}: qi \{\{nl\}\} M\textasciicircum{}2\textasciicircum{}: pj,pk & DFA M: (qi,pj) , (qi,pk) \tn 
% Row Count 10 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.84149 cm} x{3.13551 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Regular Expressions}}  \tn
% Row 0
\SetRowColor{LightBackground}
L(r1+r2) & = L(r1) ∪ L(r2) \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
L(r1•r2) & = L(r1)L(r2) \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
L(r1*) & = (L(r1))* \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
L(a) & = \{a\} \tn 
% Row Count 4 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{Precedence: {\bf{*}} → \textasciicircum{}{\bf{+}}\textasciicircum{} → {\bf{•}} → {\bf{+}}}  \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}{NFA to Regular Language}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{1. Transform each transition into regex (e.g. (a,b) is a+b} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{2. Remove each state one by one, until you are left with the initial and accepting state} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{3. Resulting regular expression: {\bf{r = r1* r2(r4+r3r1*r2)*}} where: \{\{nl\}\}r1:  initial → initial \{\{nl\}\}r2: initial → accepting \{\{nl\}\}r3: accepting → initial \{\{nl\}\}r4: accepting → accepting} \tn 
% Row Count 8 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Proving Regularity with Pumping Lemma}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Prove than an infinite language L is not regular:} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{1. Assume L is regular} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{2. The pumping lemma should hold for L} \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{3. Use the pumping lemma to obtain a contradiction:} \tn 
% Row Count 5 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{~~a. Let m be the critical length for L} \tn 
% Row Count 6 (+ 1)
% Row 5
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{~~b. Choose a particular string {\emph{w∈L}} which satisfies the length condition {\emph{|w|≥m}}} \tn 
% Row Count 8 (+ 2)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{~~c. Write {\emph{w=xyz}}} \tn 
% Row Count 9 (+ 1)
% Row 7
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{~~d. Show that {\emph{w'=xy\textasciicircum{}i\textasciicircum{}z∉L for some i≠1}}} \tn 
% Row Count 11 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


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

\end{document}