(a) Assume there are only four tags: JJ, VB, MD, and NN.

Apply the Viterbi algorithm to derive the optimal tag of the sentence:

S Janet want.

(b) How many probabilities you calculate to derive the final results? Can you generalize your results and derive the complexity of the Viterbi algorithm?

2. (20 points) Based on the transition probability P(titi1) in Figure 1 and the emission probability P(witi) in Figure 2, Figure 1: The transition probability P(titi1). The first column shows the previous tag ti1, and the first ow shows the current tag ti. Figure 2: The emission probability P(witi)