正式な言語と文法

やる気

時々、形式言語の理論のさまざまな側面に捧げられた投稿や翻訳された記事がHabréで公開されます。 そのような出版物（著者を怒らせないように特定の作品を示したくない）、特に言語を処理するためのさまざまなソフトウェアツールの説明に専念している出版物では、しばしば不正確さと混乱があります。 著者は、そのような不幸な状態に至った主な理由の1つは、形式言語の理論の根底にある考えの不十分なレベルの理解であると信じる傾向があります。



このテキストは、形式言語と文法の理論への一般的な紹介として意図されています。 この理論は、かなり複雑で紛らわしいと考えられています（そして、かなり公平に言わなければなりません）。 講義では、学生は通常退屈し、試験は熱心ではありません。 したがって、科学ではこの分野の研究者は多くありません。 前世紀の50年代半ばに正式な文法理論が誕生してから現在に至るまで、この科学分野では2つの博士論文のみが発行されてきました。 そのうちの1つは60年代後半にAlexei Vladimirovich Gladkyによって書かれました。2つ目はすでに新しいミレニアム-マティペントゥスの危機にergeしています。



さらに、最もアクセスしやすい形式で、形式言語の理論の2つの基本概念、形式言語と形式文法が説明されています。 テストが聴衆にとって興味深いものである場合、著者はこれらの反対意見をさらに2つ生まれることを厳soleに約束します。

正式な言語

要するに、形式言語は実際の言語の数学モデルです。 ここでの実際の言語とは、被験者同士の特定のコミュニケーション（コミュニケーション）の方法を意味します。 コミュニケーションのために、被験者は、厳密な一時的な順序で話される（書き出される）記号（シンボル）の有限セットを使用します。 線形シーケンスを形成します。 このようなシーケンスは通常、単語または文と呼ばれます。 したがって、いわゆる 数学的方法を使用して研究される言語のコミュニケーション機能。 この言語の他の機能はここでは学習されないため、考慮されません。



正式な言語がどのように研究されているかをより正確に理解するには、最初に数学的研究方法の特徴を理解する必要があります。 Kolmogorov et al。（Aleksandrov A.D.、Kolmogorov A.N.、Lavrentiev M.A. Mathematics。its content、methods and value。Volume 1. M .: Publishing House of the Academy of the Sciences of the US of Sciences of the USSR、1956.）適用対象にかかわらず、常に2つの基本原則に従います。

1. 汎化（抽象化）。 数学の研究の対象は、数学にのみ存在する特別な存在であり、数学者による研究を目的としています。 数学的なオブジェクトは、実際のオブジェクトを要約することによって形成されます。 数学者はオブジェクトを研究する際に、その特性の一部のみに気づき、残りの部分から注意をそらします。 したがって、抽象的な数学的オブジェクト「数」は、実際には池のガチョウの数または水滴の分子の数を示すことができます。 主なものは、ガチョウと水分子についてです
   
   集合体のように話します。 このような実際のオブジェクトの「理想化」は、1つの重要な特性を意味します。数学はしばしば無限のコレクションで動作しますが、実際にはそのようなコレクションは存在しません。
2. 厳密な推論。 科学では、その結果を実際に存在するものと比較することにより、特定の推論の真実を確認することが慣習的です。 実験を行います。 数学では、真実の推論をチェックするこの基準は機能しません。 したがって、結論は実験的には検証されませんが、特定のルールに従う厳密な推論によって妥当性を証明するのが慣習です。 これらの議論は証拠と呼ばれ、証拠は声明の忠実性を正当化する唯一の方法です。

したがって、数学的な方法を使用して言語を学習するには、まず、言語から学習に重要なプロパティを分離する必要があり、次にこれらのプロパティを厳密に定義します。 このようにして得られた抽象化は、形式言語と呼ばれます-実際の言語の数学的モデルです。 特定の数学的モデルの内容は、どのプロパティが研究に重要かによって異なります。 現時点で分離して研究する予定のもの。



このような数学的抽象化のよく知られた例として、ロシア語の耳には聞こえない「言葉の袋」という名前で知られているモデルを引用できます。 このモデルは、自然言語（つまり、人々が毎日のコミュニケーションの過程で使用する言語の1つ）のテキストを探索します。 ワードバッグモデルの主なオブジェクトは、単一の属性（ソーステキスト内でのこの単語の出現頻度）を備えた単語です。 このモデルでは、単語がどのように隣り合っているかを考慮せず、テキストに各単語が何回現れるかだけを考慮します。 単語の袋は、学習の主な目的の1つとしてテキストに基づく機械学習で使用されます。



しかし、形式言語の理論では、互いに隣り合う単語の配置の法則を研究することが重要と思われます。 テキストの構文特性。 このため、ワードバッグモデルは貧弱に見えます。 したがって、形式言語は、有限アルファベットの要素で構成される一連のシーケンスとして定義されます。 これをより厳密に定義します。



