informatics

形式言語 †

言語 language †

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

集合と濃度　 cardinality †

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

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

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

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

そのものの集まりである集合として集合Ｍと集合Ｎがあるとき、集合Ｍの中の１つ１つのもの（＝要素）が、集合Ｎの１つ１つに対応するとき、集合Ｍと集合Ｎは同じ大きさを持つという。

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

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

有限集合と無限集合 †

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

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

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