An introduction to XFST and finite state automata. (Part 1)
XFST is the Xerox Finite-State Tool, a command-line utility for performing simple finite-state operations and implementing simple finite-state networks in the form of a stack.
We can use XFST to represent morphological structures and relations and perform operations on them such as
This is going to be a short blog series detailing how to use XFST to model simple morphologies by creating finite-state transducers.
Downloading / Extracting
In order to download and use XFST you must first download the pre-compiled binaries for Windows, which you can do here.
You will need to accept the license before you are able to proceed to download. You only want the binaries and as such, you should select the top-right download link, which
correponds to the pre-compiled binaries for Windows. While this is downloading, which shouldn’t take more than a few seconds you will need to ensure you have some program installed
which can open gzipped tarballs (
.tar.gz) Popular options include 7-zip (my recommendation) or WinRar (priorietary garbage/freeware)
For those running Linux the instructions are mostly the same as outlined above. Download the Linux binaries from here. for your architecture. Once you’ve done that navigate to your downloads folder:
$ cd ~/Downloads
Having done that proceed to extract the contents
$ tar -xf ./bin.tar.gz
(Suggested) now move the extracted binaries to either
/usr/bin or your own home bin
~/bin and symbolic link them as follows:
# ln -s /home/%USER%/bin/* /usr/bin
Now you should be greeted with the xfst prompt when you type
As /usr/bin is in
You’re on your own, sorry – I’m unfamiliar with the operating system, however, if someone feels like writing up instructions for MacOS I would greatly appreciate it – Email any such instructions to [email protected] in Markdown format.
XFST is entirely used through the command line. There is no GUI available, this might be new to some, particularly the windows users who rarely venture into the deep depths of
cmd.exe or powershell.
xfst into your command prompt, if you have it installed you should be greeted with the following prompt:
Copyright © Palo Alto Research Center 2001-2021 PARC Finite-State Tool, version 2.15.7 (libcfsm-2.25.11) (svn 34269) Type "help" to list all commands available or "help help" for further help. xfst:
The last line is a prompt for you to input a command, and the
 indicates how many entires into the stack there is, by default 0 – It has no input.
Finite state automata
FSA or Finite State Machines underly the purpose of XFST. We will be using XFST to perform morphological analysis of a particular language, however it can be used to represent any finite-state machine you can dream of. It was developed by Xerox to model grammars however we’re still using it 20 years later. There are open source and proprietary alternatives to XFST such as lexc and you’ll find a lot of crossover between the two, in terms of syntax anyway.
Now that we have XFST Setup we can begin to form basic FSTs, which will be covered in the next part!