アルファベットは、要素の有限の空でないセットです。 これらの要素はシンボルと呼ばれます。 アルファベットを指定するには、通常ラテンVを使用し、アルファベットの文字、ラテンアルファベットの最初の小文字を指定します。 たとえば、式V = {a,b}



は、2文字のアルファベットaおよびbを示します。



文字列は、文字の有限シーケンスです。 たとえば、 abc



は3文字の文字列です。 多くの場合、シンボルでチェーンを指定するとき、インデックスが使用されます。 チェーン自体は、ギリシャ語のアルファベットの末尾の小文字で示されます。 たとえば、 omega = a1...an



はn文字の文字列です。 チェーンは空、つまり 単一の文字を含めないでください。 このようなチェーンは、ギリシャ文字のイプシロンで示されます。



最後に、アルファベットV上の形式言語Lは、アルファベットVの記号で構成されるチェーンの任意のセットです。ここでのAr意性とは、言語が空になる可能性があることを意味します。 単一のチェーンがないため、無限です。 無限の数のチェーンで構成されています。 後者の事実はしばしば困惑します。無限の数のチェーンを含む実際の言語はありますか？ 一般的に、自然界ではすべてが有限です。 しかし、ここでは無限の長さのチェーンを形成する可能性として無限を使用します。 たとえば、C ++プログラミング言語の可能な変数名で構成される言語は無限です。 結局のところ、C ++の変数名の長さは制限されていないため、そのような名前は無限に存在する可能性があります。 もちろん、実際には、長い変数名はあまり意味がありません。 そのような名前を読むことの終わりまでに、あなたはすでにその始まりを忘れています。 しかし、無制限の長さの変数を設定する潜在的な機会として、このプロパティは便利に見えます。



したがって、形式言語は、有限のアルファベットの文字で構成された単なるチェーンのセットです。 しかし、疑問が生じます：正式な言語はどのように尋ねられますか？ 言語が有限である場合、単純にそのすべてのチェーンを次々と書き出すことができます（もちろん、少なくとも1万個の要素を持つ言語のチェーンを書くことが理にかなっているかどうかを考えることができ、一般的にそのような記述には意味がありますか？） 言語が無限の場合の対処方法、設定方法 この時点で、文法がシーンに入ります。

正式な文法

言語を定義する方法は、その言語の文法と呼ばれます。 したがって、私たちは文法を言語を定義するあらゆる方法と呼びます。 たとえば、文法L = {a^nb^n}



（ここでnは自然数）は、 ab, aabb, aaabbb



などの形式のチェーンで構成される言語Lを定義します。 言語Lは無限の数のチェーンですが、それでも、その文法（説明）は10文字のみで構成されています。 有限。



文法の目的は、言語を設定することです。 このタスクは必ず最終的なものでなければなりません。そうしないと、人はこの文法を理解できなくなります。 しかし、最後のタスクは無限の集約をどのように記述しますか？ これは、言語のすべてのチェーンの構造が、有限数の統一原則に基づいている場合にのみ可能です。 上記の例では、次の原則がそのような原則として機能します。「各言語チェーンは文字aで始まり、同じ数の文字bが続きます」。 言語がランダムに型付けされたチェーンの無限のコレクションであり、その構造が同じ原則に従っていない場合、明らかにそのような言語の文法を発明することはできません。 そして、そのような集合体を言語とみなすことができるかどうかという別の質問があります。 数学的厳密さとアプローチの均一性のために、そのような集合体は通常、言語と見なされます。



したがって、言語の文法は、そのチェーンの内部構造の法則を説明しています。 このような法律は通常、構文法と呼ばれます。 したがって、言語の構文法則を記述する最後の方法として、文法の定義を言い換えることができます。 実際には、文法だけでなく、単一のアプローチ（形式主義またはパラダイム）のフレームワークで指定できる文法も興味深いものです。 つまり、単一の言語（メタ言語）に基づいて、すべての形式言語の文法記述。 次に、このメタ言語で作成された文法記述を入力として使用し、言語チェーンで何かを行うコンピューターのアルゴリズムを考え出すことができます。



このような文法記述パラダイムは、構文理論と呼ばれます。 正式な文法は、ある種の構文理論の枠組み内で記述された文法の数学モデルです。 かなり多くのそのような理論が発明されました。 もちろん、文法を指定するための最も有名なメタ言語は、チョムスキーの生成文法です。 しかし、他の形式があります。 それらの1つ-近隣文法については、以下で説明します。



アルゴリズムの観点から、文法は言語の指定方法に従って細分化できます。 このような主な方法は3つあります（文法の種類）：

• 文法を認識します。 このような文法は、言語のチェーンとともに提供されるデバイス（アルゴリズム）であり、出力デバイスは、チェーンが言語に属している場合は「はい」、そうでない場合は「いいえ」を出力します。
• 生成文法。 このタイプのデバイスは、オンデマンドで言語チェーンを生成するために使用されます。 比Fig的に言えば、ボタンが押されると、特定の言語の連鎖が生成されます。
• 文法のリスト。 このような文法は、すべての言語チェーンを次々に印刷します。 明らかに、言語が無限数のチェーンで構成されている場合、列挙プロセスは停止しません。 もちろん、適切なタイミングで、たとえば、目的のチェーンが印刷されたときに、強制的に停止できます。

