正式な言語

文法的には正しく構成されているが、完全に無意味な英語の文「無色の緑の思想は激しく眠る」の構造（チョムスキー1957の歴史的例）

論理学、数学、コンピュータサイエンス、言語学において、形式言語とは、「アルファベット」と呼ばれる集合から記号が取られた文字列の集合です。

形式言語のアルファベットは、文字列（「単語」とも呼ばれる）に連結される記号で構成されています。 ^{[ 1 ]}特定の形式言語に属する単語は、整形式の単語と呼ばれることもあります。形式言語は、正規文法や文脈自由文法などの形式文法によって定義されることがよくあります。

コンピュータサイエンスにおいて、形式言語は、とりわけ、プログラミング言語の文法や自然言語のサブセットの形式化されたバージョンを定義するための基礎として用いられ、そこでは言語の単語が意味またはセマンティクスに関連付けられた概念を表現する。計算複雑性理論では、決定問題は典型的には形式言語として定義され、複雑性クラスは限られた計算能力を持つ機械によって解析できる形式言語の集合として定義される。論理学および数学の基礎においては、形式言語は公理系の構文を表現するために用いられ、数学的形式主義とは、すべての数学はこのように形式言語の構文的操作に還元できるという哲学である。

形式言語理論の分野は、主にそのような言語の純粋に統語的な側面、すなわち内部構造パターンを研究する。形式言語理論は、自然言語の統語的規則性を理解するための方法として、言語学から生まれた。^{[ 2 ]}

歴史

17世紀、ゴットフリート・ライプニッツは、象形文字を用いた普遍的かつ形式的な言語である「キャラクタリスティック・ユニバーサリス」を構想し、記述しました。その後、カール・フリードリヒ・ガウスはガウス符号の問題を研究しました。^{[ 3 ]}

ゴットロープ・フレーゲは、ライプニッツの思想を、1879年の『記号論』（Begriffsschrift）で初めて概説され、 1893/1903年に2巻からなる『算術基本法』（Grundgesetze der Arithmetik）でより詳細に展開された記法体系を通して実現しようと試みた。^{[ 4 ]}これは「純粋言語の形式言語」を記述した。^{[ 5 ]}

20世紀前半には、形式言語に関連するいくつかの発展がありました。アクセル・トゥーは1906年から1914年にかけて、単語と言語に関する4つの論文を発表しました。これらの論文の最後のものは、エミール・ポストが後に「トゥーシステム」と呼ぶものを導入し、決定不能問題の初期の例を示しました。^{[ 6 ]}ポストは後にこの論文を基礎として、1947年に「半群の単語問題は再帰的に解決不可能である」という証明を行い、^{[ 7 ]}形式言語を作成するための 標準的なシステムを考案しました。

1907年、レオナルド・トーレス・ケベドはウィーンで機械図面（機械装置）の記述のための形式言語を導入した。彼は「機械の記述を容易にするための表記法と記号のシステムについて」（Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas）を出版した。^{[ 8 ]}ハインツ・ゼマネクはこれを工作機械の数値制御用プログラミング言語と同等と評価した。 ^{[ 9 ]}

ノーム・チョムスキーは、チョムスキー階層として知られる形式言語と自然言語の抽象表現を考案しました。^{[ 10 ]} 1959年にジョン・バッカスは、FORTRANの作成に続いて、高級プログラミング言語の構文を記述するためにバッカスナウア形式を開発しました。^{[ 11 ]}ピーター・ナウアはALGOL60レポートの秘書/編集者であり、その中でバッカスナウア形式を使用してALGOL60の形式部分を記述しました。

アルファベットを超える言葉

形式言語の文脈において、アルファベットは任意の集合であり、その要素は文字と呼ばれます。アルファベットは無限個の要素を含むことができます。 [^{注1 ]}しかし、形式言語理論におけるほとんどの定義では、有限個の要素を持つアルファベットが指定されており、多くの結果は有限個の要素を持つアルファベットにのみ適用されます。多くの場合、通常の意味でのアルファベット、あるいはより一般的にはASCIIやUnicodeなどの有限の文字エンコーディングを使用することが理にかなっています。

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

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

