異なる問題の 4 つの定式化に関連付けられた 4 つの科学的方向性を区別できます。これらは、当初は独立して発展し、互いにほとんど関連性がないように見えました。

これらの領域の最初の領域は、形式言語学または数学言語学の基礎の作成に関連しています。数学言語学はもともと文学言語の構造の正式な研究に関連して誕生しましたが、たとえば次のような機械翻訳の問題が定式化されたときに特に急速に発展し始めました。

所定のルールセットと所定量のコンピューターメモリが与えられた場合、任意のフレーズをある言語から別の言語に翻訳できますか。

このような条件下で翻訳できるさまざまなテキストをどのように説明すればよいでしょうか? 等

このような質問に答えようとすると、すぐに「辞書」、「文法」、「言語」の概念を形式化する必要がありました。

翻訳者の出現により、翻訳の問題がコンピュータシステムの一般理論の構築の中心となった。

完全に独立して開発された動的システムの形式モデルの構築に関連する科学の一分野。この種の典型的な例は、有限状態マシンモデルです。有限集合で定義された多くのプロセスをカバーし、数え切れないほどの時間をかけて開発された有限オートマトンは、生産的な理論を作成できるほど狭いモデルであることが判明しました。

しかし、時間スケール以外の場所で無限がこのモデルに導入されるとすぐに、それはすぐに、任意のアルゴリズムのような広範な概念に相当する、過度に一般的なシステムのクラスにつながりました。このため、有限オートマトンより広く、チューリングマシンより狭い、力学システムの中間モデルを構築する数多くの試みが生まれました。

アルゴリズムの一般理論は、現代数学の一分野として独立して並行して発展しました。「マルコフ正規アルゴリズム」、「一般再帰関数」、「チューリングマシン」という概念の等価性が確立され、チャーチの論文はこれら3つの概念をアルゴリズムの直感的なアイデアと結び付けました。

コンピュータ技術の発展により、アルゴリズムの数学理論に新たな課題が課されました。たとえば、計算の複雑さによってアルゴリズムを分類することが必要になりました。

「アルゴリズム」と「チューリングマシン」という概念が同等であるため、アルゴリズムの分類の探索は、有限オートマトンのモデルとチューリングマシンのモデル間の中間モデルの探索に関連付けられると想定するのが自然になりました。

したがって、列挙された方向性は密接に関連していることが判明し、純粋に言語的問題によって生成された言語理論が、アルゴリズムと力学システムの理論に携わる数学者の関心の中心であることが判明しました。

形式言語と文法の理論は、数学言語学の主要セクションです。自然言語と人工言語の構造の研究に焦点を当てた特定の数学分野です。

この理論は、1950 年代にアメリカの言語学者の著作の中で生まれました。

N.チョムスキー。使用される数学的装置の性質上、形式文法と言語の理論はアルゴリズムの理論とオートマトンの理論に近いものです。

いくつかの定義をあげてみましょう。

文法とは、いくつかのことを意味します 言語記号の一連のチェーン (有限シーケンス) を定義する規則のシステム.

これらのチェーンは、単語の形式、フレーズ、文など、さまざまなレベルの言語オブジェクトとして解釈できます。

単語形式または単語だけ形態素のシーケンス (チェーン) です。

形態素単語の文法的に重要な最小部分です。

たとえば、「led」という単語は、形態素 ved + w + y (語根、接尾辞、語尾) で構成されます。

フレーズまたは文章単語形式の連鎖です。

言語文法は、この言語を定義する有限のルールのセットです。

言語の文法を考慮することができます この言語の構造の理論、つまり、言語の統語構造と呼ばれる、文構築の繰り返しパターンの理論です。

言語の構文- これらは言語で文を構築するための規則です。

言語の意味論– これらのルールの解釈、構文の使用ルール。

したがって、言い換えれば、次のように言えます - 言語文法 – これは、言語を構文構造として再帰的に定義する有限の規則セットです。.

最初の主要な要件文法的には次のとおりです。

彼女 属性を付ける必要があります彼の言語のあらゆる文が 構造の説明、つまり、文がどのような要素から構成されているか、その順序や配置などは何かを示すものです。

言語の構文単位とそれらの間の階層関係が文法を通じて明確に定義されている場合に限り、構造的記述は明確になります。

2番目の要件文法は彼女です手足.

文法に不定の規則セットがあると仮定すると、文法を構築するという問題そのものが解決不可能なものとして取り除かれてしまいます。

文法の分類次の形式で表示できます。

通常の文法で文を構築するための多くの規則を指定できる場合、形式文法はそのような一連の規則を研究して説明する方法です。

通常の文法と正式な文法の間には本質的な違いがあります。正式な文法では、すべてのステートメントは少数の明確に定義された記号と演算を使って定式化されます。

これにより、形式文法は論理構造の点で比較的単純になり、その特性の研究が容易になりますが、形式文法は自然言語を記述するには非常に面倒であることが判明したため、最も一般的な特性の理論的研究のみを目的としています。言語の。

認識する検討中のチェーンの場合、このチェーンが正しいかどうかを判断し、答えが肯定的であれば、このチェーンの構造について指示を与えることができます。

形式文法と呼ばれる 原動力、その助けを借りて、その構造についての指示を与えながら正しいチェーンを構築することが可能であれば、単一の間違ったチェーンを構築することは不可能です。

形式文法と呼ばれる 変革的な、正しく構築されたチェーンについて、実行される順序で示されたマッピングを指定しながら、再び正しいチェーンの形式でそのマッピングを構築できる場合。

