2006-05-19

第９章代数系、形式言語駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』

数学てふ集合駆け足で読むシリーズ Java

本駆け足シリーズの全体の目次はこちら

代数・演算については、第４章ベクトルと行列の項で関連事項としてテンソルに触れたときにも述べたが、『演算規則について一貫性のあるもの』が代数系である。『演算』とは、引数をとって返り値を戻す作業。
n-項演算 n-ary operationは $S^n$ から $S$ への関数。以下、２項演算について記す。
*について閉じている closed under * 。Aの要素a,bについて、a*bがAの要素であるとき、Aは*について閉じている、という
結合的 associative、結合法則を満たす associative law。
- 単位元 identity element。 $a*e=e*a=a$ なるeのこと
- 右単位元 right identity、 $e*a=a$ 、左単位元 left identity、 $a*e=a$
簡約法則 cancellation law。 $b*a=c*a$ ならば $b=c$ のとき左簡約法則を満たす、と言い、 $a*b=a*c$ ならば $b=c$ のとき右簡約法則を満たす、と言う
可換的 commutative、交換法則を満たす commutative law。 $a*b=b*a$ を満たすとき
逆元 inverse。 $a*a^{-1}=a^{-1}*a=e$ のとき、 $a^{-1}$ をaの逆元と言う。
半群 semigroup。結合的な演算*を持つ集合Sを半群と呼ぶ。(S,*)で表す。
自由半群、言語
- 文字列のようなものを考える。基本構成要素の集合を字母系 S alpahabet、その要素を文字 letter と呼ぶ。Sの要素によって作られるもj列の集合を $S^*$ と書く。
- 文字列結合演算は列積 concatenationと呼ぶ
- 文法
  - 文法の構成要素
    - 変数 variableまたは非終端記号 nonterminalsと呼ばれる要素からなる有限集合V
    - 終端記号 terminals と呼ばれる要素からなる有限集合T
    - 初期記号 start symbol と呼ばれる要素からなるVの要素 S
    - 生成規則 production の有限集合P。生成規則Pは、VもしくはTの要素の集まりで、１つの要素から別のへの変換規則(要素のペアで表される)の集合になっている。なお、少なくとも１つのVの要素(変数)が規則の要素ペアの第１要素になっている必要がある。
  - 文法の種類
    - 文法は生成規則の種類により、タイプ0(規則に上述の制限以外にないもの)、タイプ1(文脈依存 context sensitive。変換該当文字列の認識に前後の文字列を必要とするもの)、タイプ2(文脈自由 context free。)、タイプ3(正則 regular。非終端記号からは、終端記号のみに変わる(文章の終了)か、終端記号とそれに続く指定された非終端記号への変換のみででき手いる)に分けられる
    - タイプ0->1->2->3の順番に制約がきつくなっている
    - 文法がタイプ3であることの必要十分条件は対応する有限オートマトンが存在であることも知られている。
群 group
- ２項演算を持つ空でない集合において、次が成り立つとき、群という
  - 結合法則 associative law
  - 単位元 identity element の存在
  - 逆元 inverse の存在
- アーベル群
  - 群であり、可換 commutative なときアーベル群 abelian という
- 置換 permutation
- 部分群 subgroup
  - 群の部分集合が、自身で群の性質を持つとき、部分群という
  - 部分群に対して、元の群の要素を右作用・左作用して得られる要素をそれぞれ右剰余類 right coset、左剰余類 left coretと呼ぶ。右剰余類の数と左剰余類の数は等しい。この数を部分群の群における指数 index という。また、右剰余類と左剰余類が等しいとき、その部分群は正規 normal であるという。
- 群における写像
  - 準同形 homomorphism
  - 同形 isomorphic
  - 核 kernel
環
- 加法において群の性質を有し、可換であり(ここまででアーベル群)、かつ、乗法において結合的であるもの。
- 乗法に関して可換な場合は、可換環 commutative ringと呼ぶ
- 乗法における単位元が存在する場合には、単位元を持つ環と呼ばれる(ここまでで、乗法の逆元がない点のみが乗法に関する群の性質を満足していない)
- 乗法における単位元が存在し、逆元も存在するとき、体 field と呼ぶ
- イデアル ideal
プログラミング問題
- 単位元の確認->IdentityList
- 可換確認->CommutativeCheck
- 結合性確認->AssociativeCheck