アルファベット（正式な言語）

形式言語理論では、アルファベットは語彙とも呼ばれ、空でない分割できない記号/文字/グリフの集合であり、^{[1]通常は文字、記号、数字、}音素、さらには単語を表すものと考えられています。 ^[2]^[3]この集合の技術的な意味でのアルファベットは、論理学、数学、コンピュータサイエンス、言語学など、さまざまな分野で使用されています。アルファベットは任意の基数（「サイズ」）を持つことができ、その目的に応じて有限（例：文字「a」から「z」のアルファベット）、可算（例：）、または不可算（例：）になる場合があります。 $\{v_{1},v_{2},\ldots \}$ $\{v_{x}:x\in \mathbb {R} \}$

文字列は「単語」や「文」とも呼ばれ、アルファベットの集合の記号の並びとして定義されます。 ^[4]たとえば、小文字の「a」から「z」までのアルファベットは「iceberg」のような英単語を作るのに使えますが、大文字と小文字の両方のアルファベットは「Wikipedia」のような固有名詞を作るのにも使えます。一般的なアルファベットは{0,1}、バイナリアルファベットは「00101111」で、バイナリ文字列の例としては「00101111」があります。記号の無限の並びも考えられます（オメガ言語を参照）。

実用上、アルファベットの記号を制限して、解釈時に曖昧さがないようにすることが必要なことがよくあります。たとえば、2 つの要素から成るアルファベットが {00,0} である場合、紙に「000」と書かれた文字列は、3 つの「0」記号のシーケンスなのか、「00」の後に「0」が続くのか、「0」の後に「00」が続くのかが不明瞭であるため、曖昧になります。

表記

Lが形式言語、つまり有限長の文字列の（おそらく無限の）集合である場合、 LのアルファベットはL内の任意の文字列に出現する可能性のあるすべての記号の集合です。たとえば、L がプログラミング言語 Cのすべての変数識別子の集合である場合、Lのアルファベットは集合 { a, b, c, ..., x, y, z, A, B, C, ..., X, Y, Z, 0, 1, 2, ..., 7, 8, 9, _ } です。

アルファベットが与えられたとき、アルファベット上の長さのすべての文字列の集合はで表されます。すべての有限文字列 (長さに関係なく) の集合は、クリーネの星型演算子によってと表され、のクリーネ閉包とも呼ばれます。表記はアルファベット上のすべての無限シーケンスの集合を示し、はすべての有限または無限シーケンスの集合を示します。 $\Sigma$ $n$ $\Sigma$ $\Sigma ^{n}$ ${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$ $\Sigma^{*}$ $\Sigma$ $\Sigma ^{\omega }$ $\Sigma$ $\Sigma ^{\infty }$ $\Sigma ^{\ast }\cup \Sigma ^{\omega }$

たとえば、2進アルファベット{0,1}を使用すると、文字列ε、0、1、00、01、10、11、000などはすべてアルファベットのクリーネ閉包に含まれます（ここで、εは空の文字列を表します）。

アプリケーション

アルファベットは、形式言語、オートマトン、セミオートマトンの使用において重要です。ほとんどの場合、決定性有限オートマトン(DFA) などのオートマトンインスタンスを定義するには、オートマトンの入力文字列を構築するアルファベットを指定する必要があります。これらのアプリケーションでは、アルファベットは通常、有限集合である必要がありますが、それ以外に制限はありません。

オートマトン、正規表現、または形式文法を文字列処理アルゴリズムの一部として使用する場合、アルファベットは、これらのアルゴリズムによって処理されるテキストの文字セット、またはその文字セットから許容される文字のサブセットであると想定できます。

参照

参考文献

^ フレッチャー、ピーター、ホイル、ヒューズ、パティ、C. ウェイン (1991)。離散数学の基礎。PWS-ケント。p. 114。ISBN 0-53492-373-9アルファベットは、そのメンバーが記号または文字と呼ばれる空でない有限集合です。
^ エビングハウス、H.-D. ; フラム、J.; トーマス、W. (1994). 数学論理学（第2版）.ニューヨーク：シュプリンガー. p. 11. ISBN 0-387-94258-0アルファベットとは、空でない記号の集合を意味します。 ${\mathcal {A}}$
^ Rosen, Kenneth H. (2012). 離散数学とその応用(PDF) (第7版). ニューヨーク: McGraw Hill . pp. 847–851. ISBN 978-0-07-338309-5語彙（またはアルファベット）V は、記号と呼ばれる有限の空でない要素の集合です。V 上の単語（または文）は、V の要素の有限の長さの文字列です。
^ ラウテンバーグ、ヴォルフガング(2010)。『数学論理の簡潔な入門』(PDF) (第3版)。シュプリンガー。p. xx。ISBN 978-1-4419-1220-6𝗔 がアルファベットである場合、つまり要素 𝐬 ∈ 𝗔 が記号または少なくとも名前の付いた記号である場合、シーケンス (𝐬 ₁ ,...,𝐬 _n )∈𝗔 ^{n は}𝐬 ₁ ···𝐬 _{nと表記され、𝗔 上の}文字列または単語と呼ばれます。

文学

John E. Hopcroft と Jeffrey D. Ullman、『オートマトン理論、言語、計算入門』、Addison-Wesley Publishing、マサチューセッツ州リーディング、1979 年。ISBN 0-201-02988 -X。

[1] フレッチャー、ピーター、ホイル、ヒューズ、パティ、C. ウェイン (1991)。離散数学の基礎。PWS-ケント。p. 114。ISBN 0-53492-373-9アルファベットは、そのメンバーが記号または文字と呼ばれる空でない有限集合です。

[Ebbinghaus1994-2] エビングハウス、H.-D. ; フラム、J.; トーマス、W. (1994). 数学論理学（第2版）.ニューヨーク：シュプリンガー. p. 11. ISBN 0-387-94258-0アルファベットとは、空でない記号の集合を意味します。 ${\mathcal {A}}$

[3] Rosen, Kenneth H. (2012). 離散数学とその応用(PDF) (第7版). ニューヨーク: McGraw Hill . pp. 847–851. ISBN 978-0-07-338309-5語彙（またはアルファベット）V は、記号と呼ばれる有限の空でない要素の集合です。V 上の単語（または文）は、V の要素の有限の長さの文字列です。

[Rautenberg-4] ラウテンバーグ、ヴォルフガング(2010)。『数学論理の簡潔な入門』(PDF) (第3版)。シュプリンガー。p. xx。ISBN 978-1-4419-1220-6𝗔 がアルファベットである場合、つまり要素 𝐬 ∈ 𝗔 が記号または少なくとも名前の付いた記号である場合、シーケンス (𝐬 ₁ ,...,𝐬 _n )∈𝗔 ^{n は}𝐬 ₁ ···𝐬 _{nと表記され、𝗔 上の}文字列または単語と呼ばれます。