文法を生成するクラスを考えてみましょう。生成文法は順序付けシステムと呼ぶことができます

ここで、はターミナルと呼ばれる有限の記号セットです。

またはメインの G 辞書。

基本的な単語のチェーンまたは辞書が構築され、文が構築される一連の初期要素。

非終端 (補助) 辞書 G と呼ばれる、有限で空ではない記号のセット。

非終端辞書は、初期要素のクラスまたはチェーンを示すシンボルのセット、または構文型の辞書です。

要素と要素は、それぞれ非終端記号と終端記号と呼ばれます。

- G 文法辞書。

要素の任意の有限シーケンスを辞書内のチェーンと呼びます。

空のチェーンはで表されます。。このチェーンのメンバーの数はその長さと呼ばれ、で表されます。

連結演算により辞書文字列を取得します。
例えば、。曖昧さがない場合には、この記号を省略することもできます。

連結操作は結合的ですが、可換的ではありません。
に相当。

S – 文法の頭文字.

これは、文法が記述することを意図している言語オブジェクトのクラスを示す専用の非終端記号です。文献では、S が文法の公理または目標と呼ばれることもあります。

P – 文法規則または、j à y の形式のチェーンの有限セット。ここで、j と y は辞書 V 内の単語であり、チェーン j には辞書 Vн からの少なくとも 1 つの文字が含まれます。

有限二項関係 à は「j を y に置き換える」と解釈されます。

この関係は非対称であり、反映されていません。

j à y 形式のチェーンは文法規則または文法規則と呼ばれます。 置換規則、集合 P は文法スキーム.

文法が与えられれば、その後、次のように言います。

チェーン w’ は、ルール j à y ( w=x1jx2 、 w"=x1jx2 および (j à y)ОP の場合) を適用することにより、チェーン w から直接取得されます。

チェーンシーケンス j=j0, j1, j2 … , jn = y (n³1) ,

ここで、0 £ i £ n および j - は 回路出力各 i について ji+1 が ji から得られる場合、y をポイントします。

チェーン y の j 出力の存在は、j => y で表されます。

このような出力に適用されたルールの数は、その出力と呼ばれます。長さ。出力の長さは、開始文字をカウントしない、出力内の文字列の数に等しくなります。

文字列 y は、文法 G の規則を適用して j から取得される場合、文字列 j から導出されます。

文字列 y の出力が考慮されます 終了した、j から続くチェーンがない場合。

終端文字のみで構成される文字列が呼び出されます。 ターミナルチェーン.

文法 G で出力される文字列の集合は、この文法によって生成された言語と呼ばれ、L(G) で表されます。

L が文法 G の終端文字列の集合である場合、言語 L(G) は終端と呼ばれます。

同意しましょう:

最初の小文字のラテン文字 a、b、c、... は、端末辞書 Vt の要素を示します。

ラテン語の大文字 A、B、C、... - 非終端辞書 Vн の要素、

小さなギリシャ文字 a、b、... - 一般語彙 V の要素。

これらの文で構成される文は、これらのアルファベットの最後の文字、つまり x1、y1、... - 要素 Vt、X、Y、...で構成される文 - 要素 Vн、w、j、y で構成される文で示されます。 , ... - 一般語彙 V の要素で構成される文。

セットの指定に記号 * (V* など) を追加すると、セット V のシンボルから取得できるすべてのチェーンのセットを意味します。

例を見てみましょう:

G=(Vt, Vn,P,S)、ここで Vt=(a, b); Vн=(A,B,C); S=C; P=(Càab、CàaCb)。

w=aCb、w"=aaCbb とします。チェーン w" は、1 つのルールを適用することによって w から直接導出されます。

j-出力: aCb、aaCbb、aaaCbbb、aaaabbbb (端末)。

リードの長さ = 3。

この例から明らかなように、 生成文法はアルゴリズムではありません。

文法の置換規則は、一連の命令ではなく、一連の許可です。

これは次のことを意味します。

ルール j à y は、「j を y に置き換えることができる」ものとして理解され、「置き換えなければならない」ものではありません。

ルールが適用される順序は任意ですが、正確な順序はアルゴリズムで指定されます。

2 つの文法は G1 と G2 と呼ばれます。 弱等価、同じ言語 L(G1)= L(G2) を生成する場合、つまり 彼らが生成するフレーズのセットは一致します。

2 つの文法は次のように呼ばれます。 強く同等、同じチェーンを生成するだけでなく、同じ構造記述を同じチェーンに割り当てる場合。

このような形式文法の適用の主な目的は、任意の文法ではなく、いくつかの特殊なタイプの文法です。

これらのタイプはルールのタイプによって区別されます。

チョムスキーの理論には次のようなものがあります。 4種類の言語、生成される 4つの主要な文法タイプ.

文法はと呼ばれます 文法タイプ 0ルール j à y に制限が課されていない場合、j と y は辞書 V の任意の文字列にすることができます。

文法はと呼ばれます タイプ 1 文法、システム P でルール j à y が条件 j = j1Аj2 y = j1wj2 を満たす場合、

j、y、w - 辞書 V からのチェーン。

したがって、非終端記号 A は、j1 および j2 のコンテキスト内の空でない文字列 w に移動します (j1 および j2 は空の文字列にすることができます)。

タイプ 1 文法は次のように呼ばれます。 文脈に応じた.

文法はと呼ばれます 文法タイプ 2 - 文脈なし、ルール P のシステムでは次の形式のルールのみが許可される場合:

ここで、A は非終端記号です。

w は V からの空ではないチェーンです。

文法はと呼ばれます タイプ3文法、フォームのルールのみが許可される場合:

ここで、w = aB または w = a。

主要なクラスはサブクラスに分割できますが、それについては少し後ほど説明します。

LABORATORNAY WORK No.1

正式な文法と構文の作成

この作業の目的は、プログラミング言語の構造を研究し、それを正式な形式で記述することです。結果の文法に基づいて結論を導き、その正しさをチェックします。

基本情報

言語文法の作成

コンピューターの問題を解決するために現在使用されているプログラミング言語は、その構造とアルゴリズムの記述方法が互いに大きく異なります。これらの言語で書かれたプログラムをデバッグおよび実行する方法も異なります。

新しいプログラミング言語の設計と開発の基本原則は何ですか? コンピュータの問題を解決するために広く使用されるように設計された言語は、どのような要件を満たす必要がありますか? まず第一に、言語はプログラマにとって使いやすいものである必要があります。特に、学習が容易であり、最小限の時間でコンピュータ上で解決するための問題を準備する手段を備えている必要があります。一方、プログラムを処理するために必要なメモリ、問題を解決するのに必要なコンピュータ時間など、プログラムを使用したコンピュータの動作の特性を考慮する必要があります。残念ながら、これらの要件はある程度までは満たされません。、互換性が難しい。コンピュータにとって「便利」なことは、プログラマにとっては完全に便利ではないことが判明し、またその逆も同様です。しかし理由は原則として、どのタスクにも使用する言語の両方の要件が含まれるため、タスクを作成するときは、その言語を使用する際の両方の側面を考慮する必要があります。

以上をまとめると、次のような結論が得られます。プログラミング言語を作成するには、一方では言語の構造を形式的に記述でき、他方では可能であれば作成する言語のマシン要件を考慮できる数学的および理論的装置が必要です。

このようなデバイスの主な定義は、形式言語の定義です。あらゆるプログラミング言語は、文のセット、つまり辞書またはアルファベットと呼ばれる、空ではない有限の記号セットからの特定の連鎖または基本単位の有限シーケンスとして定義できます。プログラミング言語のこの見方は、プログラムの作成に使用できる記号のセットと、有効なプログラムまたは構文的に正しいプログラムのクラスのみを指定しており、それぞれの正しいプログラムの意味を指定する問題には取り組んでいません。正確に定義された文字列のセットという意味での「言語」という単語の使用と、日常会話でのその単語の使用を区別するために、文字列のセットは、次のように呼ばれることがあります。形式的な言語.

言語を指定するという上記の要件を満たすための通常のアプローチは、その言語の文が特定の規則に従って形成され、それらがまとめて言語の文法と呼ばれるものを構成するというものです。これらの文法規則は、言語の文に特定の構文構造を割り当て、文の意味を指定および決定する際に使用できます。

構文– 言語文の外部表現。

セマンティクス– 言語文の意味内容。

言語形式の構文を定義する一連の規則文法言語。

形式的な文法– 自然言語の文法の抽象的な一般化 – 文字列 (チェーン) を考慮します。

正式な文法は4重文です

G = ( V , V 、P、S)、

ここで、V は終端記号のアルファベットです。ルールの左側の部分に含めることができる記号 (単語と言語記号のセットに対応)。

V - 非終端記号のアルファベット (言語の一般化された概念のセットに対応)。

P - 形式の生成ルールのセット

ここで、 と  は終端記号と非終端記号のチェーンです。

S は文法の最初の記号（最初の概念に相当）です。

任意のチェーン    に対する文法 G は、そこから演繹可能なチェーンのセットを指定し、それらを次のように再帰的に定義します。  が P に含まれる場合、チェーン r =  は  から直接導出可能です (次のように示されます)。 r)、 が  と r から演繹可能である場合、r は  (  + r) から自明ではありません。   + r または =r の場合、r は  から演繹可能です (=*r)。申請の流れルール  1   2 ... r が呼び出されます結論 1 = S の場合、 r =  をチェーンします。

S から派生したチェーンは次のように呼ばれます。文章フォーム。非終端記号を含まない文形式は次のように呼ばれます。提案. たくさんのオファーフォーム言語、文法 G (L(G)) によって生成されます。

バッカス・ナウエ形式 R(BNF)

文法規則を記述するために広く使用されている形式は、Backus-Nauer 形式 (BNF) です。

バッカス正規形– 他のプログラミング言語の構文を記述するために特別に設計された言語。 Backus 形式の主な目的は、記述されているプログラミング言語の基本構造を記述するための厳密に形式的かつ明確なルールを簡潔かつコンパクトな形式で提示することです。

なぜなら言語のあらゆる文は、その言語の基本的な記号の連鎖と考えることができ、言語の構文を記述するバッカス形式を特定の順序で使用することにより、この言語で正しいプログラムを構築することが可能になります。

自然言語と同様にプログラミング言語の特徴は、複雑な構文構造が他の構造を構成要素として含むことです。したがって、TurboPascal プログラムは通常はブロックであり、ブロックには 1 つ以上の内部ブロックが含まれる場合があります。ブロックは、説明やステートメントを含む複雑な構造でもあります。後者にはコンポーネントなどもあります。したがって、プログラムを作成するには、プログラムに含まれるブロックやその他の構造をコンポーネントとして記述するためのルールを知る必要があります。 Backus 形式で使用されるオブジェクトの 2 番目のクラスは、まさに記述されている言語の構成要素の名前、またはいわゆるメタ言語変数です。メタ言語変数の意味は、記述された言語の基本的な記号の連鎖です。

