PROBLEM $2$: Part$-$of$-$speech$-$tagging $(50$ points$)$

Use the Viterbi algorithm to assign POS tags to the following two sentences:

S $1$ : The chairman of the board is completely bold.

S$2$: A chair was found in the middle of the road.

Use the following tag transition probability table A and observation likelihood array B$.$ Both tables use the Penn Treebank POS tags.

$\backslash ($ A$=\backslash )$

$\backslash$begin$\{$tabular$\}\{|$l$|$c$|$c$|$c$|$c$|$c$|$c$|$c$|$c$|$c$|\}$

$\backslash$hline & DT & NN & VB & VBZ & VBN & JJ & RB & IN & $\backslash (\backslash$langle$/\backslash$mathrm$\{$s$\}\backslash$rangle $\backslash )\backslash \backslash$

$\backslash$hline$\backslash (\backslash$langle $\backslash )$ S $\backslash (>\backslash )$ & $0\mathrm{.}38$ & $0\mathrm{.}32$ & $0\mathrm{.}04$ & $0$ & $0$ & $0\mathrm{.}11$ & $0\mathrm{.}01$ & $0\mathrm{.}14$ & $0\backslash \backslash$

$\backslash$hline DT & $0$ & $0\mathrm{.}58$ & $0$ & $0$ & $0$ & $0\mathrm{.}42$ & $0$ & $0$ & $0\backslash \backslash$

$\backslash$hline NN & $0$ & $0\mathrm{.}07$ & $0$ & $0\mathrm{.}05$ & $0\mathrm{.}32$ & $0$ & $0$ & $0\mathrm{.}25$ & $0\mathrm{.}11\backslash \backslash$

$\backslash$hline VB & $0\mathrm{.}07$ & $0\mathrm{.}08$ & $0$ & $0$ & $0$ & $0$ & $0\mathrm{.}2$ & $0\mathrm{.}61$ & $0\mathrm{.}13\backslash \backslash$

$\backslash$hline VBZ & $0\mathrm{.}2$ & $0\mathrm{.}3$ & $0$ & $0$ & $0$ & $0\mathrm{.}24$ & $0\mathrm{.}15$ & $0\mathrm{.}11$ & $0\backslash \backslash$

$\backslash$hline VBN & $0\mathrm{.}18$ & $0\mathrm{.}22$ & $0$ & $0$ & $0\mathrm{.}2$ & $0\mathrm{.}07$ & $0\mathrm{.}16$ & $0\mathrm{.}11$ & $0\mathrm{.}06\backslash \backslash$

$\backslash$hline JJ & $0$ & $0\mathrm{.}88$ & $0$ & $0$ & $0$ & $0\mathrm{.}12$ & $0$ & $0$ & $0\backslash \backslash$

$\backslash$hline RB & $0$ & $0$ & $0$ & $0\mathrm{.}22$ & $0\mathrm{.}28$ & $0\mathrm{.}39$ & $0\mathrm{.}1$ & $0$ & $0\mathrm{.}01\backslash \backslash$

$\backslash$hline IN & $0\mathrm{.}57$ & $0\mathrm{.}28$ & $0$ & $0$ & $0$ & $0\mathrm{.}15$ & $0$ & $0$ & $0\backslash \backslash$

$\backslash$hline

$\backslash$end$\{$tabular$\}$

$1.$ Create the Hidden Markov Model $($HMM$)$ and show $($a$)$ the transition probabilities and $($b$)$ observation likelihoods in each state that will be reached by sentences S$1$ and S$2$ after $3$ time$-$steps. Present only the transition and observation likelihoods in the states reached after three steps.

$2.$ Create the Viterbi table for each sentence and populate it entirely.

$3.$ What is the probability of assigning the tag sequence for each of the sentences.?

$4.$ Execute the Stanford POS$-$tagger $($available from: