Starting xfst   

gawron@localhost gawron]$ cd xfst
[gawron@localhost xfst]$ xfst
bash: xfst: command not found
[gawron@localhost xfst]$ ./xfst
Copyright ? Xerox Corporation 1997-2004
Xerox Finite-State Tool, version 8.1.4
 
Type "help" to list all commands available or "help help" for further help.
 
xfst[0]: read regex < kaNpat.regex
kaNpat
file 		  Here's what's in kaNpat.regex: 
[ N -> m || _ p ]
.o.
[ p -> m || m _ ];
For the command used ("read regex"), the file must exactly ONE reg exp, endinh in a ";" and a newline.

Whew.

Using
kaNpat.regex 		  

xfst[3]: down N
N
xfst[3]: down Np
mm
xfst[3]: down kaNpat
kammat
xfst[3]: up kammat
kaNpat
kampat
kammat
xfst[3]: down kampat
kammat
xfst[3]: down kammat
kammat
Reordering
Rules		  

The file kaNpat-rev.regex: 

[ p -> m || m _ ]
.o.
[ N -> m || _ p ];


xfst[4]: read regex < kaNpat-rev.regex;
Opening file kaNpat-rev.regex...
356 bytes. 4 states, 15 arcs, Circular.
Closing file kaNpat-rev.regex...
xfst[5]:

What happens now?

  1. down kaNpat
  2. down kampat
  3. up kammat
  4. up kampat
  5. Why isn't "kampat" part of the answer to the previous question?
Parallel
Rules 		 

Consider the following version of the kanpat rules in the file kaNpat-par.regex: 

[ N -> m || _ p ,,
 [ p -> m || m _ ]];
This applies the rules in parallel. Note the double comma (",,"), required only for parallel rules with contexts.

What wiull happen now? 

xfst[2]: down N
N
xfst[2]: down Np
mp
xfst[2]: down kaNpat
kampat
xfst[2]: up kammat
kampat
kammat
xfst[2]: up kampat
kaNpat
xfst[2]: down kampat
kammat
xfst[2]: down kammat
kammat
xfst[2]:
Ponder these.

Note that the result do differ from EITHER of thetwo previus versions.

Loops and
parallelism 		 

Consider the following language: 

[ a -> b , b -> a ];

This turns a's into b's and b's into a's: 

xfst[2]: read regex [ a -> b , b -> a ];
156 bytes. 1 state, 3 arcs, Circular.
xfst[3]: up abba
baab
xfst[3]: up bbbbba
aaaaab
xfst[3]: up bababa
ababab
xfst[3]:


Note that NEITHER way of orderthe rule gets this result:
xfst[3]: read regex [ a -> b ] .o. [ b -> a ];
156 bytes. 1 state, 3 arcs, Circular.
xfst[4]: up abba
xfst[4]: up a
a
b
xfst[4]: up b
xfst[4]: down abba
aaaa
xfst[4]: down baab
aaaa
xfst[4]: up abba
xfst[4]: up baab
xfst[4]: up bb
And similarly: 
xfst[0]: read regex [ b -> a ] .o. [ a -> b ];
156 bytes. 1 state, 3 arcs, Circular.
xfst[1]: up abba
xfst[1]: up a
xfst[1]: up b
b
a
xfst[1]: down a
b
xfst[1]: down b
b
xfst[1]: down ab
bb
xfst[1]: down abbbba
bbbbbb
xfst[1]: down bbbaaabbb
bbbbbbbbb
xfst[1]: down aaa
bbb
xfst[1]: down bbb
bbb

So there are things you can't do with rule ordering

Now think about this. Is this right semantics for these rules? Should they feed themselves instead? Get an infinite loop?

What happens in THIS case? 

read regex [ a -> b || x _ ,, a -> c || _ y ];
. In particular, consider what happens for the following input: 
xay
What should happen? Should the world explode? In a rule ordering system it's clear what would happen. The rule that came first would win, destroying the environment for the other rule. What should happen here?

Here's what happens: 

xfst[1]: read regex [ a -> b || x _ ,, a -> c || _ y ];
492 bytes. 4 states, 21 arcs, Circular.
xfst[2]: down xa
xb
xfst[2]: down ay
cy
xfst[2]: down xay
xby
xcy
Moral: We are defining relations.