各メタ言語公式は、特定の言語構造を構築するための規則を記述しており、2 つの部分で構成されます。左側には、対応する構造を示す金属言語変数 (非終端 (NT) 記号) があります。これに、記号  の代わりに挿入され、動詞「to be」の意味を持つ、いわゆるメタ言語接続詞:: = が続きます。式の左辺と右辺を結びます。式の右側は、左側で定義された構造を構築するための 1 つ以上のオプションを示します。各バリアントは、メタ言語変数と基本シンボル (ターミナル(T)) で構成されるチェーンです。数式で定義された構造を構築するには、数式の右側からいくつかの構築オプションを選択し、各金属言語変数の代わりに対応する数式を使用して、基本的なシンボルのいくつかのチェーンを使用する必要があります。式の右側のバリエーションは、「または」を意味するメタ言語接続詞 | で区切られています。

最後に、メタ言語変数は、山かっこで囲まれた単語または名前で表すことができることに注意してください。メタ言語変数の名前はプログラマによって割り当てられ、記述されている構造の意味を説明します (例: 算術式)。

バッカス・ナウアー形式で書かれた正式な文法の例。

整数の形成の文法を説明しましょう。各数値は 1 桁にすることができます。 5 という 1 桁で構成されますが、55 という複数桁にすることもできます。複数の数字で構成されます。複数桁の数値を形成するには、その構造自体をループする必要があります。

G1 数値記述文法には、次の 13 のルールが含まれています。

(1) 番号::= hs

(2) chs::= chs 桁

(3) chs::= digit

(4) 桁::= 0

(5) 桁::= 1

(6) 桁::= 2

(7) 桁::= 3

(8) 桁::= 4

(9) 桁::= 5

(10) 桁::= 6

(11) 桁::= 7

(12) 桁::= 8

(13) 桁::= 9

G1 = ((0,1,2,3,4,5,6,7,8,9), (桁, 数値, hs), P, 数値 ),

どこ最初に指定されたセット– 終端記号のアルファベット。

2 番目に指定されたセット– 非終端記号のアルファベット。

R- 上記の 13 のルール;

 番号 - 文法の最初の記号。

バッカス・ナウアー形式では、「or」オプションは記号「|」で記述されるため、文法は次のように記述する必要があります。

番号::= hs

時間::= 時間 桁 | 桁

桁::= 0|1|2|3|4|5|6|7|8|9

チョムスキー分類

文法はルールの種類に応じて分類できます。

文法には次の 4 種類があります。

句構造を備えた文法（自然言語はそれに基づいて構築されます）。

文脈依存文法 (各文形式の外観は、シンボルが配置されている文脈に依存し、特定の規則に従ってシンボルの連鎖に置き換えられます)。

コンテキストフリー (CF) 文法。各ルールの形式は次のとおりです。

   ここで、  V 、 はアルファベット V V のチェーンです ;

オートマトン文法。各ルールの形式は次のとおりです。

  x B または

  x、ここで

x  V、(,B)  V .

L = L(G) となる適切なタイプの定義文法 G が存在する場合、言語 L はオートマトン、文脈自由、文脈依存、またはフレーズ構造であると言われます。

形式的な文法または単に文法形式言語の理論において - 形式言語を記述する方法、つまり、特定の有限のアルファベットのすべての単語のセットから特定のサブセットを分離する方法。区別する 生成するそして 認識する（または 分析的) 文法 - 1 つ目は言語の任意の単語を構成するための規則を設定し、2 つ目は特定の単語からその言語に含まれるかどうかを判断できるようにします。

条項

端子（端子記号）- 文法に対応する言語の単語に直接存在し、特定の不変の意味を持つオブジェクト（「文字」の概念の一般化）。コンピュータで使用される形式言語では、標準の ASCII 文字 (ラテン文字、数字、特殊記号) のすべてまたは一部が通常、端子として扱われます。シンボル。
非終端 (非終端記号)- 何かを表すオブジェクト エッセンス言語 (例: 式、算術式、コマンド) であり、特定の記号的な意味を持ちません。

生成文法

文法で指定された言語の単語は、すべて最初の非終端語から推論規則に従って出力（生成）された終端語の列です。

文法を定義するには、終端文字と非終端文字のアルファベット、一連の推論ルールを指定し、非終端文字のセットの最初のものを選択する必要があります。

したがって、文法は次の特性によって定義されます。

結論

出力は終端と非終端で構成される行のシーケンスです。最初の行は 1 つの非終端で始まる行で、後続の各行は、(任意の) 条件に従って特定の部分文字列を置き換えることによって前の行から取得されます。）のルール。最後の行は完全に端子で構成される行であり、したがって言語の単語です。

特定の単語の派生語の存在は、その単語がその文法で定義された言語に属するかどうかの基準になります。

文法の種類

ターミナルのアルファベット:

Σ (\displaystyle \シグマ) = {"0","1","2","3","4","5","6","7","8","9","+","-","*","/","(",")"}

非終端アルファベット:

(式、記号、数字、数字)

