- 追加された行はこの色です。
- 削除された行はこの色です。
- 形式言語 へ行く。
[[informatics]]
**形式言語 [#v22c4690]
***言語 language [#vf423c44]
-文法 Grammer&br;Ｖを変数記号ないしは非終端記号 nonterminal symbol の集合、Ｔを定数記号ないしは終端記号 terminal symbol の集合、Ｒを生成規則、Ｓを開始記号 start symbol としたとき、&br; 列（Ｖ,Ｔ,Ｒ,Ｓ）&br; を文法という。
-\(U^{*}\)：Uの要素の有限列全体の集合。重複があっても良い。
-空列：０個の要素の列。
-要素αの長さ|α|：列αを構成する U の要素の個数。
-\(U^{+}\)：\(U^{*}\)-{ε}
-文法 Grammer ：&br;Ｖを変数記号ないしは非終端記号 nonterminal symbol の集合、Ｔを定数記号ないしは終端記号 terminal symbol の集合、Ｒを生成規則、Ｓを開始記号 start symbol としたとき、&br; 列（Ｖ,Ｔ,Ｒ,Ｓ）&br; を文法という。
***集合と濃度 cardinality [#n6ca03d0]
集合論では「ものの集まり」を「集合」という。
~「もののあつまり」である集合をＭ、その集合Ｍの中に含まれるものを要素(element)という。
~これは、次のように表される。
~
\[ａ \in Ｍ\]
~
~\(\in\) という記号は、要素(element)の「e」あるいは、ギリシア語の「ε」に由来するとも言われる。
~
~そのものの集まりである集合として集合Ｍと集合Ｎがあるとき、集合Ｍの中の１つ１つのもの（＝要素）が、集合Ｎの１つ１つに対応するとき、集合Ｍと集合Ｎは同じ大きさを持つという。
~このとき、集合Ｍと集合Ｎは同じ濃度(cardinality)を持つという。
~
~集合Ｎの要素が必ず集合Ｍの要素にもなっている場合は集合としてＮはＭに含まれるといい、ＮはＭの部分集合であるという。
~
\[Ｎ \subset Ｍ\]
***有限集合と無限集合 [#aff901f4]
-有限集合：有限個の要素(element)からなる集合(set)。
-無限集合：集合を構成する要素(element)が無限にあるもの。
***可算(countable)と非可算(uncountable) [#v51a3738]
-可算集合：集合のうち、各要素に自然数の番号を割り振る事ができる集合のこと。
-非可算集合：集合のうち、各要素に自然数の番号を割り振る事ができない集合のこと。
