HFST: Plus or Minus

NOTE: The solution does not work at the moment, because rules are not yet implemented in hfst-regexp2fst

We examplify the use of HFST command line tools with an example taken from Beesley & Karttunen that creates a set of adding/subtracting transducers for non-negative integers with no leading zeros. $FORMAT is the implementation type of the transducer. The solution given on this page can also be executed with a single script.

echo "[1|2|3|4|5|6|7|8|9]" | hfst-regexp2fst -f $FORMAT > N
echo '["0" | N]' | hfst-regexp2fst -f $FORMAT > Z

Insert an initial 1 in front of a sequence of zeros. To make this relation functional in both directions, we need two replace expressions. One introduces 1, the other removes 1. The composition of the two is a relation that uniquely maps, for example, 100 to 99 and, conversely, 99 to 100.

echo '[ 1 <- [. .] || .#. _ "0"+ .#. ]' | hfst-regexp2fst -f $FORMAT > TMP;
echo '[ 1 ->   0   || .#. _ "0"+ .#. ]' | hfst-regexp2fst -f $FORMAT | hfst-compose -1 TMP > CarryUp.hfst

echo '[1 <- "0", 2 <- 1, 3 <- 2, 4 <- 3,  5  <- 4,' \
     '6 <-  5 , 7 <- 6, 8 <- 7, 9 <- 8, "0" <- 9' \
     '|| .#. ("+") @"Z"* _ 9* .#.]' | hfst-regexp2fst -f $FORMAT > AddUp.hfst

echo '[ "0" => .#. @"N" @"Z"* _ , .#. _ .#. ]' | hfst-rule2fst -f $FORMAT > NoLeadingZero.hfst

PlusMinusOne.hfst maps any natural number N to (N-1), and vice versa.

hfst-compose CarryUp.hfst AddUp.hfst | hfst-compose -2 NoLeadingZero.hfst > PlusMinusOne.hfst
hfst-compose PlusMinusOne.hfst PlusMinusOne.hfst > PlusMinusTwo.hfst
hfst-compose PlusMinusTwo PlusMinusOne > PlusMinusThree.hfst
hfst-compose PlusMinusThree PlusMinusOne > PlusMinusFour.hfst
hfst-compose PlusMinusFour PlusMinusOne > PlusMinusFive.hfst
hfst-compose PlusMinusFive PlusMinusOne > PlusMinusSix.hfst
hfst-compose PlusMinusSix PlusMinusOne > PlusMinusSeven.hfst
hfst-compose PlusMinusSeven PlusMinusOne > PlusMinusEight.hfst
hfst-compose PlusMinusEight PlusMinusOne > PlusMinusNine.hfst
hfst-compose PlusMinusNine PlusMinusOne > PlusMinusTen.hfst


-- ErikAxelson - 2011-09-12