1. 計算式 → (\displaystyle \to ) FORMULA SIGN FORMULA (式は 2 つの式を記号で接続したものです) 2. FORMULA → (\displaystyle \to ) NUMBER (式は数字です) 3. FORMULA → (\displaystyle \to )(FORMULA) (カッコ内は式です) 4. SIGN → (\displaystyle \to )+ | - | * | / (符号はプラスまたはマイナス、または乗算、または除算) 5. NUMBER → (\displaystyle \to ) DIGIT (数字は数字です) 6. NUMBER → (\displaystyle \to ) NUMBER DIGIT (数字は数字と数字です) 7. DIGIT → (\displaystyle \to ) 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (数字は 0 または 1、または... 9)

初期の非終端:

式

結論:

リストされた導出規則を使用して、式 (12+5) を導出してみましょう。明確にするために、各置換の側面はペアで示されており、各ペアでは置換された部分に下線が付けられています。

式 → 3 (\displaystyle (\stackrel (3)(\to ))) （式） (式) → 1 (\displaystyle (\stackrel (1)(\to ))) (数式の記号数式）（式サイン式） → 4 (\displaystyle (\stackrel (4)(\to )))（式 + 式) (式 + 式) (式 + 番号) (式 + 番号) (式 + 番号) (式 + 番号) (式 + 5 ) (式 + 5) → 2 (\displaystyle (\stackrel (2)(\to ))) (番号 + 5) (番号 + 5) → 6 (\displaystyle (\stackrel (6)(\to ))) (数字の桁 + 5) (番号数字 + 5) → 5 (\displaystyle (\stackrel (5)(\to ))) (番号数字 + 5) ( 番号数字 + 5) → 7 (\displaystyle (\stackrel (7)(\to ))) (1 数字 + 5) (1 番号 + 5) → 7 (\displaystyle (\stackrel (7)(\to ))) (1 2 + 5)

注釈: このセクションでは、この分野の基本である「形式文法」について説明します。この分野は記号を使ったあらゆる操作を考慮しており、その結論は人工知能だけでなく形式言語や「人間」言語の分析にも広く使用されています。この講義はこの講座の中で最も重要であると同時に、最も理解するのが難しい講義です。この点に関して、著者は数学的証明を省略し、結論だけを読者に提示します。内容をより深く理解するために、前後の講義の資料を参照する必要がある場合があります。

10.1. アルファベット

人はどんな言語でもアルファベットから学び始めます。で正式な文法言語はその意味とは無関係に定義されます。さらに、同じ言語が複数の文法によって形成されることもあります。それは学校のようなものです - 結果（教科書の最後で読むことができます）は、その領収書、つまりノートに記録された問題の解決策ほど重要ではありません。したがって、アルファベットの定義にも形式的にアプローチしてみましょう。

意味。アルファベットは空ではない有限の要素セットです。

「古典的」言語では、アルファベットは文字の集合です。音声学において、人間が発する一連の音声。音楽では、音符の集合などを指します。

多くの場合、アルファベットを使用して説明できます。無限集合言葉文法を使用して作成できる (つまり、文法によって生成された) すべての単語の集合を言語と呼びます。アルファベットとは異なり、言語は無限です。

どれでも最終シーケンスアルファベット文字ワード、またはより専門的にはチェーンと呼ばれます。文字 (a、b、c) で構成されるチェーンは、a、b、c、aa、ab、bc、ac、bb、abba などのシーケンスになります。空のチェーン A の存在、つまりシンボルが完全に存在しないことも許可されます。チェーン内の文字の順序も重要です。したがって、チェーン ab と ba は別のチェーンです。さらに、大文字のラテン文字は変数およびシンボルとして使用され、小文字のラテン文字はチェーンを示します。例えば：

X = SVT リスト 10.1。

文字 S、V、T の順序で構成される文字列。

意味。チェーンの長さは、このチェーン内の文字の数です。 |x| と表されます。。例えば： |L| = 0、|A| = 1、|BA| = 2、|ABBA| = 4.

x と y が文字列の場合、それらを連結すると文字列 xy になります。連結中にチェーンを再配置すると、結果が変わります (群理論の場合と同様)。 z = xy がチェーンの場合、x はチェーンの先頭、y は末尾になります。チェーンの先頭を気にしない場合は、次のように表します。

Z = … x リスト 10.2。

尾部を気にしない場合は、次のように書きます。

Z = x ...リスト 10.3。

意味。 2 セットのチェーンの積は、これらのセットに含まれるすべてのチェーンの連結として定義されます。たとえば、A = (a, b)、B = (c,d) と設定すると、次のようになります。

AB = (ac、ad、bc、bd) リスト 10.4。

集合の積では、連結と同様に、因数の順序が重要です。

チェーンを連結する場合とチェーンのセットを乗算する場合の両方で、次のように記述される結合法則が当てはまります。

Z = (ab)c = a(bc) = abc リスト10.5.

D = (AB)C = A(BC) = ABC リスト 10.6.

そして最後に、連鎖の次数を決定します。 x が空ではないチェーンの場合、 x 0 = (L)、x 1 = x、x 2 = xx、x n = x(x) (n-1)。集合の次数についても同様です。

10.2. 終端記号と非終端記号

端末のコンセプトと非終端記号これは、置換 (または生成) ルールの概念と密接に関連しています。定義しましょう。

意味。生成ルール、または置換ルールは、順序付きペア (U、x) であり、次のように記述されます。

U::= x リスト 10.7。

ここで、U はシンボル、x は空でない有限です。文字列.