意味

空でない集合 が与えられたとき、上の形式言語は の部分集合であり、 は上のすべての可能な有限長単語の集合である。この集合を のアルファベットと呼ぶ。一方、上の形式言語が与えられたとき、 のとき単語は整形式である。同様に、 のとき式は整形式である。上の形式言語には、からすべての可能な整形式の単語を作成するための明確な規則と制約の集合が存在する場合がある。 ${\displaystyle \Sigma }$ ${\displaystyle L}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle \Sigma }$ ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle w\in L}$ ${\displaystyle E\subseteq \Sigma ^{*}}$ ${\displaystyle E\subseteq L}$ ${\displaystyle L}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma^{*}}$

コンピュータサイエンスや数学では、自然言語を扱わないことが多いため、「形式的な」という形容詞は冗長として省略されることが多い。一方、文脈から その言語のアルファベットが明らかな場合は、「形式言語」とだけ言うこともできる。${\displaystyle L}$ ${\displaystyle \Sigma }$

形式言語理論は通常、何らかの統語規則によって記述される形式言語を扱いますが、「形式言語」という概念の実際の定義は、上記の通り、与えられたアルファベットから構成される有限長の文字列の（おそらく無限の）集合であり、それ以上でもそれ以下でもありません。実際には、正規言語や文脈自由言語など、規則によって記述できる言語は数多く存在します。形式文法の概念は、統語規則によって記述される「言語」という直感的な概念に近いかもしれません。定義を誤用すると、特定の形式言語は、それを記述する形式文法を伴うと考えられることがよくあります。

例

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

• 「+」または「=」を含まず、「0」で始まらない空でない文字列はすべて Lに含まれます。
• 文字列「0」は Lにあります。
• 「=」を含む文字列が Lに含まれるのは、「=」が 1 つだけ存在し、それがLの 2 つの有効な文字列を区切っている場合のみです 。
• 「+」を含み「=」を含まない文字列が Lに含まれるのは、文字列内のすべての「+」がLの 2 つの有効な文字列を区切る場合のみです 。
• 前の規則によって暗示される文字列以外の文字列は 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 は自然数の範囲であり、「a ⁿ」は「a」がn回繰り返されることを意味します（これは記号「a」のみで構成される単語の集合です）。
• 特定のプログラミング言語で書かれた構文的に正しいプログラムの集合（その構文は通常、文脈自由文法によって定義される）。
• 特定のチューリングマシンが停止する入力の集合。または
• この行にある英数字ASCII文字の最大文字列の集合、つまり集合 {the, set, of, maximal, strings, alphanumeric, ASCII, characters, on, this, line, i, e}。

言語仕様の形式主義

形式言語は様々な分野でツールとして用いられます。しかし、形式言語理論は特定の言語（例として扱う場合を除く）に焦点をあてることはほとんどなく、主に言語を記述するための様々な形式主義の研究に焦点をあてています。例えば、ある言語は次のように表すことができます。

• 何らかの形式文法によって生成された文字列。
• 特定の正規表現によって記述または一致する文字列。
• チューリングマシンや有限状態オートマトンなどのオートマトンによって受け入れられる文字列。
• 何らかの決定手順(一連の関連する YES/NO の質問を尋ねるアルゴリズム)によって YES という回答が生成される文字列。

このような形式主義に関してよく尋ねられる質問には次のようなものがあります。

• それらの表現力はどの程度ですか? (形式主義X は形式主義Yが記述できるすべての言語を記述できますか? 他の言語も記述できますか?)
• それらの認識可能性はどの程度ですか？（与えられた単語が形式主義Xによって記述された言語に属するかどうかを判断するのはどの程度難しいですか？）
• それらの比較可能性はどの程度ですか? (形式論Xで記述された言語と形式論Yで記述された言語、あるいは再び形式論Xで記述された言語の 2 つの言語が実際に同じ言語であるかどうかを判断するのはどの程度難しいですか)。

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

