形式言語

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

構文的に整形式であるが、無意味な英語の文、「無色の緑のアイデアは猛烈に眠る」チョムスキー1957年歴史的な例)の構造。

論理学、数学コンピュータサイエンスおよび言語学では、形式言語は、文字アルファベットから取られ、特定の一連の規則に従って 整形式になっている単語で構成されます。

形式言語のアルファベットは、言語の文字列に連結される記号、文字、またはトークンで構成されます。[1]このアルファベットの記号から連結された各文字列は単語と呼ばれ、特定の形式言語に属する単語は、整形式の単語または整形式の式と呼ばれることもあります。形式言語は、多くの場合、構成規則で構成される正規文法文脈自由文法などの形式文法によって定義されます

形式言語理論の分野は、主にそのような言語の純粋に構文的な側面、つまりそれらの内部構造パターンを研究します。自然言語の構文上の規則性を理解する方法として、形式言語理論は言語学から生まれましたコンピュータサイエンスでは、とりわけ、プログラミング言語の文法と、言語の単語が特定の意味またはセマンティクスに関連付けられた概念を表す自然言語のサブセットの形式化されたバージョンを定義するための基礎として、形式言語が使用されます。計算複雑性理論では決定問題通常、形式言語として定義され、複雑度クラスは、計算能力が制限されたマシンで解析できる形式言語のセットとして定義されます。論理数学の基礎では、形式言語は公理システムの構文を表すために使用され数学的形式主義は、すべての数学をこのように形式言語の構文操作に還元できるという哲学です。

歴史

形式言語の最初の使用は、ゴットロープ・フレーゲの1879年の概念記法であると考えられています。これは、「純粋な思考のために、算術の言語をモデルにした形式言語」を表す「概念の記述」を意味します。[2]

文字列の書き換えに使用できるAxelThueの初期のsemi-Thueシステムは、形式文法に影響与えまし

アルファベット上の単語

形式言語のコンテキストでは、アルファベットは任意のセットにすることができますが、通常の意味でのアルファベット、またはより一般的にはASCIIUnicodeなどの文字セットを使用するのが理にかなっていますアルファベットの要素はその文字と呼ばれます。アルファベットには、無限の数の要素を含めることができます。[注1]ただし、形式言語理論のほとんどの定義では、要素数が有限のアルファベットが指定されており、ほとんどの結果はそれらにのみ適用されます。

アルファベット上の単語は、文字の任意の有限シーケンス(つまり文字列)にすることができます。アルファベットΣ上のすべての単語のセットは、通常、Σ *で表されますクリーネ閉包を使用)。単語の長さは、それが構成されている文字の数です。どのアルファベットでも、長さ0の単語は1つだけで、空の単語はe、ε、λ、さらにはΛで表されることがよくあります。連結することにより、2つの単語を組み合わせて、元の単語の長さの合計である新しい単語を形成できます。単語を空の単語と連結した結果が元の単語になります。

一部のアプリケーション、特にロジックでは、アルファベットは語彙とも呼ばれ、単語は数式またはと呼ばれます。これにより、文字/単語のメタファーが壊れて、単語/文のメタファーに置き換えられます。

定義

アルファベットΣ上形式言語 Lは、 Σ *のサブセット、つまり、そのアルファベット上の単語のセットです。単語のセットが式にグループ化されることもありますが、「整形式の式」を作成するためのルールと制約が定式化される場合があります。

通常は自然言語を扱わないコンピュータサイエンスや数学では、形容詞「正式」は冗長として省略されることがよくあります。

形式言語理論は通常、いくつかの構文規則によって記述される形式言語に関係しますが、「形式言語」の概念の実際の定義は上記のとおりです。特定のアルファベットから構成される(おそらく無限の)有限長文字列のセット。これ以上でもそれ以下でもありません。実際には、正規言語文脈自由言語など、ルールで記述できる言語はたくさんあります形式文法の概念は、構文規則によって記述される「言語」の直感的な概念に近い場合があります。定義の乱用により、特定の形式言語は、それを説明する形式文法を備えていると考えられることがよくあります。

次の規則は、アルファベットΣ= {0、1、2、3、4、5、6、7、8、9、+、=}上の 形式言語 Lを記述しています。

  • 「+」または「=」を含まず、「0」で始まらない空でない文字列はすべて Lに含まれます。
  • 文字列「0」は Lにあります。
  • "="を含む文字列は、 "="が 1つだけ存在する場合にのみ 、 Lに含まれ、 Lの2つの有効な文字列を区切ります。
  • 「+」を含むが「=」を含まない 文字列は、文字列内のすべての「+」がLの2つの有効な文字列を区切る場合にのみ、  Lに含まれます。
  • Lには、前のルールで暗示されている文字列以外の文字列はありません 。

