形式言語

形式言語（けいしきげんご、英: formal language）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが残されたり、話者集団によって用法のうつろいゆくような自然言語に対して、プログラミング言語を含む一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などの形式言語は、用法の変化に関しては厳格である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。

定義

形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列（語 word） の集合である^[1]。

${\displaystyle L\subset \Sigma ^{*}=\{\langle \sigma _{1},\sigma _{2},...\rangle |\sigma _{i}\in \Sigma \}}$

ただし、長さゼロの空単語（Empty Word, 記号 ${\displaystyle e}$、${\displaystyle \epsilon }$、${\displaystyle \Lambda }$）も含む。 チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化(エンコード)し、その数値を解釈するプログラムを埋め込む必要がある。 チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。

あるチューリングマシンが存在して、言語に属するすべての語 w に対して動作させると受理状態で停止し、属さない語には受理しないようなとき、その言語はチューリング認識可能という。 また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。(この2つの違いは、一部の入力に対してチューリングマシンが停止しない場合があるかどうかである) また、チューリングマシンTMの言語 L(TM) とは、テープに w をセットしたあと、TMを動作させると受理状態に入って停止するような w の集合からなる言語(TM認識可能な言語)のことである。

この言語には以下のような演算が定義される。ここで、${\displaystyle L_{1}}$ と ${\displaystyle L_{2}}$ は共通のアルファベットから構成される言語であるとする。

• 「連結」${\displaystyle L_{1}L_{2}\quad }$ は、文字列群 ${\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 L_{1}\cup L_{2}}$ は、${\displaystyle L_{1}}$ か ${\displaystyle L_{2}}$ に含まれる文字列の集合である。
• ${\displaystyle L_{1}}$ の「補集合」は、${\displaystyle L_{1}}$ に含まれない全ての文字列の集合である。
• 「商集合」${\displaystyle L_{1}/L_{2}\quad }$ は、${\displaystyle L_{1}}$ に含まれる文字列 ${\displaystyle vw}$ に対して、${\displaystyle L_{2}}$ に含まれる文字列 ${\displaystyle w}$ が存在するときに、全ての ${\displaystyle v}$ に相当する文字列群から構成される。
• 「クリーネスター」${\displaystyle L_{1}^{*}}$ は、${\displaystyle w_{1}w_{2}...w_{n}}$ という形式の全文字列群から構成される。ただし、${\displaystyle w_{i}}$ は ${\displaystyle L_{1}}$ に含まれ、${\displaystyle n\geq 0}$ である。注意すべきは、${\displaystyle n=0}$ の場合もあるので、空文字列 ${\displaystyle \epsilon }$ も含まれるという点である。
• 「反転」${\displaystyle L_{1}^{R}}$ は、${\displaystyle L_{1}}$ の全文字列を反転させた文字列群から構成される。
• ${\displaystyle L_{1}}$ と ${\displaystyle L_{2}}$ の「シャッフル」とは、${\displaystyle v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}}$ で表される全文字列から構成される。ここで、${\displaystyle n\geq 1}$ で、${\displaystyle v_{1},...,v_{n}}$ を連結した ${\displaystyle v_{1}...v_{n}}$ は ${\displaystyle L_{1}}$ に含まれる文字列であり、${\displaystyle w_{1},...,w_{n}}$ を連結した ${\displaystyle w_{1}...w_{n}}$ は ${\displaystyle L_{2}}$ に含まれる文字列である。

モデル理論においては、言語は定数記号、関数記号、述語記号の集合である^[2]。

${\displaystyle L=\{c_{0},c_{1},...\}\cup \{f_{0},f_{1},...\}\cup \{p_{0},p_{1},...\}}$

形式文法

形式言語は、形式文法と密接な関係がある。例として、次のような文脈自由文法の構文規則があるとき、

• 名詞句 ::= 名詞 | 形容詞 名詞 | 名詞句 "を" 動詞 "ている" 名詞句
• 動詞 ::= "見"
• 名詞 ::= "猿" | "飼育員"
• 形容詞 ::= "小さい"

以下のように規則を再帰的に適用して、その言語の要素(名詞句)を列挙することができる。

1. (猿 飼育員 小さい猿 小さい飼育員)
2. (猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 猿を見ている飼育員 猿を見ている小さい猿 ... 小さい猿を見ている猿 ...)
3. (猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 ... 猿をみている猿を見ている猿 ... 小さい猿を見ている猿を見ている小さい飼育員を見ている猿 ...)

...

すなわち、このような操作の任意回の繰り返しによって、その言語(文の集合)が得られる。

また、形式文法が階層をなすというチョムスキー階層は、生成する言語では言語の認識に必要な最小のオートマトンが階層をなすという形で現れる。

その他

言及される分野

形式言語は、「人や計算機の如何なる記号変換能力から如何なる思考能力や計算能力が生まれるか」の学としての広義の数理論理学の研究対象であり、従って形式言語は、哲学・言語学・計算機科学・数学基礎論・数理心理学等々において重要な役割を演ずる。 それらの学問分野では、如何なる形式言語を研究すべきかの文法論（構文論・統辞論）や形式言語の意味論や演繹論が研究される。

形式手法という場合には、形式言語に加えて、模擬試験、検証・証明などの仕組みを込みで言う場合が有る。

自然言語への応用

自然言語を比較的単純な形式言語のモデルにあてはめて分析する言語学は、チョムスキーによって提唱された。音素や語幹などを素記号として考える。 実際の自然言語の構文規則（あるいは文法）は、文字通り自然発生的のものであり、形式言語における構文規則のように明確に規定するのは難しい。

