#### Quesion 1

(a)假设法语单词的数量为$|F|$

• 初始化$p=1$
• $\text{for }j=1,\ldots,m:$
• $p=\max_{f_j,a_j} p\times t\left(f_{j} | e_{a_{j}}\right) \times q\left(a_{j} | j, l, m\right)$
• $f_j,a_j=\arg\max_{f_j,a_j} p\times t\left(f_{j} | e_{a_{j}}\right) \times q\left(a_{j} | j, l, m\right)$
• $\text{return } p,f_j,a_j,j=1,\ldots,m$

(b)注意恒等式

• $\text{for }j=1,\ldots,m:$
• $f_j =\arg \max_{f_j} \sum_{a_{j}=0}^{l} t\left(f_{j} | e_{a_{j}}\right) q\left(a_{j} | j, l, m\right)$

(c)注意到

#### Question 2

• 初始化$p(j,f,a)=1,\text{for }a=0,\ldots, l, j=0,\ldots, m,f\in F$
• $\text{for }j=1,\ldots,m:$
• $\text{for }a=0,\ldots, l, f\in F:$
• $p(j,f, a)=\max_{f’,a’} p(j-1, f’,a’)\times t\left(f| e_{a}\right) \times q\left(a |a’, j, l, m\right)$
• $bp(j,f,a)=\arg \max_{f’,a’} p(j-1, f’,a’)\times t\left(f| e_{a}\right) \times q\left(a |a’, j, l, m\right)$
• $f_m,a_m= \arg\max_{f,a} p(m, f,a)$
• $\text{for } j=m-1,\ldots,1:$
• $f_j,a_j= bp(j, f_{j+1},a_{j+1})$

#### Question 3

• $\text{for }l=1,\ldots,N-1:$

• $\text{for }i=1,\ldots, N-l:$

• 令$j=i+l$

• 计算

• 返回$\pi(1,N,x)$

Q4代码