右側のみに登場する文字をこう呼びます。終端文字。ルールの左側と右側の両方にある記号は、非終端記号、または言語の構文単位と呼ばれます。たくさんの非終端記号 VN として示され、終端文字-VT。

注記。この端末の定義と非終端記号 KS 文法と A 文法については true (セクション 10.4.3 を参照)。

意味。文法 G[Z] は、次の内容を含む有限で空ではないルールのセットです。非終端記号一連のルールで少なくとも 1 回は Z を実行します。 Z 文字は開始文字と呼ばれます。次はみんなで非終端記号それを次のように表します<символ>.

【例01】

文法：「数字」

<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9

別の定義を与えてみましょう。

意味。次の場合、チェーン v はチェーン w を直接生成します。

V=x y と w = xuy リスト 10.8.

どこ ::= u は文法規則です。これは v => w と表されます。また、w は v から直接演繹可能であるとも言います。この場合、チェーン x と y は空であってもかまいません。

意味。次のような出力 u0、u1、…、u[n] (n > 0) の有限連鎖がある場合、v が w を生成する、または w が v に還元されると言います。

V = u0 => u1 => u2 => ... => u[n] = w リスト10.9.

このシーケンスは長さ n のピンと呼ばれ、v =>+ w で表されます。そして最後に彼らはこう書いています。

V =>* w if v => w または v =>+ w リスト 10.10.

10.3. フレーズ

意味。 G[Z] を文法、x を文字列とします。次に、次の場合、x は文形式と呼ばれます。 =>* × 。センテンスは、次のものだけで構成される文形式です。終端文字。言語は、すべての端末チェーンのセットのサブセットです。

意味。 G[Z]を文法とする。そして、w = xuy を文形式とします。その場合、u は文形式 w のフレーズと呼ばれます。非終端記号、もし：

Z =>* x yと =>+ u リスト 10.11。

Z =>* x yと => u リスト 10.12。

この場合、文字列 u は単純フレーズと呼ばれます。

「フレーズ」という言葉には注意が必要です。事実 =>+ u (チェーン u は次から推定できます) ) は、u が文形式 x の文であることを意味するものではありません y; も必要です連鎖演繹性バツ文法 Z の最初の記号からの y。

このフレーズを説明するために、[例 01] という文形式を考えてみましょう。<чс>1. これは、シンボルが<чс>ルールがある場合のフレーズです。<число> ::= <чс>? もちろん、連鎖は不可能なので、そうではありません。<число><1>- 最初の文字から:<число>。文形式の文章とは何ですか?<чс>1? 次の出力を考えてみましょう。

<число> => <чс> => <чс><цифра> => <чс><1>リスト10.13。

したがって、

<число> =>* <чс>そして<чс> =>+ <чс>1 リスト 10.14。

正式なシステムの 1 つは、置換システムまたは Thue 半システム (ノルウェーの数学者 Axel Thue にちなんで命名されました) で、アルファベット A と次の形式の置換の有限セットによって定義されます。

ここで、α i 、β i は単語であり、A では空である可能性があり、Þ はワイルドカード記号であり、以前は「暗示」、「推定」として理解されていました。

Thue システムは次の形式の関係を使用します。

置換のペアとして理解されます。

α i Þ β i (左);

β i Üα i (右)。

Thue 半システムでは、置換 α i β i は推論規則 R i として解釈されます。 50 年代のアメリカの数学者 N. チョムスキーは、これらの半システムを使用して、いわゆる形式文法の理論を形成し、発展させました。これは、その特殊なケースです。

V を空ではない記号の集合、つまりアルファベット (または辞書) とし、したがって、アルファベット V 内のすべての有限単語の集合 V * が与えられるとします。アルファベット V 内の形式言語 L は、V * の任意の部分集合です。。したがって、V にロシア語の文字、句読点、スペース文字などが含まれている場合、V * は、偉大なロシア文学 (既成および将来の) のすべての作品を含む仮想のセットになります。

単語、数学記号、幾何学的な画像なども記号として使用できます。

言語が指定または決定されている文法– 特定の言語のすべてのチェーンを生成し、それらのみを生成するルールのシステム。

形式文法 – 形式体系、微積分。

形式文法の認識、生成、変換があります。

認識する、指定された文字列について、その文字列が指定された文法の意味で正しいかどうかを判断します。

形式文法と呼ばれる 原動力正しいチェーンを構築できれば。

形式文法と呼ばれる 変革的な正しく構築されたチェーンの場合、そのマッピングは正しいチェーンの形式で構築されます。

生成形式文法のクラスを考えてみましょう。

G の生成形式文法は 4 倍です。

G= ,

ここで、T は有限の終端 (メイン) シンボルの空でない有限の集合です。

N – 非終端 (補助) シンボルの有限の空でないセット。

P – 有限の空ではない推論ルールのセット (生成物)。

S は開始文字です。

T – 終端辞書 – 文法によって生成されたチェーンが構築される最初の記号のセット。

N – 非終端辞書 – ソースシンボルのクラスを示す補助シンボルのセット。

有限集合は文法 G の完全な辞書です。

推論ルールは、φÞψ の形式の空ではない有限の二項関係のセットです。ここで、φ と ψ は辞書 V 内のチェーンであり、記号 Þ は「置換」を意味します。