ただ、素朴な文法論の主張は、形式言語の理論とみなすことができる。 素朴な文法論は、例えば次のようなものである。

• 品詞にはこのようなのものがある。
• この語はあの品詞に属す。
• この品詞に属す語をこの活用と組み合わせと順序とで並べると文（や句や節）になる。

こういう文法論はすなわち、素記号とは何かを定め、それらから文を作る構文規則を定めるのだから、まさに形式言語の理論である。

こういう形式言語論的な文法論は、実際の言語と比較することで自然言語の特徴を浮き彫りにし、自然言語のより深い理解へと導くことを可能とすることもなくはない。言語そのものではなく、言語行動の深層をなす人間精神を探るためには、むしろこういう文法論を数学化し、更に意味論・文法論を伴った論理学にまで推し進めることが有意義ともいえよう。

脚注

ウィキメディア・コモンズには、形式言語に関連するカテゴリがあります。

表 話 編 歴 論理学
関連項目 学術的領域 議論学 価値論 批判的思考 再帰理論 形式意味論 論理史 非形式論理学 計算機科学における論理学（英語版） 数理論理学 数学 メタ論理学 メタ数学 モデル理論 哲学的論理学 哲学 論理学の哲学 数学の哲学 証明論 集合論 論理学の歴史 基本概念 アブダクション 分析的と総合的の区別（英語版） 二律背反 アプリオリ 演繹 定義(内包と外延) 記述 帰納 推論 論理的帰結 論理形式（英語版） 論理的含意（英語版） 論理的真理 名前 必要十分条件 意味 パラドックス 可能世界論 前提 確率 理性 推理 参考 意味論 命題 サブスティトゥーション（英語版） 統語論（英語版） 真理 真理値 妥当性 数学記号の表
哲学的論理学 批判的思考と非形式論理学 分析 曖昧 信念 信用性（英語版） 根拠 説明 説明力（英語版） 事実 誤謬 探究 意見 節約 根拠 プロパガンダ 思慮分別（英語版） 推理 関連 修辞学 厳格 漠然（英語版） 論理学の哲学 構成主義 真矛盾主義 虚構主義（英語版） 有限主義（英語版） 形式主義 直観主義 論理的原子論（英語版） 論理主義 唯名論 プラトニック実在論（英語版） プラグマティズム 実在論
メタ論理学と超数学 カントールの定理 決定問題 チャーチのテーゼ 無矛盾性 実効的方法（英語版） 数学基礎論 ゲーデルの完全性定理 ゲーデルの不完全性定理 健全性 完全性 決定可能性 解釈 レーヴェンハイム-スコーレムの定理 メタ定理（英語版） 充足可能性 独立性（英語版） 独立 タイプとトークンの区別 使用と言及の区別
数理論理学 基幹 形式言語 構成規則 形式体系 演繹システム（英語版） 形式的証明 形式意味論 論理式 集合 元 クラス 古典論理 公理 自然演繹 推論規則 有限関係（英語版） 定理 論理的帰結 公理系 型理論 記号 統語論（英語版） 理論（英語版） 名辞論理学（英語版） 命題 推論 論証 妥当性 三段論法 反対の正方形 ベン図 命題論理とブール論理 ブール関数 命題論理 論理演算 真理値表 原子論理式 リテラル 述語論理 量化 全称記号 存在記号 一階述語論理 二階述語論理 高階述語論理 単項述語計算（英語版） 標準形 連言標準形 選言標準形 否定標準形 冠頭標準形 スコーレム標準形 節標準形 集合論 集合 空集合 数え上げ 外延 有限集合 関数 部分集合 冪集合 可算集合 帰納的集合 定義域 値域 順序対 非可算集合 モデル理論 モデル（英語版） 解釈（英語版） 超準モデル 有限モデル理論 真理値 妥当性 証明論 形式的証明 演繹システム（英語版） 形式体系 定理 論理的帰結 推論規則 統語論（英語版） 再帰理論 再帰 帰納的集合 帰納的可算集合 決定問題 チャーチ＝チューリングのテーゼ 計算可能関数 原始再帰関数 表現 真理値表 クワイン・マクラスキー法 カルノー図 存在グラフ 概念地図 オイラー図 ベン図 スパイダー図 タブローの方法 Xバー理論 構文木 構文解析
非古典論理 様相論理学 真理様相（英語版） 価値様相（英語版） 義務論理 信念様相（英語版） 認識論理 時相論理 線形時相論理 直観主義 直観論理 構成的解析（英語版） ハイディング算術（英語版） 直観主義型理論 構成的集合論（英語版） ファジィ論理 真理の程度（英語版） ファジィルール（英語版） ファジィ集合 ファジィ有限要素（英語版） ファジィ集合演算（英語版） 部分構造論理 構造規則（英語版） 適切さの論理 線形論理 矛盾許容論理 真矛盾主義 様相記述論理（英語版） 存在論 オントロジー言語（英語版）
論理学者 アンダーソン アリストテレス イブン・ルシュド イブン・スィーナー ベイン（英語版） バーワイズ（英語版） ベルナイス ブール ブーロス（英語版） カントール カルナップ チャーチ クリュシッポス カリー ド・モルガン フレーゲ ギーチ ゲンツェン ゲーデル ヒルベルト クリーネ クリプキ ライプニッツ レーヴェンハイム（英語版） ペアノ パース パトナム クワイン ラッセル シュレーダー（英語版） スコトゥス スコーレム スマリヤン タルスキ チューリング ホワイトヘッド オッカムのウィリアム ウィトゲンシュタイン ツェルメロ
カテゴリ