XFST: Homework assignment

Jurafsky & Martin rule extension

First some practice at understanding what compiled rules mean.

Do exercise 3.2. in Chapter 3 of J&M. Be careful when you do this. The problem is make sure that boss^es is still allowed, and boss^s is still blocked, and that brush^es& and church^es are allowed, and brush^s and church^s are blocked. Also be sure not to allow the rule to fire after hh. So hh^s should not become hh^es. This is not as trivial as it might seem at first.

More Numerals

Adapted from Lauri Karttunen’s 2005 XFST LSA Tutorial:

Continue the numeral script up to the point where you leave on the stack a network defined as UpToMillion containing all and only the numerals from one to nine hundred ninety-nine thousand nine hundred ninety-nine. Note that spaces are required between the components once we get beyond hundred.

You know that you have the right answer when you push the UpToMillion network onto the stack, enter the command print size and get the answer:

6.7 Kb. 187 states, 278 arcs, 999999 paths.

However, if you allow variants such as plain hundred in addition to one hundred and optional ands as in one hundred and five, the number of paths grows much larger. This is optional.

Cola Machine Enhancements

Extend the elegant definition of a cola machine used in your xfst intro. That looked like this:

xfst[0]: define ColaMachine [[D -> N^2, Q -> N^5] .o. N^5 ].u;
xfst[0]: push ColaMachine

Define alternative Cola Machines that have the following behavior

  1. Modify the above regular expression so that it compiles into a transducer that maps any sequence of coins whose value is exactly 25 cents into the multicharacter symbol COLA:

    apply down> DDQ
    ???
    apply down> DDD
    ???
    apply down> DDN
    COLA
    apply down> Q
    COLA
    apply down> DND
    COLA
    apply down> NDNN
    COLA
    
  2. Modify the transducer in (1) so that it makes change. It should return exactly one cola when the coins inserted are worth exactly 25 cents, plus it should return excess money as nickels. In addition if the coins inserted are worth less than 25 cents, it returns exactly the amount inserted. For example:

    apply down> DDQ
    COLANNNN
    apply down> DDD
    COLAN
    apply down> NNNN
    NNNN
    apply down> Q
    COLA
    apply down> QD
    COLANN
    apply down> NDNDN
    COLANN
    apply down> ND
    NNN
    
  3. Modify the transducer in (2) so that when it returns coins, it returns the minimal number of coins. Revising the examples above, we would have:

    apply down> DDQ
    COLADD
    apply down> DDD
    COLAN
    apply down> NNNN
    DD
    apply down> Q
    COLA
    apply down> QD
    COLAD
    apply down> NDNDN
    COLAD
    apply down> DN
    DN