昨日の続きです．
- 本日の資料では，多くの用語を，ホップクロフト，モトワニ，ウルマン著，野崎昭弘，高橋正子，町田元，山崎秀記訳『オートマトン 言語理論 計算論I [第2版]』，サイエンス社，ISBN4781910262 に依っている．
- 「…」（三点リーダ）を数式中に書く場合，その高さをベースラインに合わせる（x1, x2, ..., xn の列挙）ものと，文字や演算子の中心に合わせる（x1x2…xn，Σ0 ∪Σ1 ∪…∪Σn∪…）ものがある．このスライドではすべてベースラインにあわせているが，これはPowerPointのお節介機能によるものである（と言い訳をしておく）．
- Σ* は，アレフ0，すなわち整数全体と濃度の等しい集合である．Σ上の言語全体からなる集合は，アレフ1，すなわち実数全体と濃度の等しい集合である．一般に，空でない集合Xの部分集合族（部分集合全体からなる集合）は，集合Xよりも大きな集合となる（有限集合の場合，要素数を比較すればよい．無限集合の場合，集合Xとそのべき集合の間で，一対一の対応をとることができない）．
- 「(V, T, P, S)」 の両端のカッコは，４字組の始まりと終わりの記号であり，省略できない．また中の順番を変えてはいけない．「(V∪T)*」は，終端記号および非終端記号からなる長さ0以上の系列である．ここのカッコは，演算子の優先順位を変えるためのものである．例えば，V=φならば，T*と等価になる．また，逆順にして「 (T∪V)*」と書いても差し支えない．
- 空文字列εも，回文か?
- オートマトンとは 【automaton】 - 意味・解説 ： IT用語辞典: http://e-words.jp/w/E382AAE383BCE38388E3839EE38388E383B3.html
- セル・オートマトン - Wikipedia: http://ja.wikipedia.org/wiki/%E3%82%BB%E3%83%AB%E3%83%BB%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3
- 「偶数個の0と偶数個の1を持つ文字列」を導出する正規文法（生成規則のみ）*1：
S→0A, S→1B
A→0S, A→1C
B→0C, B→1S
C→0B, C→1A
*1:これでは文字列が生成できないじゃないか! 「S→ε」も必要です．
