文脈依存文法の定義・具体例・生成規則・オートマトンについて

1. 文脈依存文法とは

ここで、文脈自由文法と同様に、各要素の意味は次の通りです。

• \( N \) (非終端記号の集合): 文法で使用される非終端記号の集合。
• \( \Sigma \) (終端記号の集合): 文法で使用される終端記号の集合。
• \( P \) (生成規則の集合): 文脈依存文法の生成規則は、次の形式を取ります。\[ \alpha A \beta \rightarrow \alpha \gamma \beta \]ここで、\( A \in N \)、\( \alpha, \beta \in (N \cup \Sigma)^* \)、そして \( \gamma \in (N \cup \Sigma)^+ \) です。つまり、非終端記号 \( A \) は文脈 \( \alpha \) と \( \beta \) に囲まれている場合にのみ、文脈依存の規則に従って \( \gamma \) に置き換えられます。
• \( S \) (開始記号): 文法の開始記号であり、\( S \in N \) です。

文脈依存文法で生成される言語は、文脈依存言語と呼ばれます。

2. 文脈依存文法の具体例

次の言語は有名な文脈自由言語でない言語の一つとして知られています。

\( L = \{ a^n b^n c^n \mid n \geq 1 \} \)

この言語は「同じ数の ‘a’、’b’、’c’ を含む文字列」の集合です。これは文脈自由言語ではないことも知らています。

2.1. 文法の生成規則

言語 \( L = \{ a^n b^n c^n \mid n \geq 1 \} \) の文脈依存文法の生成規則は以下のように定義できます。

\( S \rightarrow aSBC \)
\( SB \rightarrow aBB \)
\( BB \rightarrow Bb \)
\( Bb \rightarrow bb \)
\( BC \rightarrow bC \)
\( bC \rightarrow bc \)
\( Sc \rightarrow c \)

2.2. 生成例

開始記号 \( S \) からスタートし、以下のように展開されていきます。

1. \( S \rightarrow aSBC \)
2. \( aSBC \rightarrow aaBBBC \)
3. \( aaBBBC \rightarrow aabBBC \)
4. \( aabBBC \rightarrow aabBbC \)
5. \( aabBbC \rightarrow aabbBC \)
6. \( aabbBC \rightarrow aabbcC \)
7. \( aabbcC \rightarrow aabbcc \)

したがって、文字列 \( aabbcc \) が生成されます。

この文脈依存文法では、終端記号が1つずつ生成され、各 \( a \) に対応する \( b \)、および各 \( b \) に対応する \( c \) が順番に生成されていくことで、言語 \( L = \{ a^n b^n c^n \mid n \geq 1 \} \) が構築されます。

3. オートマトンと形式文法の対応関係

オートマトンと形式文法の対応関係は次のようになります。