>>35
出力ってのがよくわからんけど、入力を受け取って遷移した先の状態に出力が対応するのかな。

(1)
Σ={00,01,10,11},Q={q00,q01,q10,q11}とし初期状態をq00とする。遷移関数δ:Q×Σ→Qを
δ(qij,kl)=qmn (i...nは0か1)
i+k+lの2進表示(2桁)の上位bitをm、下位bitをnとし、出力をnとすればいい。
出力を状態に含む必要がないなら状態は2個でいい

(2)
アイデアだけ。
2進表示で1桁ずつ出力することから繰り上がりを記憶する必要があるが
任意桁の乗算では繰り上がりの数は幾らでも大きくなるため有限状態で表わせない。