The String Matching Automaton of a string x is the minimal deterministic automaton accepting the language Σ*x when the string x is build on the alphabet Σ.
Below are three standalone easy-to-use C files that produce a LaTeX source file showing the String Matching Automaton of an input string x using Beamer and tikz.
This is for pedagogical purpose thus the length of x should not exceed 9.
The letters should all be within a and z. The first letter of the alphabet is always a. The alphabet size is determined by using the largest letter of x.
Example: if x=aca then Σ={a, b, c}.Once compiled, the C files produce a file named x.tex that can be compile using pdflatex to produce x.pdf.
You can modify the C files or modify the produced LaTeX files.The first version sma1.c produces only one slide with the final String Matching Automaton of the input string.
Here is an example.
Example of use:gcc sma1.c -o sma1 sma1 abaababa pdflatex abaababa acroread abaababa.pdf
The second version sma2.c produces one slide for each of the intermediate automata.
Here is an example.
Example of use:gcc sma2.c -o sma2 sma2 abaababa pdflatex abaababa acroread abaababa.pdf
The third version sma3.c produces one slide for each of the intermediate automata with an animation.
It requires the packages
animate.sty
and
fp.sty.
Warning: The LaTeX compilation could be quite long.
Warning: A version of Acrobat Reader 6.0 or higher is required to view the animation.
Here is an example.
Example of use:gcc sma3.c -o sma3 sma3 abaababa pdflatex abaababa acroread abaababa.pdf
Please cite
Related work: is a given graph a String Matching Automaton?
See:
J.-P. Duval, T. Lecroq and A. Lefebvre