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

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

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

文字列は多くの場合、記号の連結として記述されますが、この表記規則を使用する場合、この表記が曖昧にならないように、アルファベット内の記号を制限することが実際上便利です。たとえば、2つの要素からなるアルファベットが {00,0} の場合、連結形式で「000」と記述された文字列は、3 つの「0」記号のシーケンスなのか、「00」の後に「0」が続くのか、または「0」の後に「00」が続くのかが不明瞭なため、曖昧です。ただし、これは文字列を記述するための表記法の制限であり、文字列の根本的な定義の制限ではありません。任意の有限集合と同様に、{00,0} をアルファベットとして使用でき、その文字列は、要素をコンマで区切る別の表記規則で曖昧さなく記述できます。0,00 ≠ 0,0,0 ≠ 00,0。

定義によれば、形式言語のアルファベット${\displaystyle L}$以上${\displaystyle \Sigma }$セットは${\displaystyle \Sigma }$これは、空でない任意の記号の集合であり、その中のすべての文字列は${\displaystyle L}$構築されます。たとえば、セット${\displaystyle \Sigma =\{\_,\mathrm {a} ,\dots ,\mathrm {z} ,\mathrm {A} ,\dots ,\mathrm {Z} ,0,\mathrm {1} ,\dots ,\mathrm {9} \}}$正式な言語のアルファベットになり得る${\displaystyle L}$つまり、「C プログラミング言語のすべての変数識別子」という意味です。アルファベットのすべての記号を使用する必要はありません。${\displaystyle L}$その弦のために。

アルファベットが与えられた${\displaystyle \Sigma }$長さ のすべての文字列の集合${\displaystyle n}$アルファベット順${\displaystyle \Sigma }$によって示されます$\displaystyle \Sigma ^{n}}$セット${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$すべての有限弦（長さに関係なく）は、クリーネスター演算子によって次のように表されます。$\displaystyle \Sigma ^{*}}$また、クリーネ閉包とも呼ばれる。${\displaystyle \Sigma }$表記法$\displaystyle \Sigma ^{\omega }}$アルファベット上のすべての無限数列の集合を示す${\displaystyle \Sigma }$、 そして${\displaystyle \Sigma ^{\infty }}$セットを示します$\displaystyle \Sigma ^{\ast }\cup \Sigma ^{\omega }}$有限または無限のすべての数列。

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

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

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

• 単語の組み合わせ論
• 終端記号と非終端記号

• ジョン・E・ホプクロフト、ジェフリー・D・ウルマン著『オートマタ理論、言語、計算入門』、アディソン・ウェスリー出版、マサチューセッツ州レディング、1979年。ISBN 0-201-02988-X。