計算理論の基礎 [1] ２章 章末問題

計算機科学

Information

ver date memo
0.1 2013/06/22 first

始めに

http://www.amazon.co.jp/計算理論の基礎-原著第2版-1-オートマトンと言語-Michael-Sipser/dp/4320122070
上記の本の勉強の際のメモをまとめる。

2.1

テキストだと、木の表現が面倒なので、下記のような証明木っぽい感じで書く。
まぁ、意図は伝わるよね・・・

a

　E
ーー
　a

b
　　　　E
ーーーーーーー
　E　　+　　T
ーー　　　ーー
　T　　　　　F
ーー　　　ーー
　F　　　　　a
ーー
　a


c

type1 左結合が優先される場合((a+a)+a)

　　　　　　　　E
ーーーーーーーーーー
　　　E　　　　+　　　T
ーーーーー　　　ーーー
　E　+　T　　　　　　F
ーー　ーー　　　　ーー
　T　　　a　　　　　　a
ーー
　F
ーー
　a



type2 右結合が優先される場合(a+(a+a))

　　　　E
ーーーーーーーーーーーー
　T　　＋　　　　　E
ーー　　　　ーーーーーーー
　F　　　　　　E　　＋　　T
ーー　　　　ーー　　　　ーー
　a　　　　　　T　　　　　　F
　　　　　　　ーー　　　　ーー
　　　　　　　　F　　　　　　a
　　　　　　　ーー
　　　　　　　　a


c
 　　　　F
      ーーーーーーー
      　（　　　E　　　）
      　　　　ーー
      　　　　　T
      　　　　ーー
      　　　　　F
      　　　　ーー
      　　　　　a