Assuming we know all the possibilities, W i , of tagging each of the words w i of the input sentence, the search space of the problem can be defined by the set W 1 ×W 2 ×• • •×W m .
the solution can be found by searching the problem state space.