α=α 1 φα 2 , β=α 1 ψα 2 , (φÞψ ）。

連鎖 β は、「i =0,1,...,n-1 E i => E i +1。

このシーケンスは α からの出力 β と呼ばれ、n は出力の長さです。

α からの β の演繹可能性は、α=> n β で表されます (導出の長さを指定する必要がある場合)。

文法 G によって生成される言語 L(G) は、S から導出された端末辞書 T 内の文字列のセットです。ここで、S は、この文法が対象とする言語オブジェクトのクラスを示す最初の記号です。最初の記号は文法の目標またはその公理と呼ばれます。

L(G)=L(G 1) の場合、文法 G と G 1 は同等です。

形式文法の理論の観点から自然言語を記述する場合、終端記号は単語または形態素（言語の意味のある最小単位（語根、接尾辞など））、非終端記号は単語のクラスの名前として解釈され、語句 (主語、述語、述語群など .P.)。通常、文字列は自然言語文として解釈されます。

例1。文法を次のように与えます。

T-(a,b)、N-(S,A,B)、S-S、

P=(1.SÞaB; 2.SÞbA; 3.AÞaS; 4.AÞbAA; 5.AÞa; 6.BÞbS; 7.BÞaBB; 8.BÞb)。

提案の典型的な結論:

使用される推論ルールの番号は、矢印の上の括弧内に示されています。出力は終了します。左辺が ab に等しいルール P はありません。

このような生成文法のグラフを図に示します。 125.

米。 125. 生成文法グラフ

ここで、a と b は最終頂点 (端子) です。

例 2。文法を次のように与えます。

T=(<студент>, <прилежный>, <ленивый>, <выполняет>, <не выполняет>, <домашнее задание>};

N=(<сказуемое>, <подлежащее>, <определение>, <дополнение>, <группа подлежащего>, <группа сказуемого>, <предложение>};

チェーンを出力することができます<прилежный> <студент> <выполняет> <домашнее задание>.

明らかに、最後の推論チェーンは最終的なものであり、自然言語文を表します。同様に、チェーンを導出することができます<ленивый> <студент> <не выполняет> <домашнее задание>。この例では、非終端記号は構文上のカテゴリであることに注意してください。

出力は、図に示すいわゆる構造ツリーによって記述することもできます。 126.

米。 126. 文章出力の構造ツリー

文法は、パスカル言語のような、いわゆる Wirth 構文図によって指定することもできます。これは、シンボルの代わりに、直列接続がチェーンを示し、並列接続がチェーンの変形を示すスイッチング回路に似ています。

したがって、形式文法は認識、生成、変換することができます。また、形式文法の理論では、4種類の文法から生成される4種類の言語があるとされています。文法は、規則体系 R に徐々に増加する制限を課すことによって区別されます。

文法とそれが生成する言語の一般に受け入れられている分類はチョムスキー階層であり、4 種類の文法が含まれています。

タイプ 0 文法は、推論規則 jÞy に制限が課されていない文法です。ここで、j と y は V の任意の文字列です。このような文法は、チューリングマシンによって実装できます。この場合、チューリングマシンの状態は非終端 (補助) シンボルに対応し、テープ上のシンボルは終端シンボルに対応します。チェーンを生成するためのルールは、コマンドシステムによって記述されます。

型文法 1 は文法であり、そのすべての規則は aАbÞawb の形式を持ちます。ここで、wÎТUN、A は非終端記号です。チェーン a と b はルールのコンテキストです。使用しても変化しません。したがって、タイプ 1 の文法では、a と b のコンテキストでのみ、単一の終端記号 A が空ではない文字列 w (A は w に置き換えることができます) に入ります。タイプ 1 文法は、文脈依存型または文脈依存型と呼ばれます。

タイプ 2 文法は、AÞa 形式のルールのみが許可される文法です。ここで、aÎТUN、つまり a は V の空でないチェーンです。タイプ 2 文法は、コンテキストフリーまたはコンテキストフリーと呼ばれます。最新のアルゴリズム言語は、文脈自由文法を使用して記述されます。

型文法 3 – АÞaB または AÞb の形式のルールがあります。ここで、А、ВОN。ああ、BÎT。

ここで、A、B、a、b は、対応する辞書の単一文字 (連鎖ではない) です。このタイプの文法によって定義される言語は、と呼ばれます 自動または定期的に。

この場合、次の形式の正規表現言語 (正規言語) が使用されます。

このような言語は有限オートマトン (クリーンの定理) によって与えられます。ほとんどのアルゴリズム言語では、式は有限状態マシンまたは正規表現を使用して指定されます。

有限オートマトンで正規言語を指定する例を考えてみましょう。

X=(0,1) – 入力シンボルのセット。

Y=(S,A,B,q k ) – 内部状態のセット、q k – 最終状態、S – 初期状態。

場合によっては、いくつかの最終状態が考慮され、集合 F に結合されます。この場合、F = (q k ) となります。

j: 遷移関数 – 非決定的:

有限非決定オートマトンの遷移グラフを図に示します。 127.

米。 127. 有限非決定性オートマトンの遷移グラフ

対応する生成文法は次のとおりです。

対応する正規言語 L= :

0, 010, 01010,...

形式文法の理論はコンパイラの構築に使用されます。コンパイラはソースプログラムを解析します。同時に、与えられた文字列が正しく構成された文であるかどうかが判断され、正しく構成されている場合には、その形式が復元されます。解析または構文解析は、特別なプログラムであるパーサー（解析するための）によって実行されます。この問題を解決するために、LEX や YACC などの特別なプログラムが開発されました。

UNIX オペレーティングシステムには標準プログラム LEX および GREP があり、これらは正規言語理論に基づいて構築されています。

LEX プログラムはテキストの字句解析を実行し、特定の正規表現セットに従ってテキストを分解します。

GREP プログラム - 正規表現を使用してパターンを選択します。つまり、入力シンボルストリームからのシンボルが供給される有限状態マシンを構築しながら、1 つ以上のファイルでコンテキスト検索を実行します。

ある言語から別の言語への自動翻訳システムでは、主語、述語、定義、補語が識別されます。その後、必要な言語の規則に従って、対応する提案が作成されます。

現在、コンピュータでは Promt、Magic Gooddy、Socrat Personal などのトランスレータが使用されています。さらに、.Context、Socrat Dictionary、MultiLex などの単純な辞書が使用されます。

形式文法を使用した言語知識の表現は、知識表現一般のモデルの 1 つであり、人工知能の要素を備えたシステムなどの分野で使用されます。知識はデータとは異なり、例えば、データは対応するコンピュータプログラムによってのみ有意義に解釈され、知識には有意義な解釈の可能性が常に存在することに留意すべきである。自然言語または自然言語に近い言語でユーザーとのインターフェイスを提供するシステムのソフトウェアおよびハードウェア部分が実装されている 言語処理者、そのタスクは、自然言語テキストを、コンピューターが動作する内部表現の形式言語に直接翻訳および逆翻訳することです。

日本ではすでに、飼い主とコミュニケーションが取れる家庭用「おしゃべり」ロボットの販売を始めている企業もある。

言語プロセッサには宣言部分と手続き部分があります。 1 つ目には辞書の説明が含まれ、2 つ目には自然言語テキストの分析と合成のためのアルゴリズムが含まれます。

知識を表現するための論理モデルは、命題と述語の計算としてすでに知られています。

特定の主題領域に関する意味論的 (概念的) 知識を形式化するための基礎は、いわゆる意味論的ネットワークです。セマンティックネットワークは有向グラフであり、その頂点は特定のオブジェクトに関連付けられ、アークはそれらの間のセマンティック関係に関連付けられます。頂点ラベルは本質的に参照であり、特定の名前を表します。名前の役割は、たとえば、自然言語の単語である可能性があります。円弧ラベルは、一連の関係の要素を示します。さらに、フレームは知識を表すために使用されます。フレームは、典型的な状況を表すデータ構造として定義されることがほとんどです。

ゲーデルの定理

数学的論理では、述語計算が一貫していることが証明されています。と、を同時に表示することはできません。さらに、述語計算の完全性に関するゲーデルの定理により、述語計算では一般に有効な公式が演繹可能です。

考慮される述語計算は、一次述語計算です。二次微積分では、述語による量指定子が可能です。「P(P(x))」の形式の式、または関数による。

したがって、命題論理のすべての真のステートメントのセットは数えることができ、決定可能です。述語論理のすべての真のステートメントのセットは (その完全性により) 数えることができますが、(主題領域が無限であるため) 決定することはできません。

数理論理学におけるもう一つの形式理論として、イタリアの数学者ジュゼッペ・ペアノ（１８５８－１９３２）が提唱したいわゆる形式算術が考えられる。ペアノは記号と演算 Î、U、I を導入し、論理を数学的学問として初めて提示しました。数学を論理に還元する最初の試みは、ドイツの数学者で論理学者のゴットリープ・フレーゲ (1848-1925) によって行われました。セットを概念のボリュームとして定義したのは彼でした。彼はこう書いている。「算術は論理の一部であり、証明の基礎を経験や思索から借用すべきではない。」全集合の集合に関する有名なパラドックスは、バートランド・ラッセルによって特定されたフレーゲの体系の矛盾です。

ゲーデルは、形式的な算術を含む形式理論 T は不完全であることを証明しました。つまり、形式理論 T には、真であるような閉じた式 F が含まれていますが、F も T から導出することもできません。ゲーデルの有名な不完全性定理によると、形式的な算術を含む形式理論 T については、次のようになります。 T の無矛盾性を表す式は T では証明できません。

したがって、算術と整数論は非極大化理論であり、算術のすべての真の記述の集合は数えられません。

ゲーデルの定理は方法論的に重要な意味を持っています。十分に豊かな数学理論には、適切な形式化が存在しないことがわかります。確かに、不完全な理論 T は、真であるが T で導出できない公式を公理として追加することで拡張できます。ただし、新しい理論も不完全になります。さらに、形式理論自体の手段を使用して理論のメタプロパティを研究することは不可能です。あらゆるメタ理論 T は、少なくとも一貫性を証明できるためには、T よりも豊かでなければなりません。

したがって、唯一正当であると宣言できる一定の手段のセットとして数学を構築し、それらの助けを借りてあらゆる理論のメタ理論を構築するというアプローチ自体が疑問視されています。しかし、これは決して形式的なアプローチの崩壊ではありません。解決できない問題が存在するからといって、建設的なアプローチが適切ではないというわけではありません。それができないのは、それができる人がいないだけです。

実質的に定義された理論の完全な形式化が不可能であることは、概念の欠陥ではなく、いかなる概念によっても排除することができない客観的事実です。

理論を適切に形式化することが不可能であるということは、その理論の形式化可能な断片を探すか、より強力な形式理論を構築する必要があることを意味します。ただし、その理論はやはり不完全ではありますが、おそらく元の理論全体が含まれることになります。

非古典論理