FAQ: Self-referencial expressions in xfst

Q: xfst treats an identifier like Z or Foo as a variable if and only if it was previously 'define'd to have a value; otherwise it treats Z has a simple symbol and Foo as a multichar symbol. What does it do with self-referencial expressions like the following?

xfst[]: define Z  0 | a Z ;
xfst[]: define Foo  0 | Foo b ;

A: Yes, the problem is that in an expression like define Foo 0 | Foo b ; there is a question, in the xfst design, of how to handle the Foo on the right-hand side. Is it a self reference or just a multichar symbol?

This is resolved somewhat awkwardly in xfst with an interface variable, 'recursive-define', that can be (re)set as needed by the user. 'recursive-define' is OFF by default, so the example

xfst[0]: show recursive-define
variable recursive-define = OFF
xfst[0]: define Z 0 | Z b ;
defined Z: 144 bytes. 3 states, 2 arcs, 2 paths.
xfst[0]: push Z
xfst[1]: sigma
Z b
Size: 2
xfst[1]:

shows clearly that the resulting network contains the symbol Z in the sigma alphabet. Now let's change the value of the interface variable and try again.

xfst[1]: undefine ALL
xfst[1]: set recursive-define ON
variable recursive-define = ON
xfst[1]: define Z 0 | Z b ;
defined Z: 100 bytes. 1 state, 1 arc, Circular.
xfst[1]: push Z
xfst[2]: sigma
b
Size: 1
xfst[2]: print net
Sigma: b
Size: 1
Net:
Flags: deterministic, pruned, minimized, epsilon_free
Arity: 1
fs0: b -> fs0.

You will recognize that with recursive definition, define Z 0 | Z b ; should be equivalent to define Z b*;, which can easily be tested:

xfst[2]: up b
b
xfst[2]: up bb
bb
xfst[2]: up bbb
bbb
xfst[2]: up bbbb
bbbb


Last Modified:Sunday, 07-Mar-2004 22:43:35 PST