これらの規則では、文字列 "23 + 4 = 555"は Lに含まれますが、文字列 "= 234 = +"は含まれません。この形式言語は、自然数、整形式の加算、および整形式の加算の等式を表現しますが、それらが何を意味するか(セマンティクス)ではなく、それらがどのように見えるか(構文)のみを表現します。たとえば、これらのルールのどこにも、「0」は数字のゼロを意味し、「+」は加算を意味し、「23 + 4 = 555」は偽であるという表示はありません。

構造

有限言語の場合、整形式のすべての単語を明示的に列挙できます。たとえば、言語 LをL  = {a、b、ab、cba}として記述することができます。この構造の退化したケースは、単語をまったく含まない空の言語です( L  =  )。

ただし、Σ= {a、b}のような有限の(空でない)アルファベットでも、表現できる可能性のある有限長の単語は無限にあります: "a"、 "abb"、 "ababba"、 " aaababbbbaab "、....したがって、正式な言語は通常無限であり、無限の正式な言語を記述することは、L  = {a、b、ab、cba}と書くほど簡単ではありません。形式言語の例を次に示します。

  • L* 、Σ上のすべての単語のセット。
  • L = {a} * = {a n }、ここでnは自然数の範囲であり、「 an 」は「a」がn回繰り返されることを意味しますこれは記号「a」のみで構成される単語のセットです)。
  • 特定のプログラミング言語で構文的に正しいプログラムのセット(その構文は通常、文脈自由文法によって定義されます)。
  • 特定のチューリングマシンが停止する入力のセット。また
  • この行の英数字 ASCII文字の最大文字列のセット。つまり、
    セット{the、set、of、maximal、strings、alphanumeric、ASCII、characters、on、this、line、i、e}。

言語仕様の形式

形式言語は、複数の分野でツールとして使用されます。ただし、形式言語理論が特定の言語に関係することはめったにありませんが(例を除く)、主に言語を記述するためのさまざまなタイプの形式主義の研究に関係しています。たとえば、言語は次のように与えることができます

そのような形式について尋ねられる典型的な質問は次のとおりです。

  • 彼らの表現力は何ですか?(形式主義Xは形式主義Yが説明できるすべての言語を説明できますか?他の言語を説明できますか?)
  • 彼らの認識可能性は何ですか?(与えられた単語が形式主義Xによって記述された言語に属するかどうかを決定することはどれほど難しいですか?)
  • それらの比較可能性は何ですか?(1つは形式主義Xで記述され、もう1つは形式主義Yで記述されている、またはXで記述されている、2つの言語が実際に同じ言語であるかどうかを判断するのはどれほど難しいですか?)

驚くべきことに、これらの決定問題に対する答えは、「まったく実行できない」、または「非常に高価である」(どれだけ高価であるかを特徴づける)です。したがって、形式言語理論は、計算可能性理論複雑性理論の主要な応用分野です。形式言語は、生成文法の表現力と認識オートマトンの複雑さに基づいて、チョムスキー階層に分類できます。文脈自由文法正規文法は、表現度と構文解析の容易さの間の適切な妥協点を提供し、実際のアプリケーションで広く使用されています。

言語の操作

言語に対する特定の操作は一般的です。これには、和集合、積集合、補集合などの標準の集合演算が含まれます。別のクラスの操作は、文字列操作の要素ごとのアプリケーションです。

例:いくつかの一般的なアルファベット上の言語です

  • 連結_ フォームのすべての文字列で構成されますどこからの文字列ですからの文字列です
  • 交差点_ 両方の言語に含まれるすべての文字列で構成されます
  • 補体_ に関して以上のすべての文字列で構成されますにない
  • クリーネ閉包:元の言語で0個以上の単語を連結したすべての単語で構成される言語。
  • 逆転
    • εを空の単語とすると、 と
    • 空でない単語ごとに(どこいくつかのアルファベットの要素です)、
    • その後、形式言語の場合
  • 文字列準同型

このような文字列操作は、言語のクラスのクロージャプロパティを調査するために使用されます。言語のクラスは、クラス内の言語に適用される操作が常に同じクラス内の言語を再び生成するときに、特定の操作の下で閉じられます。たとえば、文脈自由言語は、和集合、連結、および正規言語との共通部分の下で閉じられることが知られていますが、共通部分または補集合の下では閉じられません。トリオ抽象的な言語族の理論は、それ自体で言語族の最も一般的な閉包特性を研究します。[3]