言語の操作

言語における特定の演算は一般的です。これには、和集合、積集合、補集合といった標準的な集合演算が含まれます。また、文字列演算の要素単位の適用も、演算の一種です。

例:と が共通のアルファベットに基づく言語であるとします。 ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle \Sigma }$

• 連結は 、 の文字列であり、の文字列である、の形式のすべての文字列で構成されます。${\displaystyle L_{1}\cdot L_{2}}$ ${\displaystyle vw}$ ${\displaystyle v}$ ${\displaystyle L_{1}}$ ${\displaystyle w}$ ${\displaystyle L_{2}}$
• と の共通部分 は、両方の言語に含まれるすべての文字列から構成されます。${\displaystyle L_{1}\cap L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$
• に関するの補集合 は、に含まれない上のすべての文字列から構成されます。${\displaystyle \neg L_{1}}$ ${\displaystyle L_{1}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle L_{1}}$
• クリーネスター: 元の言語の 0 個以上の単語を連結したすべての単語で構成される言語。
• 逆転：
  • εを空語とすると、${\displaystyle \varepsilon ^{R}=\varepsilon }$
  • 空でない各単語（ここではアルファベットの要素）について、${\displaystyle w=\sigma _{1}\cdots \sigma _{n}}$ ${\displaystyle \sigma _{1},\ldots ,\sigma _{n}}$ ${\displaystyle w^{R}=\sigma _{n}\cdots \sigma _{1}}$
  • 形式言語の場合、。${\displaystyle L}$ ${\displaystyle L^{R}=\{w^{R}\mid w\in L\}}$
• 文字列準同型

このような文字列演算は、言語のクラスの閉包性を調査するために使用されます。言語のクラスが特定の演算に関して閉じているとは、その演算をそのクラスの言語に適用すると、常に同じクラスの言語が再び生成されることを意味します。例えば、文脈自由言語は、正規言語との和集合、連接、積集合に関して閉じていることが知られていますが、積集合や補集合に関しては閉じていないことが知られています。三言語族理論と抽象言語族理論は、言語族の最も一般的な閉包性をそれ自体で研究します。^{[ 12 ]}

言語族の閉包性（Op、ただし、との両方が列で指定された言語族に属する）。HopcroftとUllmanによる。 ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$

手術		通常	DCFL	CFL	インド	CSL	再帰的	再エネ
連合	${\displaystyle L_{1}\cup L_{2}=\{w\mid w\in L_{1}\lor w\in L_{2}\}}$	はい	いいえ	はい	はい	はい	はい	はい
交差点	${\displaystyle L_{1}\cap L_{2}=\{w\mid w\in L_{1}\land w\in L_{2}\}}$	はい	いいえ	いいえ	いいえ	はい	はい	はい
補体	${\displaystyle \neg L_{1}=\{w\mid w\not \in L_{1}\}}$	はい	はい	いいえ	いいえ	はい	はい	いいえ
連結	${\displaystyle L_{1}\cdot L_{2}=\{wz\mid w\in L_{1}\land z\in L_{2}\}}$	はい	いいえ	はい	はい	はい	はい	はい
クリーネスター	${\displaystyle L_{1}^{*}=\{\varepsilon \}\cup \{wz\mid w\in L_{1}\land z\in L_{1}^{*}\}}$	はい	いいえ	はい	はい	はい	はい	はい
（文字列）準同型${\displaystyle h}$	${\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}$	はい	いいえ	はい	はい	いいえ	いいえ	はい
εフリー（弦）準同型${\displaystyle h}$	${\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}$	はい	いいえ	はい	はい	はい	はい	はい
代替${\displaystyle \varphi }$	${\displaystyle \varphi (L_{1})=\bigcup _{\sigma _{1}\cdots \sigma _{n}\in L_{1}}\varphi (\sigma _{1})\cdot \ldots \cdot \varphi (\sigma _{n})}$	はい	いいえ	はい	はい	はい	いいえ	はい
逆準同型${\displaystyle h^{-1}}$	${\displaystyle h^{-1}(L_{1})=\bigcup _{w\in L_{1}}h^{-1}(w)}$	はい	はい	はい	はい	はい	はい	はい
逆行する	${\displaystyle L^{R}=\{w^{R}\mid w\in L\}}$	はい	いいえ	はい	はい	はい	はい	はい
正規言語との交差${\displaystyle R}$	${\displaystyle L\cap R=\{w\mid w\in L\land w\in R\}}$	はい	はい	はい	はい	はい	はい	はい

アプリケーション

プログラミング言語

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

もちろん、コンパイラはソースコードを解析するだけではありません。通常は、それを何らかの実行形式に変換します。そのため、パーサーは通常、yes/noの回答以上のもの、典型的には抽象構文木を出力します。これはコンパイラの後続の段階で使用され、最終的にハードウェア上で直接実行されるマシンコード、または仮想マシンでの実行を必要とする中間コードを含む実行ファイルを生成します。

形式理論、システム、証明

この図は、形式体系における統語的区分を示しています。記号列は、大きく分けて無意味な式と整形式の式に分けられます。整形式の式は、定理と非定理に分けられます。

数理論理学では、形式理論とは形式言語で表現された 文の集合です。

形式体系（論理計算または論理システムとも呼ばれる）は、形式言語と演繹装置（演繹システムとも呼ばれる）から構成されます。演繹装置は、有効な推論規則として解釈できる一連の変換規則、または一連の公理、あるいはその両方で構成されます。形式体系は、1 つ以上の他の式から 1 つの式を導き出すために使用されます。形式言語はその式で識別できますが、形式体系は同様にその定理で識別することはできません。2 つの形式体系とがすべて同じ定理を持ちながらも、重要な証明理論的方法で異なる場合があります（たとえば、式 A は、一方においては式 B の構文上の帰結であるが、もう一方ではそうではないなど）。 ${\displaystyle {\mathcal {FS}}}$ ${\displaystyle {\mathcal {FS'}}}$

形式的な証明または導出とは、整形式の式（文または命題として解釈できる）の有限列であり、各式は公理であるか、または列内の先行する式から推論規則によって導かれる。列の最後の文は、形式体系の定理である。形式的な証明は、その定理が真の命題として解釈できるため有用である。

解釈とモデル

形式言語は本質的に完全に統語論的ですが、言語の要素に意味を与える意味論を付与することができます。例えば、数理論理学では、特定の論理における可能な式の集合が形式言語であり、解釈によって各式に意味（通常は真理値）が割り当てられます。

形式言語の解釈の研究は形式意味論と呼ばれます。数理論理学では、これはしばしばモデル理論の観点から行われます。モデル理論では、式に現れる項は数学的構造内のオブジェクトとして解釈され、一定の構成的解釈規則によって、項の解釈から式の真理値がどのように導かれるかが決定されます。式のモデルとは、式が真となるような項の解釈です。

参照

• 単語の組合せ論
• 形式手法
• 自由モノイド
• 文法の枠組み
• 数学表記
• 文字列（コンピュータサイエンス）

注記

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

参考文献

引用

1. 例えば、 Reghizzi, Stefano Crespi (2009). Formal Languages and Compilation . Texts in Computer Science. Springer. p. 8. Bibcode : 2009flc..book.....C . ISBNを参照 9781848820500アルファベットは有限集合である
2. 「オートマトン理論、言語、計算入門」 infolab.stanford.edu . 2026年1月23日閲覧。
3. 「形式言語理論の前史：ガウス言語」 1992年1月。 2021年4月30日閲覧。
4. “ゴットロブ・フレーゲ” . 2019 年 12 月 5 日。2021 年4 月 30 日に取得。
5. マーティン・デイビス (1995). 「数理論理学のコンピュータサイエンスへの影響」 . ロルフ・ヘルケン編著. 『ユニバーサル・チューリングマシン：半世紀の概観』 . シュプリンガー. 290ページ. ISBN 978-3-211-82637-9。
6. “Thue's 1914 paper: a translation” (PDF) . 2013年8月28日. 2021年4月30日時点のオリジナルよりアーカイブ(PDF) . 2021年4月30日閲覧。
7. 「エミール・レオン・ポスト」 2001年9月. 2021年4月30日閲覧。
8. トーレス・ケベド、レオナルド。 Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas、(pdf)、25–30 ページ、Revista de Obras Públicas、1907 年 1 月 17 日。
9. ブルーダラー、ハーバート（2021年）「コンピュータ技術の世界的な進化」アナログ・デジタルコンピューティングのマイルストーン、シュプリンガー、1212頁。ISBN 978-3030409739。
10. イェーガー、ゲルハルト、ロジャース、ジェームズ (2012年7月19日). 「形式言語理論：チョムスキー階層の洗練」 . Philosophical Transactions of the Royal Society B. 367 ( 1598): 1956–1970. doi : 10.1098 / rstb.2012.0077 . PMC 3367686. PMID 22688632 .  
11. 「ジョン・ワーナー・バッカス」 2016年2月. 2021年4月30日閲覧。
12. Hopcroft & Ullman (1979)、第11章：言語族の閉包特性。

出典

引用文献

• ホップクロフト, ジョン・E. ;ウルマン, ジェフリー・D. (1979). 『オートマトン理論、言語、計算入門』 マサチューセッツ州レディング: アディソン・ウェスリー出版. ISBN 81-7808-347-7。

一般的な参考文献

• AGハミルトン『数学者のための論理学』ケンブリッジ大学出版局、1978年、ISBN 0-521-21838-1。
• シーモア・ギンズバーグ『形式言語の代数的およびオートマトン理論的性質』ノースホランド、1975年、ISBN 0-7204-2506-9。
• マイケル・A・ハリソン著『形式言語理論入門』、アディソン・ウェスレー、1978年。
• ラウテンバーグ、ヴォルフガング(2010). 『数理論理学簡潔入門（第3版）』 ニューヨーク:シュプリンガー・サイエンス+ビジネス・メディア. doi : 10.1007/978-1-4419-1221-3 . ISBN 978-1-4419-1220-6。
• Grzegorz Rozenberg、Arto Salomaa、『形式言語ハンドブック：第1-3巻』、Springer、1997年、ISBN 3-540-61486-9。
• パトリック・サップス『論理学入門』 D.ヴァン・ノストランド、1957年、ISBN 0-442-08072-7。

外部リンク

• 「形式言語」、数学百科事典、EMSプレス、2001 [1994]
• メリーランド大学、形式言語定義、 2008年2月16日アーカイブ、 Wayback Machine
• James Power、「形式言語理論と構文解析に関するノート」、Wayback Machineで 2007 年 11 月 21 日にアーカイブ、2002 年 11 月 29 日。
• 「形式言語理論ハンドブック」第1～3巻、G. RozenbergとA. Salomaa編、Springer Verlag（1997年）のいくつかの章の草稿：
  • Alexandru Mateescu および Arto Salomaa、第 1 巻の「序文」、v ～ viii 頁、および第 1 巻の第 1 章「形式言語: 序論と概要」 1、1–39ページ
  • 盛宇「正規言語」第1巻第2章
  • Jean-Michel Autebert、Jean Berstel、Luc Boasson、「文脈自由言語とプッシュダウンオートマトン」、第1巻第3章
  • Christian Choffrut と Juhani Karhumaki、「言葉の組み合わせ論」、第 6 巻の第 6 章1
  • テロ・ハルジュとユハニ・カルフマキ、「モーフィズム」、第 7 巻第 7 章1、439～510ページ
  • Jean-Eric Pin、「統語的半群」、第1巻第10章、679～746ページ
  • M. CrochemoreとC. Hancart、「パターンマッチングのためのオートマトン」、第2巻第9章
  • Dora Giammarresi、Antonio Restivo、「二次元言語」、第 4 巻の第 4 章3、215–267ページ