Finite automata and (deterministic) Turing machine running/drawing.

fa.sty

\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{fa}
  [2018/03/09 v0.3 Construct finite automata and Turing machines]

\RequirePackage{tikz}
\RequirePackage{etoolbox}

\usetikzlibrary{arrows.meta,automata,calc,chains,positioning}

% Define \emptystring to \varepsilon
\newrobustcmd*\emptystring{\ensuremath{\varepsilon}}

\protected\def\visiblespace{%
  \texttt{\textvisiblespace}%
}

\tikzset{
  % Draw state as a cat.
  cat state/.style={append after command={%
    (\tikzlastnode)edge[gray,rounded corners=6pt,-,shorten >=0pt,shorten <=0pt,to path={%
      (\tikztostart.110)--+(-.2,.4)--(\tikztostart.130)%
      (\tikztostart.80)--+(.2,.4)--(\tikztostart.60)%
      ($(\tikztostart.center)+(-.2,.05)$) .. controls +(-.2,.1) and +(.3,.1) .. ($(\tikztostart.center)+(-.8,.15)$)
      ($(\tikztostart.center)+(-.225,0)$) .. controls +(-.2,.1) and +(.3,.1) .. ($(\tikztostart.center)+(-.8,0)$)
      ($(\tikztostart.center)+(-.25,-.05)$) .. controls +(-.2,.1) and +(.3,.1) .. ($(\tikztostart.center)+(-.8,-.2)$)
      ($(\tikztostart.center)+(.2,.05)$) .. controls +(.2,.1) and +(-.3,.1) .. ($(\tikztostart.center)+(.8,.15)$)
      ($(\tikztostart.center)+(.225,0)$) .. controls +(.2,.1) and +(-.3,.1) .. ($(\tikztostart.center)+(.8,0)$)
      ($(\tikztostart.center)+(.25,-.05)$) .. controls +(.2,.1) and +(-.3,.1) .. ($(\tikztostart.center)+(.8,-.2)$)
    }](\tikzlastnode)%
  }},
  % Draw state as a bunny.
  bunny state/.style={append after command={%
    (\tikzlastnode)edge[gray,-,shorten >=0pt,shorten <=0pt,to path={%
      (\tikztostart)to[out=130,in=110,looseness=9](\tikztostart)%
      (\tikztostart)to[out=60,in=80,looseness=9](\tikztostart)%
      ($(\tikztostart.center)+(-.2,.05)$) .. controls +(-.2,.1) and +(.3,.1) .. ($(\tikztostart.center)+(-.8,.15)$)
      ($(\tikztostart.center)+(-.225,0)$) .. controls +(-.2,.1) and +(.3,.1) .. ($(\tikztostart.center)+(-.8,0)$)
      ($(\tikztostart.center)+(-.25,-.05)$) .. controls +(-.2,.1) and +(.3,.1) .. ($(\tikztostart.center)+(-.8,-.2)$)
      ($(\tikztostart.center)+(.2,.05)$) .. controls +(.2,.1) and +(-.3,.1) .. ($(\tikztostart.center)+(.8,.15)$)
      ($(\tikztostart.center)+(.225,0)$) .. controls +(.2,.1) and +(-.3,.1) .. ($(\tikztostart.center)+(.8,0)$)
      ($(\tikztostart.center)+(.25,-.05)$) .. controls +(.2,.1) and +(-.3,.1) .. ($(\tikztostart.center)+(.8,-.2)$)
    }](\tikzlastnode)%
  }},
  % Draw states as black circles filled with gray.
  every state/.style={minimum size=1cm, inner sep=1pt, fill=black!10},
  % Draw accepting states with an inner circle
  accepting/.style={path picture={
    \draw let \p1 = (path picture bounding box.north east),
              \p2 = (path picture bounding box.center)
          in
            (\p2)circle[x radius=\x1-\x2-2pt,y radius=\y1-\y2-2pt];
  }},
  rejecting/.style={},
  % No text on initial arrows.
  every initial by arrow/.style={initial text=},
  % Set the default bend angle, arrow style, and label style
  every edge/.style={
    draw,
    thick,
    bend angle=15,
    ->,
    auto,
    inner sep=2pt,
    >=stealth,
    shorten >=1pt,
    node font=\ttfamily
  },
  % Highlight nodes on given slides
  highlight/.code={\only<#1>{\pgfkeysalso{fill=yellow!75!black}}},
  highlight/.default=beamer,
  % Mark the given input symbol
  markinput/.code={\only<#1>{\pgfkeysalso{color=red!75!black}}},
  % Gray out the previous symbols (XXX: probably should be combined with
  % markinput)
  grayinput/.code={\alt<-#1>{}{\pgfkeysalso{color=black!25}}},
  % Make the states small
  small states/.style={
    every state/.append style={minimum size=.5cm, inner sep=0}
  }
  pda/.style={%
    node distance=1cm and 1.5cm,%
    transition/.style n args={3}{%
      edge label={$##1,##2\to##3$}%
    },%
    eps/.style={transition={\emptystring}{\emptystring}{\emptystring}},%
    push/.style={transition={\emptystring}{\emptystring}{##1}},%
    pop/.style={transition={\emptystring}{##1}{\emptystring}},%
    replace/.style 2 args={transition={\emptystring}{##1}{##2}},%
    push on/.style 2 args={transition={##1}{\emptystring}{##2}},%
    pop on/.style 2 args={transition={##1}{##2}{\emptystring}}%
  },
  tm/.style={%
    node distance=1cm and 1.5cm,%
  },
  minimum tape cells/.store in=\fa@tapecells,
}

\def\fa@tapecells{0}

\newcommand*\fa@err[1]{%
  \PackageError{fa}{#1}{}%
}

\newcommand\state[2][]{%
  \node[state,name={#2},#1]{\ensuremath{#2}}%
}
\newcommand\initial[2][]{%
  \node[state,initial,#1]{#2}%
}
\newcommand\accepting[2][]{%
  \node[state,accepting,#1]{#2}%
}

% \newdfa{name}{states}{transitions}
%
% States are a comma-separated list of states with the following format.
%   name/displayname/options
% The name is used in the transitions. The displayname is shown in the diagram
% and the options are TikZ options to the state node (see TikZ's automata
% library). In particular, initial denotes the initial state and accepting
% denotes the accepting states. Multiple options can be given as a
% brace-delimited, comma-separated list. E.g., q0/q_0/{initial,accepting}.
%
% Transitions are a comma-separated list of transitions with the following
% format.
%   x/a/y/edgeoptions/labeloptions
% Here, x and y are states and a is an input symbol such that y = delta(x, a).
% The edgeoptions apply to the TikZ edge operation and labeloptions apply to
% the label node. In both cases, multiple options can be given as a
% brace-delimited, comma-separated list.
%
% The input symbol can be a brace-delimited, comma-separated list of input
% symbols. E.g., q0/{a,b}/q1/loop above/.
\newcommand*\newdfa[3]{%
  \csgdef{#1@states}{#2}%
  \csgdef{#1@transitions}{#3}%
  \global\csundef{#1@initial}%
  \def\temp{initial}%
  \foreach \s/\n/\o in {#2}{%
    \foreach \x in \o {%
      \ifx\temp\x
        \global\cslet{#1@initial}\s
        \breakforeach
      \fi
    }%
    \ifcsdef{#1@initial}{\breakforeach}{}%
  }%
  \ifcsundef{#1@initial}{\NoInitialStateDefined}{}%
}

\newif\iffa@transitioned

% \dfarunfrom{dfa}{state}{input}
% Input is stored in \dfainput.
% Output state is stored in \dfastate.
% The state sequence is stored in \dfastates as a comma-separated list.
\newcommand*\dfarunfrom[3]{%
  \global\letcs\dfa@states{#1@states}%
  \global\letcs\dfa@trans{#1@transitions}%
  \xdef\dfalastrun{#1}%
  \xdef\dfastate{#2}%
  \xdef\dfainput{#3}%
  \xdef\dfastates{\dfastate}%
  \foreach \i in \dfainput {%
    \global\fa@transitionedfalse
    \foreach \s/\as/\r/\x/\y in \dfa@trans {%
      \ifx\s\dfastate
        \foreach \a in \as {%
          \ifx\a\i
            \global\let\dfastate\r
            \xappto\dfastates{,\r}%
            \global\fa@transitionedtrue
            \breakforeach
          \fi
        }%
        \iffa@transitioned
          \breakforeach
        \fi
      \fi
    }%
    \iffa@transitioned\else
      \gdef\dfastate{NO-MATCHING-TRANSITION}%
      \breakforeach
    \fi
  }%
}

% \dfarun{dfa}{input}
% Input is stored in \dfainput.
% Output state is stored in \dfastate.
% The state sequence is stored in \dfastates as a comma-separated list.
\newcommand*\dfarun[2]{%
  \dfarunfrom{#1}{\csuse{#1@initial}}{#2}%
}

% \newnfa{name}{states}{transitions}
%
% States are a comma-separated list of states with the following format.
%   name/displayname/options
% The name is used in the transitions. The displayname is shown in the diagram
% and the options are TikZ options to the state node (see TikZ's automata
% library). In particular, initial denotes the initial state and accepting
% denotes the accepting states. Multiple options can be given as a
% brace-delimited, comma-separated list. E.g., q0/q_0/{initial,accepting}.
%
% Transitions are a comma-separated list of transitions with the following
% format.
%   x/{a,b}/y/edgeoptions/labeloptions,
%   x/a/z/edgeoptions/labeloptions
% Here, x, y, and z are states and a is an input symbol such that
% {y, z} = delta(x, a) and b is such that {y} = delta(x, b).
% The edgeoptions apply to the TikZ edge operation and labeloptions apply to
% the label node. In both cases, multiple options can be given as a
% brace-delimited, comma-separated list.
%
% The input symbol can be a brace-delimited, comma-separated list of input
% symbols. E.g., q0/{a,b}/q1/loop above/.
\let\newnfa=\newdfa

% \fa@addalluniqueto{\listmacro}{\csvlist}
\newcommand*\fa@addalluniqueto[2]{%
  \expandafter\forcsvlist
  \expandafter{\expandafter\fa@adduniqueto\expandafter#1\expandafter}%
    \expandafter{#2}%
}

\newif\iffa@added

% \fa@adduniqueto{\listmacro}{item}
\newcommand*\fa@adduniqueto[2]{%
  \ifinlist{#2}{#1}{}{\global\fa@addedtrue\listgadd{#1}{#2}}%
}

% \fa@csvlisttolist{\listmacro}{\csvlistmacro}
\newcommand*\fa@csvlisttolist[2]{%
  \gdef#1{}%
  \expandafter\forcsvlist
  \expandafter{\expandafter\listgadd\expandafter#1\expandafter}%
    \expandafter{#2}%
}

% \fa@csvlistadd{\csvlistmacro}{item}
\newcommand*\fa@csvlistadd[2]{%
  \ifdefempty{#1}%
    {\gdef#1{#2}}%
    {\gappto{#1}{,#2}}%
}

% \fa@listtocsvlist{\csvlistmacro}{\listmacro}
\newcommand*\fa@listtocsvlist[2]{%
  \gdef#1{}%
  \forlistloop{\fa@csvlistadd{#1}}{#2}
}

% \fa@singlestep{\outputstates}{\inputsymbol}{curstate}
\newcommand*\fa@singlestep[3]{%
  \def\fa@curstate{#3}%
  \foreach \s/\as/\r/\x/\y in \fa@trans {%
    \ifx\s\fa@curstate
      \foreach \a in \as {%
        \ifx\a#2%
          \expandafter\fa@adduniqueto\expandafter#1\expandafter{\r}%
          \breakforeach
        \fi
      }%
    \fi
  }%
}

\newcommand*\fa@emptystring{\emptystring}

% \fa@epsclosure{\states}
% Compute the epsilon-closure of the states.
\newcommand*\fa@epsclosure[1]{%
  % This could be faster
  \global\fa@addedtrue
  \loop\iffa@added
    \global\fa@addedfalse
    \forlistloop{\fa@singlestep{#1}{\fa@emptystring}}{#1}%
  \repeat
}

\newif\iffapreeps

% \farunfrom{nfa}{states}{input}
% Input is stored in \fainput.
% Output states are stored in \fastate.
% The state sequence is stored in \fastates as a comma-separated list of
% brace-delimited, comma-separated states.
\newcommand*\farunfrom[3]{%
  \global\letcs\fa@states{#1@states}%
  \global\letcs\fa@trans{#1@transitions}%
  \xdef\fastate{#2}%
  \xdef\fainput{#3}%
  \iffapreeps
    \xdef\fastates{{\fastate},}%
  \else
    \gdef\fastates{}%
  \fi
  % Compute epsilon-closure
  \fa@csvlisttolist{\fa@nextstates}{\fastate}%
  \fa@epsclosure{\fa@nextstates}%
  % Add it to the list of states
  \fa@listtocsvlist{\fastate}{\fa@nextstates}%
  \xappto{\fastates}{{\fastate}}%
  \foreach \i in \fainput {%
    \global\let\fa@curstates=\fa@nextstates
    \gdef\fa@nextstates{}%
    % Loop over each current state and perform the single step transitions
    % for the state on input \i
    \forlistloop{\fa@singlestep{\fa@nextstates}{\i}}{\fa@curstates}%
    %
    \iffapreeps
      \fa@listtocsvlist{\fastate}{\fa@nextstates}%
      \xappto{\fastates}{,{\fastate}}%
    \fi
    \fa@epsclosure{\fa@nextstates}%
    \fa@listtocsvlist{\fastate}{\fa@nextstates}%
    \xappto{\fastates}{,{\fastate}}%
  }%
}

% \farun{nfa}{input}
% Input is stored in \fainput.
% Output states are stored in \fastate.
% The state sequence is stored in \fastates as a comma-separated list of
% brace-delimited, comma-separated states.
\newcommand*\farun[2]{%
  \fapreepsfalse
  \farunfrom{#1}{\csuse{#1@initial}}{#2}%
}

\newcommand*\farunpreeps[2]{%
  \fapreepstrue
  \farunfrom{#1}{\csuse{#1@initial}}{#2}%
}

% \fahighlight[options]{name}{state highlights}
% Draw and highlight the states corresponding to the sequence of states from
% state highlights
%
% name should be the name of the finite automaton
% state highlights should (expand to) be a comma separated, sequence of
% brace-delimited, comma-separated set of states
\newcommand*\fahighlight[3][]{%
  \global\letcs\fa@states{#2@states}%
  \global\letcs\fa@trans{#2@transitions}%
  \xdef\fa@hlstates{#3}%
  \begin{scope}[%
    /tikz/name/.append style={/tikz/alias={#2-##1}},%
    #1%
  ]%
  \foreach \fa@s/\fa@n/\fa@o in \fa@states {%
    \gdef\fa@hl{}%
    \foreach[count=\fa@c] \fa@xs in \fa@hlstates {%
      \foreach \fa@x in \fa@xs {%
        \ifx\fa@s\fa@x
          \ifdefempty{\fa@hl}%
            {\xdef\fa@hl{\fa@c}}%
            {\xappto\fa@hl{,\fa@c}}%
          \breakforeach
        \fi
      }%
    }%
    \toks0=\expandafter{\fa@o}%
    \toks2=\expandafter{\fa@n}%
    \edef\fa@temp{\noexpand\node[state,\ifdefempty{\fa@hl}{}{highlight={\fa@hl},}\the\toks0](\fa@s){\noexpand\ensuremath{\the\toks2}}}%
    \fa@temp;%
  }%
  \foreach \fa@s/\fa@a/\fa@r/\fa@x/\fa@y in \fa@trans {%
    \toks0=\expandafter{\fa@x}%
    \toks2=\expandafter{\fa@y}%
    \toks4=\expandafter{\fa@a}%
    \edef\fa@temp{\noexpand\path (\fa@s) edge[\the\toks0] node [\the\toks2] {\the\toks4} (\fa@r)}%
    \fa@temp;%
  }%
  \end{scope}%
}

% \fadraw[options]{automaton}
\newcommand*\fadraw[2][]{\fahighlight[#1]{#2}{}}

% \fainputhighlight[options]{input}
\newcommand*\fainputhighlight[2][]{%
  \xdef\fa@input{#2}
  \begin{scope}[start chain, node distance=0pt, every node/.style={inner sep=0pt}, #1]%
    \foreach \fa@x [count=\fa@i] in \fa@input
      \node [on chain, grayinput=\fa@i, markinput=\fa@i] {\strut\texttt{\fa@x}};%
  \end{scope}%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Compatibility
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \drawdfa[options]{dfa}
\newcommand*\dfadraw[2][]{%
  \fahighlight[#1]{#2}{}%
}

% \dfainputhighlightlast[options]
% Highlight the last sequence of input run by \dfarun.
\newcommand*\dfainputhighlightlast[1][]{%
  \fainputhighlight[#1]{\dfainput}%
}

% \dfahighlightlast[options]
% Draw and highlight the states corresponding to the sequence of states from
% the last run of \dfarun.
\newcommand*\dfahighlightlast[1][]{%
  \fahilight[#1]{\dfalastrun}{\dfastates}%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Turing machines
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*\newtm[3]{%
  \ifcsdef{fa@#1@states}{\fa@err{#1 already defined}}{}%
  \csgdef{fa@#1@states}{#2}%
  \csgdef{fa@#1@transitions}{#3}%
  \global\csundef{fa@#1@initial}%
  \global\csundef{fa@#1@accepting}%
  \global\csundef{fa@#1@rejecting}%
  \def\fa@initial{initial}%
  \def\fa@accept{accepting}%
  \def\fa@reject{rejecting}%
  \foreach \fa@s/\fa@n/\fa@o in {#2}{%
    \foreach \fa@x in \fa@o {%
      \ifx\fa@initial\fa@x
        \ifcsdef{fa@#1@initial}{\fa@err{#1 has multiple initial states}}{}%
        \global\cslet{fa@#1@initial}\fa@s
      \fi
      \ifx\fa@accept\fa@x
        \ifcsdef{fa@#1@accept}{\fa@err{#1 has multiple accepting states}}{}%
        \global\cslet{fa@#1@accept}\fa@s
      \fi
      \ifx\fa@reject\fa@x
        \ifcsdef{fa@#1reject}{\fa@err{#1 has multiple rejecting states}}{}%
        \global\cslet{fa@#1@reject}\fa@s
      \fi
    }%
  }%
  \ifcsdef{fa@#1@initial}{}{\fa@err{#1 doesn't have an initial state}}%
  \ifcsdef{fa@#1@accept}{}{\fa@err{#1 doesn't have an accepting state}}%
  \ifcsdef{fa@#1@reject}{}{\csgdef{fa@#1@reject}{REJECT}}%
  \ifcsequal{fa@#1@accept}{fa@#1@reject}%
    {\fa@err{#1's accepting state is its rejecting state}}{}%
}

\newcommand\iftm@halted{%
  \ifdefequal{\tmstate}{\fa@accept}%
    {\@firstoftwo}%
    {%
      \ifdefequal{\tmstate}{\fa@reject}%
        {\@firstoftwo}%
        {%
          \ifnum\tmsteps=\fa@max@steps
            \expandafter\@firstoftwo
          \else
            \expandafter\@secondoftwo
          \fi
        }%
    }%
}%


\newcount\tmsteps

\newcommand*\tmrun[3][25]{%
  \begingroup
    \let~=\relax
    \global\mathchardef\fa@max@steps=#1\relax
    \global\letcs\fa@states{fa@#2@states}%
    \global\letcs\fa@trans{fa@#2@transitions}%
    \global\letcs\fa@accept{fa@#2@accept}%
    \global\letcs\fa@reject{fa@#2@reject}%
    \gdef\fa@left{}%
    \xdef\tmstate{\csuse{fa@#2@initial}}%
    \fa@split@tape\fa@sym\fa@right#3~\@nil
    \xdef\tmconfig{{}{\tmstate}{#3}}%
    \xdef\tmconfigs{\tmconfig}%
    \global\tmsteps=0
    \iftm@halted{}{\fa@tm@run}%
  \endgroup
}

\def\fa@tm@run{%
  \advance\tmsteps by1
  \global\fa@transitionedfalse
  \foreach \fa@q/\fa@ts/\fa@r/\fa@x/\fa@y in \fa@trans {%
    \ifx\fa@q\tmstate
      \foreach \fa@t in \fa@ts {%
        \expandafter\fa@tm@split@transition\fa@t X\@nil
        \ifx\fa@sym\fa@rsym
          \if\fa@dir L%
            \ifx\fa@left\@empty
              % At the left side, don't move
              \global\let\fa@sym\fa@wsym
            \else
              \xdef\fa@right{\fa@wsym\fa@right}%
              \expandafter\fa@split@tape\expandafter\fa@sym\expandafter\fa@left\fa@left\@nil
            \fi
          \else\if\fa@dir S%
            \global\let\fa@sym\fa@wsym
          \else % R
            \xdef\fa@left{\fa@wsym\fa@left}%
            \ifx\fa@right\@empty
              \gdef\fa@sym{~}%
            \else
              \expandafter\fa@split@tape\expandafter\fa@sym\expandafter\fa@right\fa@right\@nil
            \fi
          \fi\fi
          \global\fa@transitionedtrue
          \breakforeach
        \fi
      }%
      \iffa@transitioned
        \global\let\tmstate\fa@r
        \breakforeach
      \fi
    \fi
  }%
  \iffa@transitioned\else
    \global\let\tmstate\fa@reject
    \xdef\fa@left{\fa@sym\fa@left}%
    \ifx\fa@right\@empty
      \gdef\fa@sym{~}%
    \else
      \expandafter\fa@split@tape\expandafter\fa@sym\expandafter\fa@right\fa@right\@nil
    \fi
  \fi
  \xdef\tmconfig{{\expandafter\fa@reverse\fa@left\@nil\fa@stop}{\tmstate}{\fa@sym\fa@right}}%
  \xdef\tmconfigs{\tmconfigs,\tmconfig}%
  \iftm@halted{}{\fa@tm@run}%
}

\def\fa@split@tape#1#2#3#4\@nil{%
  \gdef#1{#3}%
  \gdef#2{#4}%
}%

\def\fa@tm@split@transition#1->#2#3#4\@nil{%
  \gdef\fa@rsym{#1}%
  \if#3X%
    % a->L or a->S or a->R
    \gdef\fa@wsym{#1}%
    \gdef\fa@dir{#2}%
  \else
    % a->bL or a->bS or a->bR
    \gdef\fa@wsym{#2}%
    \gdef\fa@dir{#3}%
  \fi
}

% \tmsplitconfig{\leftcs}{\statecs}{\rightcs}{config}
\newcommand*\tmsplitconfig[4]{%
  \begingroup
  \let~=\relax
  \edef\fa@temp{%
    \endgroup
    \noexpand\fa@tm@split@config{\noexpand#1}{\noexpand#2}{\noexpand#3}#4%
  }%
  \fa@temp
}%

\def\fa@stop{\fa@stop}
\def\fa@tm@split@config#1#2#3#4#5#6{%
  \def#1{#4}%
  \def#2{#5}%
  \def#3{#6}%
}

\def\fa@reverse#1#2\fa@stop{%
  \ifx#1\@nil
    \expandafter\@gobble
  \else
    \expandafter\@firstofone
  \fi
  {\fa@reverse#2\fa@stop#1}%
}

% \tmstatename[reject state]{\cs}{tm}{state}
\newcommand*\tmstatename[4][q_{\text{reject}}]{%
  \ifcsdef{fa@#3@states}{}{\fa@err{TM #3 not defined}}%
  \global\letcs\fa@states{fa@#3@states}%
  \edef\fa@state{#4}%
  \global\let\fa@temp\relax
  \foreach \fa@s/\fa@n/\fa@o in \fa@states {%
    \ifx\fa@s\fa@state
      \expandafter\gdef\expandafter\fa@temp\expandafter{\fa@n}%
      \breakforeach
    \fi
  }%
  \ifx\fa@temp\relax
    \def#2{\ensuremath{#1}}%
  \else
    \expandafter\def\expandafter#2\expandafter{\expandafter\ensuremath\expandafter{\fa@temp}}%
  \fi
}

\providecommand\@secondofthree[3]{#2}

\newtoks\fa@toks
\newcommand*\tmdirfont{\normalfont}
\def\fa@tm@space{~}

% \tmhighlight[options]{tm}{configurations}
\newcommand*\tmhighlight[3][tm]{%
  \global\letcs\fa@states{fa@#2@states}%
  \global\letcs\fa@trans{fa@#2@transitions}%
  \begingroup
    \let~=\relax
    \xdef\fa@configs{#3}%
  \endgroup
  \begin{scope}[%
    /tikz/name/.append style={/tikz/alias={#2-##1}},%
    #1%
  ]%
  \foreach \fa@q/\fa@n/\fa@o in \fa@states {%
    \gdef\fa@hl{}%
    \foreach[count=\fa@c] \fa@config in \fa@configs {%
      \edef\fa@state{\expandafter\@secondofthree\fa@config}%
      \ifx\fa@q\fa@state
        \ifdefempty{\fa@hl}%
          {\xdef\fa@hl{\fa@c}}%
          {\xappto\fa@hl{,\fa@c}}%
      \fi
    }%
    \toks0=\expandafter{\fa@o}%
    \toks2=\expandafter{\fa@n}%
    \edef\fa@temp{\noexpand\node[state\ifdefempty{\fa@hl}{}{,highlight={\fa@hl}},\the\toks0](\fa@q){\noexpand\ensuremath{\the\toks2}}}%
    \fa@temp;%
  }%
  \foreach \fa@q/\fa@ts/\fa@r/\fa@x/\fa@y in \fa@trans {%
    \toks0=\expandafter{\fa@x}%
    \toks2=\expandafter{\fa@y}%
    \global\fa@toks={}%
    \global\fa@transitionedfalse
    \foreach \fa@t in \fa@ts {%
      \expandafter\fa@tm@split@transition\fa@t X\@nil
      \ifx\fa@rsym\fa@tm@space
        \def\fa@rsym{\visiblespace}%
      \fi
      \ifx\fa@wsym\fa@tm@space
        \def\fa@wsym{\visiblespace}%
      \fi
      \edef\fa@temp{\fa@rsym$\noexpand\to$\ifx\fa@rsym\fa@wsym\else\fa@wsym,\fi{\noexpand\tmdirfont\fa@dir}}%
      \iffa@transitioned
        \toks4=\expandafter{\fa@temp}%
        \edef\fa@temp{\the\fa@toks\noexpand\\\the\toks4}%
      \else
        \global\fa@transitionedtrue
      \fi
      \global\fa@toks=\expandafter{\fa@temp}%
    }%
    \edef\fa@temp{\noexpand\path(\fa@q)edge[\the\toks0]node[align=left,\the\toks2]{\the\fa@toks} (\fa@r)}%
    \fa@temp;%
  }%
  \end{scope}%
}

\newcommand*\tmdraw[2][tm]{%
  \tmhighlight[#1]{#2}{}%
}

\newcommand*\tmhighlighttape[2][]{%
  \begingroup
    \let~=\relax
    \xdef\fa@configs{#2}%
  \endgroup
  \begin{scope}[%
    start chain=tape,%
    node distance=0pt,%
    every node/.style={inner sep=0pt,minimum size=1em},%
    font=\ttfamily,%
    #1]%
    \foreach [count=\fa@i] \fa@config in \fa@configs {%
      \expandafter\only\expandafter<\number\fa@i>{%
        \tmsplitconfig{\fa@left}{\fa@state}{\fa@right}{\fa@config}%
        \tmsteps=0
        \expandafter\fa@tm@add@tape@cells\fa@left\fa@stop
        \count@=\tmsteps
        \expandafter\fa@tm@add@tape@cells\fa@right\fa@stop
        \loop\ifnum\tmsteps<\fa@tapecells\relax
          \node[on chain]{\strut};
          \ifnum\tmsteps>0
            \draw (tape-end.south west) -- (tape-end.north west);
          \fi
          \advance\tmsteps by1
        \repeat
        \draw (tape-begin.south west) rectangle (tape-end.north east);
        \advance\count@ by1
        \draw[thick,red,<-,shorten <=1pt](tape-\the\count@) -- +(0,-2em);
        \breakforeach
      }%
    }%
  \end{scope}%
}

\def\fa@tm@add@tape@cells#1{%
  \ifx#1\fa@stop\else
    \advance\tmsteps by1
    \node[on chain]{\strut#1};%
    \ifnum\tmsteps>0
      \draw (tape-end.south west) -- (tape-end.north west);
    \fi
    \expandafter\fa@tm@add@tape@cells
  \fi
}

\iffalse
% XXX: We should be able to use this to speed up TM drawing by selecting the
% configuration to draw and just drawing that.
\def\fa@tm@select@config#1{%
  \count@=#1\relax
  \advance\count@ by-1
  \expandafter\fa@tm@select@config@A\fa@configs,,,,,,,,,\fa@stop
}

\def\fa@tm@select@config@A#1,#2,#3,#4,#5,#6,#7,#8,#9,{%
  \ifnum\count@<9
    \ifcase\count@ \def\fa@config{#1}%
    \or \gdef\fa@config{#2}%
    \or \gdef\fa@config{#3}%
    \or \gdef\fa@config{#4}%
    \or \gdef\fa@config{#5}%
    \or \gdef\fa@config{#6}%
    \or \gdef\fa@config{#7}%
    \or \gdef\fa@config{#8}%
    \or \gdef\fa@config{#9}%
    \fi
    \expandafter\fa@tm@select@config@B
  \else
    \advance\count@ by-9
    \ifx\relax#9\relax
      \fa@err{Requested configuration number larger than number of
        configurations}%
    \fi
    \expandafter\fa@tm@select@config@A
  \fi
}

\def\fa@tm@select@config@B#1\fa@stop{%
  \ifx\fa@config\@empty
    \fa@err{Requested configuration number larger than number of
      configurations}%
  \fi
}
\fi

\endinput

% vim: set shiftwidth=2 softtabstop=2 tabstop=8 expandtab: