# 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

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

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

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