形式的な言語について詳しく解説

多くの文脈 (科学、法律など) において、形式言語は、日常言語よりも形式的で正確な表現方法 (この 2 つは必ずしも連携しているわけではありません) を指します (自然言語を参照)。

厳密な論理規則 (正式な文法または構文と呼ばれる) に従う一連の単語。
基礎的なセマンティクスの。

形式言語の強みは、意味論を抽象化できることであり、これにより理論が複数のモデルで再利用可能になります。したがって、給与または逆行列の特定の計算は常に給与または逆行列の計算のままですが、群に関する定理はルービックキューブの変換と同様に整数の集合にも適用されます。

フォーマルな言語、仕事のツール

科学分野の形式言語は、厳密な形式構文に従う言語であり、記述を正確に、できれば簡潔かつ明確な方法で表現するために使用されます。これは自然言語と対照的です。

形式言語と自然言語

形式言語には、ステートメントの操作と変換が容易になるという利点があります。変換されたステートメントの意味や変換の意味を知らなくても、正確な変換規則 (論理式の展開、正規形、対偶、可換性、結合性など) を適用できます。これは強力な探索ツールであり、機械に「数学を行う」ことを可能にする唯一の言語です。

欠点は明らかです。ステートメントの意味がわからないと、関連する変換が何であるかを知ることができず、推論の直観が損なわれます。したがって、形式言語ステートメントをすばやく読み、それを 1 つ以上の意味のある自然言語ステートメントにすばやく翻訳する方法を知っておくとよいでしょう。

コンピュータを使った理解

コンピューティングの初期から、研究者はコンピュータの外部形式から内部形式に移行するために、言語の翻訳を支援するツールを開発してきました。最もよく知られているツールはLex と Yaccです。他の研究者はプログラミング言語のセマンティクスを定義しました。

数学と科学の歴史の中で

20^世紀以前

数学は古代から存在していましたが、その表現方法は大きく進化しました。

他の学問分野と同様に、その学問分野の言語は明らかに学問そのものよりも前から存在していたわけではありません。したがって、数学用に構築されていない言語を使用する必要があり、少しずつ特定の専門用語が強化されました。

したがって、今日の私たちにとって、古代の数学的記述の多くは、特定の概念を表す言葉がない場合、周辺表現が過剰に詰め込まれた、かなり複雑な定式化を持っているように見えます。

したがって、専門用語は何世紀にもわたって充実し、進化し続けています。

この現象と並行して、正式な言語が徐々に形成され、それが私たちが知っているものになりましたが、自然な専門用語は十分に正確でも簡潔でもないことが判明しました。

20^世紀には

20^世紀初頭、数学者のデイヴィッドヒルベルトと彼とともに形式主義者たちは、一般的な公理化と共通の形式言語の使用を通じて数学を統一できると信じていました。

この数学観は 1931 年に論理学者クルトゲーデルが、算術を含む形式体系には少なくとも 1 つの決定不可能な命題が存在するという有名な不完全性定理を発表したときに弱体化しました。

形式言語に戻ると、この定理の結果は次のとおりです。形式言語、その公理、および算術を表現できる形式演繹システムが与えられると、このシステムでは証明できないこの言語の命題を述べることができます。そしてその否定も。数学をどれだけ形式化しても、その実証ではこの形式主義を離れるか、新しい公理を追加して拡張する必要がある形式的なステートメントが常に見つかります。これにより、必然的に新しい決定不可能なステートメントが導入されます。このように、形式主義的アプローチは依然として有効ではありますが、今や限界があることがわかっています。

²⁰世紀後半、コンピューターと情報技術の出現により、比較的新しい形式言語がツールとして、また研究の対象として特別な地位を与えられました。

現在（ 21^世紀初頭）

数学の論文では形式言語と自然言語の両方が使用されます。形式的な言語は、広範な説明を必要としないほど単純な技術的な文章や記述のために予約されており、重要な結果は形式的な言語と自然言語の両方で説明されることがよくあります。

