fmcross

Name

fmcross -- compute the cross product of two machines

Synopsis

fmcross fm1 fm2

fmcross fm2 <fm1

Description

fmcross computes the cross product of the machines fm1 and fm2, writing the result machine on the standard output. Both machines may be specified on the command line, or one may be read from standard input. fm2 can, if desired, be the same file as fm1.

The result is not guaranteed to have a final state unless fm2 is the same as fm1. Furthermore, the generated machine is not guaranteed to be complete, connected, minimal, or deterministic.

If two machines are not specified, fmcross returns 0. fm1 and fm2 must conform to the Grail format for machines.

The cross product contains a instruction of the form: .ce $ ( ( x sub fm1 , x sub fm2 ) , ~ label, ~ ( y sub fa1 , y sub fa2 ) ) $

for each pair of instructions in the input machines of the form .ce $ (x sub fm1 , ~ label, ~ y sub fa1 ) ~ member ~ fa1 $ .ce $ (x sub fm2 , ~ label, ~ y sub fa2 ) ~ member ~ fa2 $

The state numbers in the output machines are computed from the input state numbers as follows: $ s sub o~ = ~ s sub fm1 ~ + ~ ( ( max + 1) * s sub fm2 ) $

where $s sub o$ is the output state number, $ s sub fm2$ is the state number of fm2, and $max$ is the maximum state number of fm1. Since the output state numbers have a unique factorization in terms of input state numbers, it is possible to determine from the output state which pair of input states it represents.

Computing the cross product of two finite-state machines generates their intersection; if the input machines are equivalent, then the result is the same as the input. Computing the cross product of a nondeterministic machine with itself produces a result that accepts the same language, but is substantially larger. Recursive application of cross product results in an exponential growth in the size of the machine. Thus one can generate large nondeterministic machines with a known language; this may be useful for testing other filters.

Examples

This example computes the cross product of a simple nfm with itself:

% cat nfm
(START) |- 0
0 a 1
0 a 2
1 -| (FINAL)
2 -| (FINAL)

% fmcross nfm nfm
(START) |- 0
0 a 4
0 a 7
0 a 5
0 a 8
4 -| (FINAL)
7 -| (FINAL)
5 -| (FINAL)
8 -| (FINAL)

This example computes the cross product of two fms which have the property that $ L sub 1 $ in $ L sub 2 $:

% cat dfm1
(START) |- 0
0 a 1
1 b 2
2 c 3
3 -| (FINAL)

% cat dfm2
(START) |- 0
0 a 0
0 b 1
1 c 1
1 -| (FINAL)

% fmcross dfm1 dfm2
(START) |- 0
0 a 1
1 b 6
6 c 7
7 -| (FINAL)

This example shows the exponential increase in the size of cross product results, using wc to compute the size of the machine file):

$ for i in 1 2 3 4
> do
> 	fmcross nfm nfm >tmp
> 	mv tmp nfm
> 	wc nfm
> done
       9      27      97 nfm
      33      99     381 nfm
     513    1539    6925 nfm
  131073  393219 2293773 nfm
$

Authors