語族の閉包性(Opここで両方列で指定された言語族に属します)。ホップクロフトとウルマンの後。
手術 通常 DCFL CFL IND CSL 再帰的 RE
連合 はい 番号 はい はい はい はい はい
交差点 はい 番号 番号 番号 はい はい はい
補体 はい はい 番号 番号 はい はい 番号
連結 はい 番号 はい はい はい はい はい
クリーネ閉包 はい 番号 はい はい はい はい はい
(文字列)準同型 はい 番号 はい はい 番号 番号 はい
εフリー(ストリング)準同型 はい 番号 はい はい はい はい はい
置換 はい 番号 はい はい はい 番号 はい
逆準同型 はい はい はい はい はい はい はい
逆行する はい 番号 はい はい はい はい はい
正規言語との交差 はい はい はい はい はい はい はい

アプリケーション

プログラミング言語

コンパイラには通常、2つの異なるコンポーネントがあります。ようなツールによって生成されることもある字句解析lexプログラムは、プログラミング言語の文法のトークンを識別します。たとえば、識別子キーワード、数値および文字列リテラル、句読点、演算子記号などです。これらは、通常は正規表現を使用して、より単純な形式言語で指定されます。式最も基本的な概念レベルでは、のようなパーサージェネレーターによって生成されることもあるパーサーは、ソースプログラムが構文的に有効かどうか、つまり、コンパイラーが構築されたプログラミング言語の文法に関して適切に形成されているかどうかを判断しようとします。 yacc

もちろん、コンパイラはソースコードを解析するだけでなく、通常は実行可能形式に変換します。このため、パーサーは通常、yes / noの回答よりも多く、通常は抽象構文ツリーを出力します。これは、コンパイラの後続のステージで使用され、ハードウェア上で直接実行されるマシンコード、または仮想マシンの実行を必要とする中間コードを含む実行可能ファイルを最終的に生成します。

正式な理論、システム、および証明

この図は、正式なシステム内の構文上の分割を示しています記号の文字列は、意味のない式と整形式の式に大きく分けることができます論理式のセットは、定理と非定理に分けられます。

数理論理学では形式理論は形式言語で表現され た一連の文です。

形式システム論理計算、または論理システムとも呼ばれます)は、形式言語と演繹装置演繹システムとも呼ばれます)で構成されます。演繹装置は、有効な推論規則として解釈される可能性のある一連の変換規則、または一連の公理、あるいはその両方で構成され得る。正式なシステムは、1つ以上の他の式から1つの式を導出するために使用されます。形式言語はその公式で識別できますが、形式システムはその定理で同様に識別できません。2つの正式なシステムすべて同じ定理を持っていても、いくつかの重要な証明理論的な方法で異なる場合があります(たとえば、式Aは、式Bの構文的帰結である可能性がありますが、別の式ではない可能性があります)。

正式な証明または導出は、それぞれが公理であるか、推論規則によってシーケンス内の前の式に続く、整形式の式(文または命題として解釈される場合があります)の有限のシーケンスです。シーケンスの最後の文は、形式体系の定理です。正式な証明は、それらの定理が真の命題として解釈できるため、有用です。

解釈とモデル

形式言語は本質的に完全に構​​文的ですが、言語の要素に意味を与えるセマンティクスが与えられる場合があります。たとえば、数理論理学では、特定の論理の可能な式のセットは形式言語であり、解釈によって各式に意味が割り当てられます。通常は、真理値です。

形式言語の解釈の研究は、形式意味論と呼ばれます。数理論理学では、これはモデル理論の観点から行われることがよくあります。モデル理論では、数式で発生する用語は数学的構造内のオブジェクトとして解釈され、固定された構成解釈ルールによって、数式の真理値をその用語の解釈からどのように導き出すことができるかが決まります。式のモデルは、式が真になるような用語の解釈です。

も参照してください

メモ

  1. ^ たとえば、一階述語論理は、∧、¬、∀や括弧などの記号に加えて、変数の役割を果たすx 0、  x 1、  x 2 、…などの要素を無限に含むアルファベットを使用して表現されることがよく

参考文献

引用

  1. ^ たとえば、Reghizzi、Stefano Crespi(2009)、正式な言語と編集、コンピュータサイエンスのテキスト、Springer、p。8、Bibcode2009flc..book ..... CISBN 9781848820500アルファベットは有限集合です
  2. ^ マーティンデイビス(1995)。「コンピュータサイエンスに対する数理論理学の影響」Rolf Herken(ed。)万能チューリング機械:半世紀の調査スプリンガー。p。290. ISBN 978-3-211-82637-9
  3. ^ Hopcroft&Ullman(1979)、第11章:言語族の閉包特性。

ソース

引用された作品
一般的な参考資料

外部リンク