上下文無關語言的閉包性質是什麼？

上下文無關語言 (CFG) 的閉包性質如下：

對並集運算封閉

為了證明上下文無關語言對並集運算封閉，考慮兩個不同語言 L1 和 L2 的兩個起始變數 S1 和 S2。

並集運算的語法如下所示：

S -> S1 | S2

如果兩種語言都屬於上下文無關語言，那麼兩種語言的並集也應該屬於上下文無關語言。

根據上述定義，如果使用者生成 S1 和 S2 字串或兩者，則會生成兩種語言的並集。

因此，L1 U L2 ∈ CFL

所以，上下文無關語言對並集運算封閉。

對連線運算封閉

為了證明上下文無關語言對連線運算封閉，該運算考慮兩個不同語言 L1 和 L2 的兩個起始變數 S1 和 S2。

並集運算的語法如下所示：

S -> S1S2

如果兩種語言都屬於上下文無關語言，那麼兩種語言之一的連線也應該屬於上下文無關語言。

∀L₁L₂∈CFL

{W₁W₂:W₁∈L₁∈ΛW₂∈L₂}∈CFL

根據上述定義，如果使用者為語言 L1 生成 S1 字串，然後為語言 L2 生成 S2 字串，那麼就會生成兩種語言的連線。

因此，結果如下：

{W₁W₂:W₁∈L₁∈ΛW₂∈L₂}∈CFL

所以，上下文無關語言對連線運算封閉。

對 Kleene 星號運算封閉

為了證明上下文無關語言對 Kleene 星號運算封閉，考慮語言 L1 的一個起始變數 S1。

並集運算的語法如下所示：

S -> S1S | ε

如果該語言屬於上下文無關語言，那麼該語言的 Kleene 星號也應該屬於上下文無關語言。

∀L₁∈CFL

根據上述定義，如果使用者生成零個或多個字串（這是 Kleene 星號的定義），那麼上下文無關語言對 Kleene 星號運算封閉。

Bhanu Priya

更新於：2021年6月16日

4K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習