Let's tag the sentence Janet will back the bill; the goal is the correct series of tags (see also Fig. 8.11 Let the HMM be defined by the two tables in Fig. 8 .12 and Fig. 8 .13. Figure 8 .12 lists the a i j probabilities for transitioning between the hidden states (part-of-speech tags). Figure 8 .13 expresses the b i (o t ) probabilities, the observation likelihoods of words given tags. This table is (slightly simplified) from counts in the WSJ corpus. So the word Janet only appears as an NNP, back has 4 possible parts of speech, and the word the can appear as a determiner or as an NNP (in titles like "Somewhere Over the Rainbow" all words are tagged as NNP). Figure 8 .14 The first few entries in the individual state columns for the Viterbi algorithm. Each cell keeps the probability of the best path so far and a pointer to the previous cell along that path. We have only filled out columns 1 and 2; to avoid clutter most cells with value 0 are left empty. The rest is left as an exercise for the reader. After the cells are filled in, backtracing from the end state, we should be able to reconstruct the correct state sequence NNP MD VB DT NN. Figure 8 .14 shows a fleshed-out version of the sketch we saw in Fig. 8 .11, the Viterbi lattice for computing the best hidden state sequence for the observation sequence Janet will back the bill.