文法を数学で表すための主要な概念

Posted On 2025年12月14日

💡 文法を数学で表すための主要な概念

文法の構造を数学的に表現する際に中心となるのは、「形式文法 (Formal Grammar)」の概念です。形式文法は、特定の言語（文字列の集合）を生成するための一連の規則を、以下の4つの要素で定義します。

1. 終端記号の集合 (

\Sigma

: Terminal Symbols)

言語を構成する**「最終的な文字」や「単語」**の集合です。
自然言語では個々の単語（例： $\{私, は, りんご, を, 食べる\}$ ）、プログラミング言語ではキーワードや演算子（例： $\{\text{if}, \text{else}, +, *\}$ ）などが該当します。

2. 非終端記号の集合 (

N

: Non-Terminal Symbols)

文法構造を表す**「抽象的な記号」**です。文法の構成要素や、文の途中段階を示します。
例： $\{\text{文}, \text{名詞句}, \text{動詞句}\}$

3. 開始記号 (

S

: Start Symbol)

非終端記号の一つで、文法の生成プロセスを開始する記号です（例：

$S = \text{文}$

）。

4. 生成規則の集合 (

P

: Production Rules)

最も重要な要素で、「左辺 $\rightarrow$ 右辺」の形で示され、非終端記号を別の記号の列に置き換える規則です。

具体例：簡単な文の文法

\begin{array}{rcl} \text{文} & \rightarrow & \text{名詞句} \quad \text{動詞句} \\ \text{名詞句} & \rightarrow & \text{私} \mid \text{りんご} \\ \text{動詞句} & \rightarrow & \text{を食べる} \end{array}

この規則を使うと、「文」から「私を食べる」という正しい文が生成（導出）できます。

\text{文} \rightarrow \text{名詞句} \quad \text{動詞句} \rightarrow \text{私} \quad \text{動詞句} \rightarrow \text{私 を食べる}

🌐 形式言語理論とチョムスキー階層

言語学者ノーム・チョムスキーは、生成規則の制約の厳しさによって形式文法を4つのタイプに分類しました。これを「チョムスキー階層」と呼びます。

階層 (Type)	文法タイプ	生成規則の制約	認識可能なオートマトン	適用例
タイプ 3	正規文法	左辺は非終端記号1個、右辺は終端記号1個と非終端記号1個以下	有限オートマトン	正規表現、単純な状態遷移
タイプ 2	文脈自由文法	左辺は非終端記号1個のみ（右辺の文脈を考慮しない）	プッシュダウン・オートマトン	多くのプログラミング言語の構文（代入文、関数呼び出しなど）
タイプ 1	文脈依存文法	左辺の非終端記号が置き換えられる際、その周囲の記号（文脈）も考慮される	線形拘束オートマトン	自然言語の一部
タイプ 0	制限なし文法	最も一般的な形式	チューリング機械	全ての計算可能な問題

このように、文法の構造は数学（集合論、論理学）を基盤とした形式体系によって明確に定義され、その複雑さに応じて**オートマトン（抽象的な計算モデル）**と一対一に対応づけられています。これは、コンピュータがプログラミング言語の構文を解析したり（コンパイラ）、自然言語処理を行ったりするための理論的基礎となっています。

スペイン語で人生を変えよう

Think different