2017 · open round · F · 10 points

Transition(al) Numbers

Harold Somers · morphology · number systems · formal and computational

The following diagram represents a “transition network” (also known as a “finite state automaton”). The circles represent “states” while the boxes represent letter sequence that can be “generated” from any given state, as indicated by the lines (the “transitions”). The aim is to start at “S” and get to the end state “0”. For some boxes there is a choice of transition. The lines are directional (it would have been even more messy to add the arrowheads), so note that you can only enter a state from the front (left). So you can go from “ty” to “S”, but not the other direction.

Transition network with a start state S on the left, an end state 0 on the right, and states 1 and 2 in the middle. Boxes between them are labelled one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thir, fif, twen, for, plus a box teen leading out of state 1 and a box ty leading out of state 2.

The above diagram is already quite messy, and it can be represented more neatly by a set of rules as on the next page. Each rule is identified (in square brackets) but this is ONLY for ease of reference in answering the questions. Apart from that, each rule consists of a state (the symbol before the “:”), a text string, and then, after the arrow (“->”), a list of states to which you can then move. Starting at position “S”, you generate the text indicated, and then continue to any ONE of the states listed after the arrow. State “0” is a special case meaning “finish”.

[a]	S: one -> 0
[b]	S: two -> 0
[c]	S: three -> 0
[d]	S: four -> 0,1
[e]	S: five -> 0
[f]	S: six -> 0,1,2
[g]	S: seven -> 0,1,2
[h]	S: eight -> 0,1,2
[i]	S: nine -> 0,1,2
[j]	S: ten -> 0
[k]	S: eleven -> 0
[l]	S: twelve -> 0
[m]	S: thir -> 1,2
[n]	S: fif -> 1,2
[o]	S: twen -> 2
[p]	S: for -> 2
[q]	1: teen -> 0
[r]	2: ty -> S,0

So for example, we can generate “fourteen” by taking rule [d] then rule [q]. We cannot generate “twelveteen” because rule [l] only allows one way to progress, namely to finish.

Answer the following questions in the Answer Sheets.

TimerminutesOptional. Set whatever limit suits you.

Questions

0 of 12 correct

Write out the sequence of rules and states followed to generate the following words. For example, for "fourteen," you would write "d 1 q 0".

a. sixteen

b. ninetythree

c. twentyeight

d. fifteen

The network above "overgenerates", that is, it allows us to create words which are not valid numbers. For each of the following words, write Y if the word can be generated by the network, or write N if the word cannot be generated by the network.

a. oneten

b. fiftytwelve

c. sixteensix

d. twentyfourteen

e. fortythirty

f. eleventythree

g. fivety

The above network currently generates a misspelling in the case of "eighteen" as well as any number beginning with "eighty." This can be fixed by removing rule [h] and replacing it with two new rules (both of which will be similar to rule [h]). Write the two new rules that need to replace rule [h]. NOTE: For full points, make sure that the modified network still generates "eight" without misspelling it.

Write the two new rules that replace rule [h].

Explanation

Try the questions first. Use the Hint button next to any part if you need a nudge.

Reading the explanation costs no XP. Worth 10 points in the real exam.