文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう はノーム・チョムスキー による句 く 構造 こうぞう 文法 ぶんぽう の研究 けんきゅう の中 なか から、形式 けいしき 言語 げんご の類別 るいべつ (形式 けいしき 言語 げんご の階層 かいそう やチョムスキー階層 かいそう の記事 きじ を参照 さんしょう )のひとつとして見出 みいだ されたものである[ 2] 。
文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう の形式 けいしき 性 せい は、言語 げんご 学 がく が伝統 でんとう 的 てき に自然 しぜん 言語 げんご の文法 ぶんぽう を形式 けいしき 的 てき に記述 きじゅつ してきた既存 きそん の方法 ほうほう (例 たと えばパーニニ )に倣 なら っている。たとえば、入 い れ子 こ (nesting)を自然 しぜん に捉 とら えていることや、形式 けいしき 的 てき であることから形式 けいしき 的 てき な手法 しゅほう が使 つか えるという利点 りてん がある。一方 いっぽう で問題 もんだい もあり、たとえば自然 しぜん 言語 げんご の文法 ぶんぽう の重要 じゅうよう な機能 きのう である一致 いっち や参照 さんしょう といった属性 ぞくせい は綺麗 きれい に表 あらわ すことができない(自然 しぜん 言語 げんご に限 かぎ らず、プログラミング言語 げんご でもしばしば文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう から「はみ出 だ している」仕様 しよう がある)。
文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう は、(チョムスキーらによって言語 げんご 学 がく で)提唱 ていしょう されてすぐに、(形式 けいしき 言語 げんご と密接 みっせつ な関係 かんけい にあるオートマトン理論 りろん のような理論 りろん 計算 けいさん 機 き 科学 かがく の分野 ぶんや にとどまらず)プログラミング言語 げんご ALGOL の仕様 しよう 策定 さくてい において、構文 こうぶん の仕様 しよう を示 しめ すバッカス・ナウア記法 きほう という形 かたち でとり入 い れられ、その後 ご コンピュータ科学 かがく 一般 いっぱん に、あるいはもっと広 ひろ く実務 じつむ にも応用 おうよう されている。
「文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう はほとんどのプログラミング言語 げんご の文法 ぶんぽう を記述 きじゅつ できるほど強力 きょうりょく であり、実際 じっさい 、多 おお くのプログラミング言語 げんご は文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう で構文 こうぶん 仕様 しよう を定義 ていぎ している。」といった言説 げんせつ がしばしば見 み られるが[ 注釈 ちゅうしゃく 1] 誤 あやま りである。本当 ほんとう に実際 じっさい の所 ところ は、yaccで定義 ていぎ されていても、純粋 じゅんすい に構文 こうぶん では定義 ていぎ しきれない部分 ぶぶん をあれこれと意味 いみ 規則 きそく で補 おぎな っているのが普通 ふつう である。
文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう は効率 こうりつ 的 てき な構文 こうぶん 解析 かいせき アルゴリズム を適用 てきよう できる程度 ていど に単純 たんじゅん である。つまり、ある文字 もじ 列 れつ が特定 とくてい の文法 ぶんぽう による言語 げんご に属 ぞく しているかどうかを判断 はんだん することができる(例 たと えばアーリー法 ほう )。初期 しょき の構文 こうぶん 解析 かいせき 手法 しゅほう であるLR法 ほう やLL法 ほう は文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう のサブセットを扱 あつか うものであった。
全 すべ ての形式 けいしき 言語 げんご が文脈 ぶんみゃく 自由 じゆう であるわけではない。文脈 ぶんみゃく 自由 じゆう でない例 れい として
{
a
n
b
n
c
n
:
n
≥
0
}
{\displaystyle \{a^{n}b^{n}c^{n}:n\geq 0\}}
がある。この言語 げんご は Parsing Expression Grammar (PEG) では生成 せいせい できる。PEG は文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう と扱 あつか える範囲 はんい の文法 ぶんぽう が異 こと なり文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう を全 すべ て扱 あつか えるわけではないがプログラミング言語 げんご に適 てき した新 あら たな定式 ていしき 化 か のひとつである。
文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう G は次 つぎ の 4-タプル で表 あらわ される。
G
=
(
V
,
Σ しぐま
,
R
,
S
)
{\displaystyle G=(V\,,\Sigma \,,R\,,S\,)}
ここで
V
{\displaystyle V\,}
は変数 へんすう (非終端 ひしゅうたん 記号 きごう )の有限 ゆうげん 集合 しゅうごう
Σ しぐま
{\displaystyle \Sigma \,}
は終端 しゅうたん 記号 きごう の有限 ゆうげん 集合 しゅうごう で、
Σ しぐま
∩
V
=
∅
{\displaystyle \Sigma \cap V=\emptyset }
S
{\displaystyle S\,}
は開始 かいし 記号 きごう (変数 へんすう )
R
{\displaystyle R\,}
は
V
{\displaystyle V}
から
(
V
∪
Σ しぐま
)
∗
{\displaystyle (V\cup \Sigma )^{*}}
への関係 かんけい であり、
∃
w
∈
(
V
∪
Σ しぐま
)
∗
:
(
S
,
w
)
∈
R
{\displaystyle \exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R}
が成 な り立 た つ
R
{\displaystyle R\,}
のメンバーを文法 ぶんぽう の規則 きそく と呼 よ ぶ。
任意 にんい の
(
α あるふぁ
,
β べーた
)
∈
R
{\displaystyle (\alpha ,\beta )\in R}
について
P
α あるふぁ
β べーた
(
u
,
v
)
=
(
u
α あるふぁ
v
,
u
β べーた
v
)
{\displaystyle P_{\alpha \beta }(u,\,v)=(u\alpha v,\,u\beta v)}
となるような生成 せいせい 写像 しゃぞう
P
α あるふぁ
β べーた
:
(
V
∪
Σ しぐま
)
∗
×
(
V
∪
Σ しぐま
)
∗
⟶
(
V
∪
Σ しぐま
)
∗
×
(
V
∪
Σ しぐま
)
∗
{\displaystyle P_{\alpha \beta }:(V\cup \Sigma )^{*}\times (V\cup \Sigma )^{*}\longrightarrow (V\cup \Sigma )^{*}\times (V\cup \Sigma )^{*}}
が存在 そんざい する。
順序 じゅんじょ 対 たい
(
u
α あるふぁ
v
,
u
β べーた
v
)
{\displaystyle (u\alpha v,\,u\beta v)}
を
G
{\displaystyle G\,}
のプロダクション(生成 せいせい 規則 きそく )と呼 よ び、一般 いっぱん に
u
α あるふぁ
v
→
u
β べーた
v
{\displaystyle u\alpha v\rightarrow u\beta v}
のように表記 ひょうき する。
任意 にんい の
u
,
v
∈
(
V
∪
Σ しぐま
)
∗
{\displaystyle u,v\in (V\cup \Sigma )^{*}}
について、
u
{\displaystyle u\,}
が
v
{\displaystyle v\,}
を生成 せいせい することを
u
⇒
v
{\displaystyle u\Rightarrow v}
で表 あらわ す。ただし、
u
=
u
1
α あるふぁ
u
2
{\displaystyle u\,=u_{1}\alpha u_{2}}
かつ
v
=
u
1
β べーた
u
2
{\displaystyle v\,=u_{1}\beta u_{2}}
で
∃
(
α あるふぁ
,
β べーた
)
∈
R
,
u
1
,
u
2
∈
(
V
∪
Σ しぐま
)
∗
{\displaystyle \exists (\alpha ,\beta )\in R,u_{1},u_{2}\in (V\cup \Sigma )^{*}}
が成 な りたねばならない。
任意 にんい の
u
,
v
∈
(
V
∪
Σ しぐま
)
∗
{\displaystyle u,v\in (V\cup \Sigma )^{*}}
について、
u
⇒
∗
v
{\displaystyle u{\stackrel {*}{\Rightarrow }}v}
(あるいは
u
⇒⇒
v
{\displaystyle u\Rightarrow \Rightarrow v}
)であるとは、
u
⇒
u
1
⇒
u
2
⋯
⇒
u
k
⇒
v
{\displaystyle u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v}
となるような
∃
u
1
,
u
2
,
⋯
u
k
∈
(
V
∪
Σ しぐま
)
∗
,
k
≥
0
{\displaystyle \exists u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0}
が成 な り立 た つ場合 ばあい である。
文法 ぶんぽう
G
=
(
V
,
Σ しぐま
,
R
,
S
)
{\displaystyle G=(V\,,\Sigma \,,R\,,S\,)}
の言語 げんご は次 つぎ の集合 しゅうごう で表 あらわ される。
L
(
G
)
=
{
w
∈
Σ しぐま
∗
:
S
⇒
∗
w
}
{\displaystyle L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}}
言語 げんご
L
{\displaystyle L\,}
は、
L
=
L
(
G
)
{\displaystyle L\,=\,L(G)}
となるような文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう
G
{\displaystyle G\,}
が存在 そんざい するとき、文脈 ぶんみゃく 自由 じゆう 言語 げんご (CFL)であるという。
最初 さいしょ の例 れい を示 しめ す。
ここで、 | は「選択 せんたく 」を意味 いみ し、ε いぷしろん は空 そら の文字 もじ 列 れつ を意味 いみ する。この文法 ぶんぽう によって生成 せいせい される言語 げんご は以下 いか のようになる。
{
a
n
b
n
:
n
≥
0
}
{\displaystyle \{a^{n}b^{n}:n\geq 0\}}
これは正規 せいき 言語 げんご ではない例 れい でもある。
また、「選択 せんたく 」は文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう の表現 ひょうげん に必 かなら ずしも必須 ひっす ではない。次 つぎ の2つの規則 きそく でも、上 うえ の例 れい と同様 どうよう の言語 げんご を定義 ていぎ している。
次 つぎ は三 さん 種類 しゅるい の変数 へんすう x, y, z を使 つか った文法 ぶんぽう 的 てき に正 ただ しい四則 しそく 演算 えんざん の数式 すうしき を生成 せいせい する文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう である。ここで演算 えんざん 子 こ は中置 ちゅうち としている。
S → x | y | z | S + S | S - S | S * S | S/S | (S)
この文法 ぶんぽう に従 したが うと、例 たと えば "( x + y ) * x - z * y / ( x + x )" といった式 しき が生成 せいせい 可能 かのう である。
この文法 ぶんぽう は、構造 こうぞう が異 こと なる構文 こうぶん 木 き から同 おな じ文字 もじ 列 れつ が生成 せいせい されうるという意味 いみ で曖昧 あいまい である。
文字 もじ セット {a,b} について、異 こと なる個数 こすう の a と b から構成 こうせい される全 すべ ての文字 もじ 列 れつ を生成 せいせい する文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう は以下 いか のようになる。
S → U | V
U → TaU | TaT
V → TbV | TbT
T → aTbT | bTaT | ε いぷしろん
ここで、T に関 かん する生成 せいせい 規則 きそく は a と b が同数 どうすう の文字 もじ 列 れつ を生成 せいせい するが、U は a の方 ほう が必 かなら ず多 おお くなる文字 もじ 列 れつ を生成 せいせい し、V は b の方 ほう が必 かなら ず多 おお くなる文字 もじ 列 れつ を生成 せいせい する。
次 つぎ の例 れい は
{
a
n
b
m
c
m
+
n
:
n
≥
0
,
m
≥
0
}
{\displaystyle \{a^{n}b^{m}c^{m+n}:n\geq 0,m\geq 0\}}
である。これは正規 せいき 言語 げんご ではなく文脈 ぶんみゃく 自由 じゆう 言語 げんご である。以下 いか の生成 せいせい 規則 きそく で生成 せいせい される(この生成 せいせい 規則 きそく は文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう にしたがっている)。
S → aSc | B
B → bBc | ε いぷしろん
文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう は数学 すうがく 的 てき な「形式 けいしき 的 てき 」言語 げんご だけで利用 りよう されるわけではない。例 たと えば、タミル語 ご の詩 し である Venpa は文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう で定式 ていしき 化 か できることが指摘 してき されている[ 3] 。
ある文法 ぶんぽう において、開始 かいし 記号 きごう からある文字 もじ 列 れつ が導出 みちびきだ される過程 かてい を記述 きじゅつ する方法 ほうほう は二 に 種類 しゅるい 存在 そんざい する。単純 たんじゅん な方法 ほうほう は導出 どうしゅつ 過程 かてい の途中 とちゅう の文字 もじ 列 れつ を全 すべ て書 か き出 だ していく方法 ほうほう である。つまり開始 かいし 記号 きごう から始 はじ めて、生成 せいせい 規則 きそく を一 いち 回 かい 適用 てきよう する度 たび に文字 もじ 列 れつ を書 か き出 だ して、最後 さいご に目的 もくてき の文字 もじ 列 れつ になるまで列挙 れっきょ するのである。例 たと えば「左端 ひだりはし に最 もっと も近 ちか い非終端 ひしゅうたん 記号 きごう を最初 さいしょ に書 か き換 か える」という規則 きそく を適用 てきよう したとすれば、文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう では適用 てきよう する生成 せいせい 規則 きそく を列挙 れっきょ するだけで十分 じゅうぶん である。これを文字 もじ 列 れつ の「左端 ひだりはし 導出 どうしゅつ 」(Leftmost Derivation)と呼 よ ぶ。例 たと えば、以下 いか の文法 ぶんぽう があるとする。
(1) S → S + S
(2) S → 1
(3) S → a
文字 もじ 列 れつ 「1 + 1 + a」を導出 どうしゅつ する過程 かてい は [ (1), (1), (2), (2), (3) ] というリストになる。同様 どうよう に「右 みぎ 端 はし 導出 どうしゅつ 」も定義 ていぎ できる。この例 れい の場合 ばあい 、右 みぎ 端 はし 導出 どうしゅつ での導出 どうしゅつ 過程 かてい は [ (1), (3), (1), (2), (2)] というリストになる。
左端 ひだりはし 導出 どうしゅつ と右 みぎ 端 はし 導出 どうしゅつ のリストが異 こと なるのは重要 じゅうよう なポイントである。構文 こうぶん 解析 かいせき では、文法 ぶんぽう 規則 きそく 毎 ごと にそれを入力 にゅうりょく 文字 もじ 列 れつ に適用 てきよう する小 ちい さなプログラムが存在 そんざい する。したがって、構文 こうぶん 解析 かいせき が左端 ひだりはし 導出 どうしゅつ を行 おこな うのか右 みぎ 端 はし 導出 どうしゅつ を行 おこな うのかによってそれらのプログラムを適用 てきよう する順番 じゅんばん が変 か わってくるのである。
導出 どうしゅつ 過程 かてい は導出 みちびきだ される文字 もじ 列 れつ 上 じょう にある種 しゅ の階層 かいそう 構造 こうぞう を描 えが くことでも表 あらわ される。例 れい として左端 ひだりはし 導出 どうしゅつ による「1 + 1 + 1」に対 たい する階層 かいそう 構造 こうぞう を見 み てみよう。導出 どうしゅつ 過程 かてい は以下 いか のようになる。
S→S+S (1)
S→S+S+S (1)
S→1+S+S (2)
S→1+1+S (2)
S→1+1+1 (2)
{ { { 1 }S + { 1 }S }S + { 1 }S }S
ここで { ... }S は S から導出 みちびきだ された部分 ぶぶん 文字 もじ 列 れつ を意味 いみ している。これに対応 たいおう する階層 かいそう 構造 こうぞう は以下 いか のような木 き 構造 こうぞう になる。
S
/|\
/ | \
/ | \
S '+' S
/|\ |
/ | \ |
S '+' S '1'
| |
'1' '1'
この木 き 構造 こうぞう をその文字 もじ 列 れつ の「具象 ぐしょう 構文 こうぶん 木 き 」と呼 よ ぶ(抽象 ちゅうしょう 構文 こうぶん 木 き も参照 さんしょう されたい)。この場合 ばあい 、上述 じょうじゅつ の左端 ひだりはし 導出 どうしゅつ も右 みぎ 端 はし 導出 どうしゅつ も同 おな じ構文 こうぶん 木 き になるが、左端 ひだりはし 導出 どうしゅつ には以下 いか のような別 べつ の導出 どうしゅつ 過程 かてい が存在 そんざい する。
S→ S + S (1)
S→ 1 + S (2)
S→ 1 + S + S (1)
S→ 1 + 1 + S (2)
S→ 1 + 1 + 1 (2)
これによって定義 ていぎ される構文 こうぶん 木 き は以下 いか のようになる。
S
/|\
/ | \
/ | \
S '+' S
| / |\
| / | \
'1' S '+' S
| |
'1' '1'
この文法 ぶんぽう のように、ある文字 もじ 列 れつ を導出 どうしゅつ する構文 こうぶん 木 き が複数 ふくすう 考 かんが えられる文法 ぶんぽう を「曖昧 あいまい な文法 ぶんぽう 」(Ambiguous Grammar )と呼 よ ぶ。このような文法 ぶんぽう の構文 こうぶん 解析 かいせき は、生成 せいせい 規則 きそく の適用 てきよう 順序 じゅんじょ を毎回 まいかい 決定 けってい しなければならないため難 むずか しい。
空 そら の文字 もじ 列 れつ を生成 せいせい しない文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう は等価 とうか なチョムスキー標準 ひょうじゅん 形 がた かグライバッハ標準 ひょうじゅん 形 がた に変換 へんかん できる。ここでいう「等価 とうか 」とは同 おな じ言語 げんご を生成 せいせい するという意味 いみ である。
チョムスキー標準 ひょうじゅん 形 がた 文法 ぶんぽう は生成 せいせい 規則 きそく が単純 たんじゅん なので、この標準 ひょうじゅん 形 がた は理論 りろん 的 てき にも実用 じつよう 上 じょう も密接 みっせつ な関係 かんけい がある。例 たと えば、ある文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう についてチョムスキー標準 ひょうじゅん 形 がた を使 つか うことで多項式 たこうしき 時間 じかん のアルゴリズムで入力 にゅうりょく された文字 もじ 列 れつ がその文法 ぶんぽう で生成 せいせい されるものか否 ひ かを判定 はんてい できる(CYKアルゴリズム )。
文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう は能力 のうりょく が制限 せいげん されているため、その操作 そうさ の一部 いちぶ は決定 けってい 可能 かのう であるが、同時 どうじ に決定 けってい 不能 ふのう な問題 もんだい もある。最 もっと も単純 たんじゅん で分 わ かり易 やす い決定 けってい 不能 ふのう 問題 もんだい の1つとして、CFG が言語 げんご の全 ぜん 文字 もじ 列 れつ を受容 じゅよう するかどうかという問題 もんだい がある。還元 かんげん によって、この問題 もんだい がチューリングマシンの停止 ていし 問題 もんだい と同 おな じであることが示 しめ される。その還元 かんげん には、チューリングマシン のあらゆる計算 けいさん 過程 かてい を示 しめ す「計算 けいさん 履歴 りれき 」と呼 よ ばれる概念 がいねん を用 もち いる。あるチューリングマシンがある入力 にゅうりょく を与 あた えられたとき、それを受容 じゅよう しない計算 けいさん 履歴 りれき の文字 もじ 列 れつ を生成 せいせい するCFGを構築 こうちく でき、そうすると、そのCFGはマシンが入力 にゅうりょく を受容 じゅよう しないときだけ文字 もじ 列 れつ を受容 じゅよう (認識 にんしき )する。
これを応用 おうよう すると、2つのCFGが同 おな じ言語 げんご を記述 きじゅつ しているかどうかも判定 はんてい 不能 ふのう である。なぜなら、言語 げんご の全 ぜん 文字 もじ 列 れつ を受理 じゅり する自明 じめい なCFGとの等価 とうか 性 せい を判定 はんてい できないためである。
また、文脈 ぶんみゃく 依存 いぞん 文法 ぶんぽう が文脈 ぶんみゃく 自由 じゆう 言語 げんご を表 あらわ しているかどうかも決定 けってい 不能 ふのう な問題 もんだい である。
文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう の形式 けいしき 性 せい の拡張 かくちょう として、非終端 ひしゅうたん 記号 きごう に引数 ひきすう を持 も たせ、規則 きそく 内 ない で値 ね を渡 わた すということが考 かんが えられる。これにより、自然 しぜん 言語 げんご の一致 いっち や参照 さんしょう といった機能 きのう を表現 ひょうげん 可能 かのう となり、プログラミング言語 げんご での識別子 しきべつし の定義 ていぎ や正 ただ しい用法 ようほう を自然 しぜん な形 かたち で表現 ひょうげん 可能 かのう となる。例 たと えば、英語 えいご の文 ぶん で、主語 しゅご と動詞 どうし が数 かず において合致 がっち しなければならないということを容易 ようい に表現 ひょうげん できる。
計算 けいさん 機 き 科学 かがく では、このようなアプローチの例 れい として接辞 せつじ 文法 ぶんぽう 、属性 ぞくせい 文法 ぶんぽう 、Van Wijngaarden の two-level grammar などがある。
同様 どうよう の拡張 かくちょう は言語 げんご 学 がく にもある。
別 べつ の拡張 かくちょう として、規則 きそく の左辺 さへん に追加 ついか の記号 きごう を書 か けるようにする手法 しゅほう がある。これは文脈 ぶんみゃく 依存 いぞん 文法 ぶんぽう に他 た ならない。
ノーム・チョムスキー 自身 じしん は、生 なま 成文法 せいぶんほう を追加 ついか することで文脈 ぶんみゃく 自由 じゆう 文法 ぶんぽう の制限 せいげん を克服 こくふく したいと考 かんが えていた[ 2] 。
そのような規則 きそく も言語 げんご 学 がく によく見 み られる。例 たと えば、英語 えいご における受動態 じゅどうたい 化 か である。しかし、それらは強力 きょうりょく すぎるため(チューリング完全 かんぜん )、変換 へんかん の適用 てきよう は制限 せいげん される必要 ひつよう がある。生 なま 成文法 せいぶんほう の大 だい 部分 ぶぶん は、句 く 構造 こうぞう 文法 ぶんぽう と変換 へんかん 規則 きそく の記述 きじゅつ 機構 きこう を改善 かいぜん し、自然 しぜん 言語 げんご が表現 ひょうげん できることを正確 せいかく に表 あらわ せるようにすることを目的 もくてき としている。
彼 かれ は自然 しぜん 言語 げんご が文脈 ぶんみゃく 自由 じゆう でないと考 かんが えていたが[ 4] 、彼 かれ がCFGでは不十分 ふじゅうぶん であることを示 しめ す証拠 しょうこ として挙 あ げた事例 じれい は、後 のち に間違 まちが いであることが証明 しょうめい された[ 5] 。Gerald Gazdar と Geoffrey Pullum は、一部 いちぶ に文脈 ぶんみゃく 自由 じゆう 的 てき でない構造 こうぞう があるものの、自然 しぜん 言語 げんご の大 だい 部分 ぶぶん は文脈 ぶんみゃく 自由 じゆう であると指摘 してき している[ 5] 。文脈 ぶんみゃく 自由 じゆう でない部分 ぶぶん とは、例 たと えば、スイスドイツ語 ご の cross-serial dependencies [ 4] や、バンバラ語 ご の畳語 じょうご である[ 6] 。
^ たとえばウィキペディア日本語 にほんご 版 ばん のこの部分 ぶぶん にはずっとそう書 か かれていた。
^ 『国語 こくご 学 がく 五 いつ つの発見 はっけん 再 さい 発見 はっけん 』(水谷 みずたに 静夫 しずお )§3.3.5.(p. 83)
^ a b Chomsky, Noam (1956年 ねん 9月 がつ ). “Three models for the description of language” . Information Theory, IEEE Transactions 2 (3): 113–124. http://ieeexplore.ieee.org/iel5/18/22738/01056813.pdf?isnumber=22738&prod=STD&arnumber=1056813&arnumber=1056813&arSt=+113&ared=+124&arAuthor=+Chomsky%2C+N . 2007年 ねん 6月 がつ 18日 にち 閲覧 えつらん 。 .
^ L, BalaSundaraRaman; S, Ishwar; Ravindranath, Sanjeeth Kumar (22 August 2003). "Context Free Grammar for Natural Language Constructs - An implementation for Venpa Class of Tamil Poetry" . Proceedings of Tamil Internet, Chennai, 2003 . International Forum for Information Technology in Tamil. pp. 128–136. 2006年 ねん 8月 がつ 24日 にち 閲覧 えつらん 。
^ a b Shieber, Stuart (1985年 ねん ). “Evidence against the context-freeness of natural language” . Linguistics and Philosophy 8 : 333–343. http://www.eecs.harvard.edu/~shieber/Biblio/Papers/shieber85.pdf .
^ a b Pullum, Geoffrey K.; Gerald Gazdar (1982年 ねん ). “Natural languages and context-free languages”. Linguistics and Philosophy 4 : 471–504.
^ Culy, Christopher (1985). “The Complexity of the Vocabulary of Bambara”. Linguistics and Philosophy 8 : 345–351.
Michael Sipser (1997). Introduction to the Theory of Computation . PWS Publishing. ISBN 0-534-94728-X Section 2.1: Context-Free Grammars, pp.91–101. Section 4.1.2: Decidable problems concerning context-free languages, pp.156–159. Section 5.1.1: Reductions via computation histories: pp.176–183.