興味深い質問は、文法の種類を相互に変換することです。 生成文法を使用して、たとえば列挙子を作成することは可能ですか？ 答えはイエスです、できます。 これを行うには、たとえば文字の長さと順序で並べ替えてチェーンを生成するだけで十分です。 しかし、列挙文法を認識文法に変えることは一般的に不可能です。 次の方法を使用できます。 入力としてチェーンを受け取ったら、チェーンをリストするプロセスを開始し、リストの文法がこのチェーンを印刷するかどうかを待ちます。 そのようなチェーンが印刷される場合、列挙プロセスを終了し、「はい」を印刷します。 チェーンが言語に属している場合、必ず印刷され、認識されます。 ただし、チェーンが言語に属していない場合、認識プロセスは無期限に継続します。 認識文法プログラムがループします。 この意味で、文法を認識する力は、ジェネレーターと列挙子の力よりも小さいです。 これは、チョムスキーの生成文法とチューリングの認識マシンを比較する際に留意する必要があります。

隣の文法

60年代半ば、ソビエトの数学者ジュリアスアナトリエヴィッチシュライダーは、いわゆる 近所の文法。 言語の各シンボルに対して、有限数の「近傍」が指定されます。このシンボルを含むチェーン（近隣の中心）は、内部のどこかにあります。 言語アルファベットの各シンボルのこのような近傍のセットは、近傍文法と呼ばれます。 チェーンは、このチェーンの各シンボルがその近隣に含まれている場合、近隣文法によって定義された言語に属していると見なされます。



例として、言語A = {a+a, a+a+a, a+a+a+a,...}



考えA = {a+a, a+a+a, a+a+a+a,...}



。 この言語は、算術式の言語の最も単純なモデルであり、記号「a」が数字の役割を果たし、記号「+」が演算の役割を果たします。 この言語の近隣文法を作成します。 シンボル「a」の近傍を定義します。 文字「a」は、3つの構文コンテキストの言語Aのチェーンで発生する可能性があります。最初、2つの「+」文字の間、および最後です。 チェーンの始まりと終わりを示すために、疑似シンボル「＃」を導入します。 その場合、シンボル「a」の近傍は次のようになります： #a+, +a+, +a#



通常、近隣の中心を強調するために、チェーン内のこのシンボルには下線が引かれています（結局、チェーン内には中心ではない他のシンボルが存在する可能性があります！）、ここでは単純な技術的可能性がないため、これを行いません。 記号「+」は2つの記号「a」の間でのみ発生するため、1つの近傍、つまりチェーンa+a



が指定されます。



チェーンa+a+a



を検討し、言語に属しているかどうかを確認します。 チェーンの最初の文字「a」は、近傍#a+



とともに含まれています。 2番目の「+」文字は、近隣a+a



とともにチェーンに入ります。 同様の発生は、チェーンの残りの文字、つまり 予想されるように、このチェーンは言語に属します。 ただし、たとえば、チェーンa+aa



は言語Aに属しません。これは、最後から最後から2番目の文字「a」にはこのチェーンに入る近隣がないためです。



すべての言語が近隣文法で記述できるわけではありません。 たとえば、文字Bが文字「0」または文字「1」で始まる言語Bを考えてみましょう。 後者の場合、文字「a」と「b」はチェーンのさらに先に進むことができます。 チェーンがゼロから始まる場合、文字「a」のみが続行できます。 この言語では近隣文法が発明されないことを証明するのは簡単です。 チェーン内の記号「b」の入力の正当性は、その最初の記号によるものです。 文字「b」と「1」の間の接続が指定されている近隣文法では、文字「b」の近隣がチェーンの先頭に到達しないように、十分に長いチェーンを選択することが可能です。 その後、最初にシンボル「0」を置換することが可能になり、チェーンは言語Aに属しますが、この言語のチェーンの構文構造についての直観的なアイデアを満たしていません。



一方、この言語を認識する有限状態マシンを構築するのは簡単です。 これは、近隣文法で記述される言語のクラスがすでにオートマトン言語のクラスであることを意味します。 近隣文法で定義された言語は、シュレーダー言語と呼ばれます。 したがって、言語の階層では、オートマトン言語のサブクラスであるシュレーダー言語のクラスを区別できます。



シュレーダー言語は、1つの単純な構文関係-「近くにある」または直前の関係を定義していると言えます。 遠い優先順位の関係（明らかに、言語Bに存在します）は、近隣の文法によって与えることはできません。 しかし、言語チェーンで構文関係を視覚化すると、そのようなチェーンが変換される関係の図について、近隣の文法を思い付くことができます。