We extend the technique developed in [E. Bayraktar, A Proof of the Smoothness of the Finite Time Horizon American Put Option for Jump Diffusion, http://arxiv.org/abs/math/0703782, 2007] to a class of finite time horizonal optimal stopping problems under regime switching models which includes the pricing of American put options. The construction involved also leads to a computational procedure for the solutions of such optimal stopping problems.