この記事では、現代の数学形式言語について説明します。

形式言語、研究対象

形式言語は、論理および理論的コンピューターサイエンスの別の分野の研究対象でもあります。この研究は計算可能性の理論と強く結びついています。実際、言語としての形式言語の特徴は、コンピュータまたはその形式モデルであるチューリングマシンによって処理できることです。

定義

研究の対象として、形式言語は、ある有限のアルファベット、つまりこのアルファベット上の自由モノイドの一部から推定される有限長の単語 (つまり文字列) の集合として定義されます。

通常、アルファベットは { a , b } となり、そのアルファベット上の単語はababbaになります。

このアルファベット上の典型的な言語であり、この単語が含まれる言語は、同じ数の記号aとb を含むすべての単語のセットになります。

空のワード(長さ 0 のワード) が許可され、ε で示されます。アルファベットは有限の集合であり、各単語の長さは有限ですが、言語には無限に多くの単語が含まれる可能性があります (単語の長さに制限がないため)。

例

形式言語の例をいくつか示します。

{ a , b } 上の単語のセット、
集合 { a ⁿ : nは素数}、
指定されたプログラミング言語の構文的に正しいプログラムのセット、
特定のチューリングマシンが停止する入力単語のセット。

形式言語の構築

形式言語は、次のようなさまざまな方法で指定できます。

形式文法規則としても知られる生成規則によって生成される単語 (言語の分類を参照)、
正規表現によって生成された単語、
チューリングマシンや有限状態オートマトンなどの特定のオートマトンによって受け入れられる単語、
答えが「YES」である意思決定問題のインスタンスのセット、
推論結果。

いくつかの操作を使用して、既知の言語から新しい言語を作成できます。 L1とL2_が共通のアルファベットの言語である_と仮定します。

L ₁とL ₂の連結は、 vw という形式の単語のセットです。ここで、 vはL ₁の単語、 w はL ₂の単語です。評価:
$$ {L_1\cdot L_2} $$
またはL1 _L2 _。
L1とL2の共通部分は_、 L1_とL2 の両方_にある単語のセット_です。評価:
$$ {L_1\cap L_2} $$
。
L ₁とL ₂の和集合は、 L ₁またはL ₂のいずれかにある単語のセットです。評価:
$$ {L_1\cup L_2} $$
またはL ₁ + L ₂ 。
言語L ₁の補語は、そのアルファベット上の、 L ₁に含まれない単語のセットです。
Ｌ _１とＬ _２の右側の商は、Ｌ _２の単語ｗが存在する単語ｖの集合であり、 ｖｗはＬ _１に属する。表記： _L1 / _L2 。
L ₁のKleene 閉包は、書くことができる単語のセットです
$$ {w_1 w_2 \dots w_n} $$
と
$$ {w_1,w_2, \dots w_n \in L_1} $$
そして
$$ {n\ge 0} $$
。 n = 0 が許可されるため、このセットにはストップワード ε が含まれます。評価:
$$ {L_1^\star} $$
。
L ₁の反転には、 L ₁の単語が逆向きに書かれたものが含まれます。評価:
$$ {{L_1}^R} $$
。
L ₁とL ₂を組み合わせたものが書ける単語のセットです
$$ {v_1 w_1 v_2 w_2 \dots v_n w_n} $$
または
$$ {n\ge 1} $$
、
$$ {v_1 v_2 \dots v_n} $$
はL1のワードであり_、
$$ {w_1 w_2 \dots w_n} $$
はL2_ワードです。

メンバーシップ、計算可能性、複雑さ

形式言語に関してよくある質問は次のとおりです。

特定の単語がこの言語に属するかどうかをアルゴリズム的に決定できるでしょうか?
もしそうなら、そのような答えはアルゴリズム的にどれくらい複雑ですか?

これらの質問は、計算可能性理論と複雑性理論の分野に分類されます。