アルファベット（計算機科学）とは？定義・例・クレーネ星の解説

計算機科学のアルファベットとは何かを定義・例・クレーネ星（Kleene閉包）まで図解と具体例でやさしく解説。有限集合や文字列の基礎から応用まで学べる記事。

コンピュータサイエンスでは、アルファベットは有限の非空の集合である。アルファベットの要素は、アルファベットの文字や記号と呼ばれます。

アルファベットの例としては、{ - , ・ }があります。モールス信号や、プログラミング言語のキーワードになりそうな{begin, if, else, for, while}のようなものがあるかもしれない。

自然数の集合は有限ではないので、アルファベットではありません。

コンピュータサイエンスで最も多く使われているアルファベットは{0,1}です。これは、2つの記号を含むことから、2進法のアルファベットと呼ばれています。アルファベットは文字列（または単語）を作るのに使うことができます。これは、アルファベットからの文字の有限のシーケンスです。例えば、{0,1}上の長さ5の文字列は01101です。

空文字列は、文字を含まない文字列である（λ {\displaystyle \lambda } と書かれることが多い）。空文字列は、任意のアルファベットの上の文字列である。

Σ(ﾟДﾟ)ﾉ Σ(ﾟДﾟ)ﾉ Σというアルファベットがあれば.Σ {\displaystyle \Sigma }から作れる全ての文字列の集合を Σ Σ ∗ {\displaystyle \Sigma ^{*}}と書く。.これは、Σ｛\displaystyle \Sigma｝のKleene star（またはKleene closure）と呼ばれる。.数学者のスティーブン・コール・クレーネにちなんで名付けられました。

二進アルファベットのクレーネ星は { λ , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , ...}♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪ ♪.001 の後の 3 つの点は、無限集合であるため、アルファベットの Kleene の星を完全に書くことができないことを示しています。

アルファベットは、形式言語や有限オートマトン、コンピュータサイエンスでは何が計算できて何が計算できないのかという非常に難しい問題を研究するために使われているので、重要です。

定義の補足

アルファベット (alphabet) は有限個の記号を集めた集合です。記号はしばしば英字や数字、特別な記号などで表され、集合を Σ（シグマ）と書くことが多いです。有限であること、かつ空集合でないことが重要な条件です（空ではない＝少なくとも一つの記号を持つ）。

文字列と長さ・連接

アルファベット Σ の上の 文字列 (string) は、Σ の元（文字）からなる有限長の並びです。文字列の長さは通常 |w| で表します。例えば Σ = {0,1} に対して文字列 w = 01101 は |w| = 5 です。文字列の連接（concatenation）を用いると、文字列 u と v から新しい文字列 uv を作れます。空文字列 λ（あるいは ε と表すこともある）は長さ 0 の特別な文字列で、任意の文字列 w について λw = wλ = w となります。

Kleene（クレーネ）閉包（Σ*）と Σ+

アルファベット Σ に対して、Σ*（Σ の Kleene star）は Σ から作れるすべての有限長の文字列の集合です。記法としては Σ* = {λ} ∪ Σ ∪ Σ^2 ∪ Σ^3 ∪ ... のように書きます。ここで Σ^n は長さ n のすべての文字列の集合です。クレーネ星は有限長のすべてを含むので、通常は無限集合になります（Σ が空でない限り）。

また、Σ+（Kleene プラス）は空文字列を除いたすべての有限長文字列の集合で、Σ+ = Σ Σ*（すなわち Σ* から λ を除いたもの）です。

や といった記法は理論計算機科学や形式言語論で広く使われています。数学者のスティーブン・コール・クレーネ（Stephen Cole Kleene）にちなんで名付けられました。

具体例

• 英語アルファベット Σ = {a, b, c, ..., z} — 有限個の文字からなる典型的なアルファベット。
• 二進アルファベット Σ = {0,1} — コンピュータのビット列を表す基本的な例。
• モールス信号やプログラミング言語のキーワード集合（例: {begin, if, else, for, while}）も有限ならアルファベットになり得る。
• 自然数全体の集合は無限なのでアルファベットにはならない（有限でないため）。

言語と応用

言語 (language) とは、Σ* の部分集合です。すなわち、あるアルファベット上の言語はそのアルファベットから作れる文字列の集まりのことを指します。形式言語論、正規表現、有限オートマトン、文脈自由文法、チューリングマシンなどはすべてアルファベットとその上の言語を基盤にしています。

アルファベットとその構成する言語の理論は、何が効率的に認識・生成できるか（計算可能性、複雑性）や、コンパイラ設計、通信プロトコル、データ検証、暗号理論など多くの応用分野で重要です。有限オートマトンや正規表現は、実際のソフトウェアで文字列処理やパターン照合を行う際に直接使われます。

補足：性質と注意点

• アルファベットは必ず有限かつ非空であること。
• Σ* はほとんどの場合無限集合（Σ に少なくとも1要素ある場合）。
• 空文字列 λ はすべての Σ に対して Σ* に含まれる。
• ある言語が正規言語／文脈自由言語であるかどうかは、その言語がどのような計算モデルで認識できるかによって決まる（形式言語論の基本問題）。

以上が、計算機科学における「アルファベット」とその周辺概念（文字列、空文字、Kleene 星、言語、応用）についての概要です。具体例や演習問題を通して、Σ、Σ*、言語の操作（和、連接、クリーニング、閉包など）に慣れると理解が深まります。

質問と回答

Q:アルファベットとは何ですか?

Q:自然数の集合はアルファベットと言えるのでしょうか?

Q:コンピュータサイエンスで最もよく使われるアルファベットは何ですか?

Q:アルファベットから文字列を作るとはどういう意味ですか?

Q:クリーネ星とは何を指しているのですか?

Q:連星系アルファベットのKleene星は、どのように表現すればよいのでしょうか?

Q:なぜアルファベットはコンピュータサイエンスで重要なのですか?

文字で検索