String Matching Automaton



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

Algorithms on Strings
Algorithms on strings
M. Crochemore, C. Hancart and T. Lecroq
Cambridge University Press


Related work: is a given graph a String Matching Automaton?

See:

J.-P. Duval, T. Lecroq and A. Lefebvre

Efficient validation and construction of border arrays and validation of string matching automata

RAIRO-Theoretical Informatics and Applications 43(2) (2009) 281-297.

Thierry Lecroq
Home Page

vi power