文脈依存言語
[math] \newcommand{\mathsetextension}[1]{% \left\{ #1 \right\}% } \newcommand{\mathderiv}{\mathrel{\mathop{\Rightarrow}^{*}}} \newcommand{\mathgen}{\rightsquigarrow} \newcommand{\emptyword}{\varepsilon} \newcommand{\kleenecl}[1]{{#1}^{*}} \newcommand{\interpret}[1]{[\![#1]\!]} \newcommand{\mathautomaton}[1]{\mathcal{#1}} \newcommand{\mathnat}{\mathbb{N}} \newcommand{\qed}{\blacksquare} [/math]
文脈依存言語（context-sensitive language）とは文脈依存文法によって生成される形式言語である。
文脈依存文法は句構造文法の一種であるから、 文脈依存言語は句構造言語の一種である．
以下、項目形式言語において定められている言語上の演算などについては特に断らず用いる。
文脈依存言語の導入
この節では文脈依存言語を定義する。
定義 1 (文脈依存文法)
文脈依存文法（context-sensitive grammar）とは
- 記号集合 $\Sigma$
- $\Sigma$ と互いに素な変数記号（variable）の有限集合 $V$
- 開始記号(start symbol)または初期記号と呼ばれる $S\in V$
- 生成規則（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\}$)
の４つ組 $(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$ と書く。
導出、 生成される言語などは 句構造言語と同様に定義される。
文脈依存言語とは何らかの文脈依存文法によって生成される言語のことを言う。
参考文献
- 新屋 良磨、オートマトン理論再考、コンピュータ ソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3、https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
- 五十嵐喜英他、『[数理情報科学シリーズ ２４ オートマトンと形式言語の基礎]』、牧野書店、2011
関連項目
| 文法のタイプ | 言語のクラス | 計算モデル |
|---|---|---|
| タイプ0 | 句構造言語 | Turingマシン |
| タイプ1 | 文脈依存言語 | 線形有界オートマトン |
| タイプ2 | 文脈自由言語 | プッシュダウン・オートマトン |
| タイプ3 | 正規言語 | 有限オートマトン |
