Tikz diagram for Thompson's Construction of Finite Automata from Regular Expressions

thompsons.tex

\usepackage{subcaption,tikz}
\usetikzlibrary{arrows.meta,bending,automata,shapes}

\begin{figure}[t]
\centering
\begin{subfigure}[b]{0.3\textwidth}
\begin{tikzpicture}[->,>={Stealth[round]},shorten >=1pt,auto,semithick]
  \tikzstyle{vertex}=[circle,draw=black,minimum size=30pt,inner sep=0pt]
  \node[vertex] (q)[initial, initial where=left,initial text={}]
                at (1,0) {$q$};
  \node[vertex] (f)[accepting]
                at (3,0) {$f$};
\end{tikzpicture}
\caption{Empty Set $\emptyset$}
\label{fig:empty-set}
\end{subfigure}
%
\begin{subfigure}[b]{0.3\textwidth}
\begin{tikzpicture}[->,>={Stealth[round]},shorten >=1pt,auto,semithick]
  \tikzstyle{vertex}=[circle,draw=black,minimum size=30pt,inner sep=0pt]
  \node[vertex] (q)[initial, initial where=left,initial text={}]
                at (1,0) {$q$};
  \node[vertex] (f)[accepting]
                at (3,0) {$f$};

  \path (q) edge  node {$\epsilon$} (f);

\end{tikzpicture}
\caption{Empty String $\epsilon$}
\label{fig:empty-string}
\end{subfigure}
%
\begin{subfigure}[b]{0.3\textwidth}
\begin{tikzpicture}[->,>={Stealth[round]},shorten >=1pt,auto,semithick]
  \tikzstyle{vertex}=[circle,draw=black,minimum size=30pt,inner sep=0pt]
  \node[vertex] (q)[initial, initial where=left,initial text={}]
                at (1,0) {$q$};
  \node[vertex] (f)[accepting]
                at (3,0) {$f$};

  \path (q) edge  node {$a$} (f);

\end{tikzpicture}
\caption{Character $a \in \Sigma$}
\label{fig:character}
\end{subfigure}
\caption{Constructing Finite Automata from Regular Expression Constants}
\label{fig:regex-consts}
\end{figure}


\begin{figure}[t]
\centering
\begin{subfigure}[c]{\textwidth}
\begin{tikzpicture}[->,>={Stealth[round]},shorten >=1pt,auto,semithick]
  \tikzstyle{vertex}=[circle,draw=black,minimum size=30pt,inner sep=0pt]

  \node[vertex] (q)[initial, initial where=left,initial text={}] at (0,0) {$q$};
  \node[vertex] (q1) at (2,0) {};
  \node[vertex] (q2)[accepting] at (4,0) {};
  \node[vertex] (q3) at (7,0) {};
  \node[vertex] (q4)[accepting] at (9,0) {};
  \node[vertex] (f)[accepting] at (11,0) {$f$};

  \path (q) edge node {$\epsilon$} (q1);
  \path (q2) edge node {$\epsilon$} (q3);
  \path (q4) edge node {$\epsilon$} (f);
  \path[dashed] (q1) edge node {$R$} (q2);
  \path[dashed] (q3) edge node {$S$} (q4);

  \draw[rounded corners] (1.25,-0.75) rectangle (4.75,0.75);
  \draw[rounded corners] (6.25,-0.75) rectangle (9.75,0.75);

\end{tikzpicture}
\caption{Concatentation}
\label{fig:regex-concat}
\end{subfigure}

\begin{subfigure}[b]{0.49\textwidth}
\centering
\begin{tikzpicture}[->,>={Stealth[round]},shorten >=1pt,auto,semithick]
  \tikzstyle{vertex}=[circle,draw=black,minimum size=30pt,inner sep=0pt]

  \node[vertex] (q)[initial, initial where=left,initial text={}] at (0,0) {$q$};
  \node[vertex] (f)[accepting] at (5,0) {$f$};
  \node[vertex] (q1) at (1.5,1) {};
  \node[vertex] (q2)[accepting] at (3.5,1) {};
  \node[vertex] (q3) at (1.5,-1) {};
  \node[vertex] (q4)[accepting] at (3.5,-1) {};

  \path (q) edge node {$\epsilon$} (q1)
        (q) edge node {$\epsilon$} (q3);
  \path (q2) edge node {$\epsilon$} (f)
        (q4) edge node {$\epsilon$} (f);
  \path[dashed] (q1) edge node {$R$} (q2);
  \path[dashed] (q3) edge node {$S$} (q4);

  \draw[rounded corners] (0.75, 0.2) rectangle (4.25, 1.8);
  \draw[rounded corners] (0.75,-0.2) rectangle (4.25,-1.8);

\end{tikzpicture}
\caption{Union}
\label{fig:regex-union}
\end{subfigure}
%
\begin{subfigure}[b]{0.49\textwidth}
\centering
\begin{tikzpicture}[->,>={Stealth[round]},shorten >=1pt,auto,semithick]
  \tikzstyle{vertex}=[circle,draw=black,minimum size=30pt,inner sep=0pt]

  \node[vertex] (q)[initial, initial where=left,initial text={}] at (0,0) {$q$};
  \node[vertex] (q1) at (2,0) {};
  \node[vertex] (q2)[accepting] at (4,0) {};
  \node[vertex] (f)[accepting] at (6,0) {$f$};

  \path (q) edge node {$\epsilon$} (q1);
  \path (q2) edge node {$\epsilon$} (f);
  \path[dashed] (q1) edge node {$R$} (q2);
  \draw (q2) to[out=90,in=90] node {$\epsilon$} (q1);
  \draw (q) to[out=270,in=270] node {$\epsilon$} (f);
  \draw[rounded corners] (1.25,-0.75) rectangle (4.75,0.75);

\end{tikzpicture}
\caption{Closure}
\label{fig:regex-closure}
\end{subfigure}
\caption{Constructing Finite Automata using Regular Expression Operations}
\label{fig:regex-ops}
\end{figure}