Finite-State Funhouse

Welcome to the Finite-State Funhouse, a small collection of amusing finite-state machine examples that have been implemented in Xerox Finite-State Tools (XFST). You need to have XFST installed in order to try them. Enjoy!

ELIZA
Lingo
The World's Fastest Haiku Generator!

ELIZA

ELIZA (Weizenbaum 1966) is a computer program simulating a (rogerian) psycho-therapist. The program is a 'classical' program in the area of Artificial Intelligence, with many followers (Emacs users: run the command "Meta-x doctor" to meet with one of them!).

The following regular expressions compile into a finite-state transducer implementing a Swedish speaking version of ELIZA:

define Delimiter [" "|.#.|"."|"?"] ;

regex jag -> du, du -> jag || Delimiter _ Delimiter;

regex dig -> mig, mig -> dig || Delimiter _ Delimiter;

regex $[mamma|pappa] @-> "Kan du berätta mer om din familj?";

turn stack
compose net
apply down

Note the use of parallel- and longest-match replacement. The resulting machine behaves as follows:

xfst[1]: apply down
apply down> hej
hej
apply down> jag längtar efter min mamma
Kan du berätta mer om din familj?
apply down> varför frågar du mig?
varför frågar jag dig?
apply down> jag tycker du är dum
du tycker jag är dum
apply down>

Constructed by Torbjörn Lager

Lingo

In a game of Lingo, there is a hidden word, five characters long. The object of the game is to find this word by guessing, and in return receive two kinds of information: 1) the characters that are fully correct, with respect to identity as well as to position, and 2) the characters that are indeed present in the word, but which are placed in the wrong position.

A machine with which one can play Lingo can easily be constructed in XFST. Square brackets are used to mark characters correct in the sense of 1), and ordinary parantheses to mark characters correct in the sense of 2).

Assuming, for example, that the machine conceals the word "tiger", you may interact with it in the following way:

xfst[1]: apply down
apply down> snake
snak(e)
apply down> fiest
f[i](e)s(t)
apply down> times
[t][i]m[e]s
apply down> tiger
[t][i][g][e][r]
apply down>

Here's an XFST script accomplishing this:

read regex
        t -> %[ ... %] || _ ? ? ? ? ,,
        i -> %[ ... %] || ? _ ? ? ? ,,
        g -> %[ ... %] || ? ? _ ? ? ,,
        e -> %[ ... %] || ? ? ? _ ? ,,
        r -> %[ ... %] || ? ? ? ? _ ;
define CorrectChar

define CorrectPos [t|i|g|e|r] -> "(" ... ")" || [.#.|\"["] _ [\"]"|.#.];

regex CorrectChar .o. CorrectPos;

apply down

Constructed by Natalia Zinovjeva and Torbjörn Lager

The World's Fastest Haiku Generator!

Haiku is a Japanese form of poetry which in its classical form consists of seventeen syllables. In English haiku poems, these are distributed over three lines (for more about the relation between English and Japanese haikus, see here):

    Five syllables
    Seven syllables
    Five syllables

Syntactically, it may look as follows (although many other variants are possible):

    Prep Det A N
    Det A N Part Vsg3
    Mod Adv

Here's a concrete example:

    Behind hope's dead goose
    Joe's eager baboon still snorts
    seemingly slowly

define Tag [%+DET|%+N|%+V|%+A|%+Ving|%+Vsg3|%+ADV|%+MOD|%+PREP|%+PART|%@|%@ %@|%@ %@ %@];

define SP " " ;

define Syll %@+;

define Words [[Word SP]+ "\n"]+;

define Det [? %+DET Syll SP] ;
define N [? %+N Syll SP] ;
define V [? %+V Syll SP] ;
define A [? %+A Syll SP] ;
define Ving [? %+Ving Syll SP] ;
define Vsg3 [? %+Vsg3 Syll SP] ;
define ADV [? %+ADV Syll SP] ;
define PART [? %+PART Syll SP] ;
define PREP [? %+PREP Syll SP] ;
define MOD [? %+MOD Syll SP] ;

define FiveSyllLine [?* %@ ?* %@ ?* %@ ?* %@ ?* %@ ?*] ;

define SevenSyllLine [?* %@ ?* %@ ?* %@ ?* %@ ?* %@ ?* %@ ?* %@ ?*] ;

define Phrase1 [PREP Det A N];

define Phrase2 [Det A N PART Vsg3];

define Phrase3 [MOD ADV];

define Line1 FiveSyllLine & Phrase1;

define Line2 SevenSyllLine & Phrase2;

define Line3 FiveSyllLine & Phrase3;

define Haiku [Line1 "\n" Line2 "\n" Line3 "\n"] ;

define FilterTags Tag -> [];

regex [Words & Haiku] .o. FilterTags ;

Constructed by Torbjörn Lager