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) †
- 可算集合:集合のうち、各要素に自然数の番号を割り振る事ができる集合のこと。
- 非可算集合:集合のうち、各要素に自然数の番号を割り振る事ができない集合のこと。