P52

Book PurpleDragonBook
  • Exercise 2.2.5
    • a: ヒント: 構文木のノード数に関する帰納法を使う.
      • こんな感じ↓で単純にプロダクションで場合分けすれば良い気がする.
    • Base Case: num -> 11 (2^1+2^0) および num -> 1001 (2^3+2^0)
    • 2^{k+1}+2^{k} および 2^{k+3}+2^{k} が3の倍数とする(I.H.)
    • num -> num 0 の場合:
      1. k+1番目の時は，2^{k+2}+2^{k+1} = 2*(2^{k+1}+2^k) で，I.H.よりこれは3の倍数.
      2. 同様に k+1番目の時 2^{k+4}+2^{k+1} = 2*(2^{k+3}+2^k) だから I.H.よりこれは3の倍数.
        • ;; つーかこれって左シフト演算に他ならないので自明か．
    • num -> num num は以下4通りの場合分け.
      1. 2^{k+3}+2^{k+2}+2^{k+1}+2^{k+0} の時, 2^{2}*(2^{k+1}+2^{k+0})+2^{k+1}+2^{k+0} = (2^{k+1}+2^{k+0})(2^{2}*+1) = (2^{k+1}+2^{k+0})*5 で，I.H.よりこれは3の倍数
      2. 2^{k+5}+2^{k+4}+2^{k+3}+2^{k+0} の時, (2^{4})(2^{k+1}+2^{k+0})+2^{k+3}+2^{k+0} I.H.より2^{k+1}+2^{k+0}および2^{k+3}+2^{k+0}は3の倍数だからこれも3の倍数
      3. 2^{k+5}+2^{k+2}+2^{k+1}+2^{k+0} の時も同様.
      4. 2^{k+7}+2^{k+4}+2^{k+3}+2^{k+0} の時も同様.
    • b: No. 反例: 10101 (21)
  • Exercise 2.2.6 : ローマ数字の文脈自由文法を作れ.
    • ローマ数字 - Wikipedia
    • 5000,10000の表記は逆Cが必要.
    • 同じ記号は3つまで連続して出現できる．
    • とりあえずアトムは I|V|X|L|C|D|M|I\C\C|CCI\C\C か．
    • IV,IXとか減算があるのがウザイ．