アルファベット(形式言語)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

正式な言語理論ではアルファベットは空でない記号/グリフのセットであり、通常は文字、文字、または数字を表すと考えられています[1]が、他の可能性の中でも、「記号」は一連の音符(音の単位)である可能性もあります。 )。この技術的な意味でのアルファベットは、論理学、数学、コンピューターサイエンス、言語学など、さまざまな分野で使用されています。アルファベットには任意のカーディナリティ(「サイズ」)があり、その目的に応じて有限(たとえば、「a」から「z」までの文字のアルファベット)、可算(たとえば、)、または数えられない(例えば、)。

アルファベット上の文字列( 「単語」とも呼ばれます)は、アルファベットセットの一連の記号として定義されます。[2]たとえば、小文字の「a」から「z」のアルファベットを使用して「iceberg」のような英語の単語を形成でき、大文字と小文字の両方のアルファベットを使用して「Wikipedia」のような固有名詞を形成することもできます。 "。一般的なアルファベットは{0,1}、バイナリアルファベットであり、「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、_}。

与えられたアルファベット、長さのすべての文字列のセットアルファベットの上によって示されますセットすべての有限文字列(長さに関係なく)は、クリーネ閉包演算子によって次のように示されます。、およびのクリーネ閉包とも呼ばれます表記アルファベット上のすべての無限シーケンスのセットを示します、 とセットを示しますすべての有限または無限のシーケンスの。

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

アプリケーション

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

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

も参照してください

参考文献

  1. ^ エビングハウス、H.-D。; Flum、J。; トーマス、W。(1994)。数理論理学(第2版)。ニューヨークSpringerp。11. ISBN 0-387-94258-0アルファベット 空でない記号のセットを意味します
  2. ^ Rautenberg、Wolfgang(2010)。数理論理学の簡潔な紹介(PDF)(第3版)。スプリンガー。p。xx。ISBN  978-1-4419-1220-6𝗔がアルファベットの場合、つまり要素𝐬∈𝗔が記号または少なくとも名前の付いた記号の場合、シーケンス(𝐬1 ...、𝐬n ∈𝗔n𝐬1 ···𝐬n記述されます。文字列または単語と呼ばれる𝗔。

文学