文脈依存言語

文脈依存言語(context-sensitive language)とは文脈依存文法によって生成される形式言語である。

文脈依存文法は句構造文法の一種であるから、 文脈依存言語は句構造言語の一種である.

以下、項目形式言語において定められている言語上の演算などについては特に断らず用いる。

$\global\def\mathderiv{\mathrel{\mathop{\Rightarrow}}^{*}}$ $\global\def\mathgen{\rightsquigarrow}$ $\global\def\emptyword{\varepsilon}$ $\global\def\kleenecl#1{{#1}^{*}}$ $\global\def\interpret#1{[\![#1]\!]}$

文脈依存言語の導入

この節では文脈依存言語を定義する。

文脈依存文法

文脈依存文法(context-sensitive grammar)とは

  1. 記号集合 $\Sigma$
  2. $\Sigma$ と互いに素な変数記号(variable)の有限集合 $V$
  3. 開始記号(start symbol)または初期記号と呼ばれる $S\in V$
  4. 生成規則(production rule)と呼ばれる、所属するすべての元が $(S, \emptyword)$ または $(\gamma A\delta, \gamma\alpha\delta)$ という形をしている有限集合(ただし、$\gamma, \delta \in \kleenecl{(\Sigma \cup V)}$, $A\in V$, $\alpha \in \kleenecl{(\Sigma \cup V)}\setminus \{\emptyword\}$)

の4つ組 $(V, \Sigma, R, S)$ である。

これは、句構造文法の一種である。

句構造言語と同様、$\Sigma$ の元を終端記号(terminal)、$V$ の元を非終端記号(non-terminal)と呼ぶことも多い。

以下では、元 $(\gamma A\delta, \gamma\alpha\delta)\in R$ のことを$\gamma A\delta \mathgen \gamma\alpha\delta$ と書く。また、元 $(S, \emptyword)\in R$ のことを$S \mathgen \emptyword$ と書く。

導出

句構造言語導出の節を参照。

文脈依存言語の定義

文脈依存言語とは何らかの文脈依存文法によって生成される言語のことを言う。

参考文献

  1. 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
  2. 五十嵐喜英他、『数理情報科学シリーズ 24 オートマトンと形式言語の基礎?』、牧野書店、2011

関連項目

Chomsky 階層

文法のタイプ言語のクラス計算モデル
タイプ0句構造言語Turingマシン?
タイプ1文脈依存言語線形有界オートマトン?
タイプ2文脈自由言語プッシュダウン・オートマトン?
タイプ3正規言語有限オートマトン


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2020-11-06 (金) 00:33:59 (161d)