informatics

形式言語

言語 language

  • \(U^{*}\):Uの要素の有限列全体の集合。重複があっても良い。
  • 空列:0個の要素の列。
  • 要素αの長さ|α|:列αを構成する U の要素の個数。
  • \(U^{+}\):\(U^{*}\)-{ε}
  • 文法 Grammer :
    Vを変数記号ないしは非終端記号 nonterminal symbol の集合、Tを定数記号ないしは終端記号 terminal symbol の集合、Rを生成規則、Sを開始記号 start symbol としたとき、
    列(V,T,R,S)
    を文法という。

集合と濃度  cardinality

集合論では「ものの集まり」を「集合」という。

「もののあつまり」である集合をM、その集合Mの中に含まれるものを要素(element)という。

これは、次のように表される。
\[a \in M\]

\(\in\) という記号は、要素(element)の「e」あるいは、ギリシア語の「ε」に由来するとも言われる。

そのものの集まりである集合として集合Mと集合Nがあるとき、集合Mの中の1つ1つのもの(=要素)が、集合Nの1つ1つに対応するとき、集合Mと集合Nは同じ大きさを持つという。

このとき、集合Mと集合Nは同じ濃度(cardinality)を持つという。

集合Nの要素が必ず集合Mの要素にもなっている場合は集合としてNはMに含まれるといい、NはMの部分集合であるという。
\[N \subset M\]

有限集合と無限集合

  • 有限集合:有限個の要素(element)からなる集合(set)。
  • 無限集合:集合を構成する要素(element)が無限にあるもの。

可算(countable)と非可算(uncountable)

  • 可算集合:集合のうち、各要素に自然数の番号を割り振る事ができる集合のこと。
  • 非可算集合:集合のうち、各要素に自然数の番号を割り振る事ができない集合のこと。


トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-04-07 (水) 21:21:58 (5331d)