Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Finite automata and (deterministic) Turing machine running/drawing.
\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:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment