finite-automata - 非线性、明确和非确定性 CFL 的示例？

Question

在形式语言的乔姆斯基分类中，我需要一些 Non-Linear, Unambiguous and also Non-Deterministic 的例子上下文无关语言(N-CFL)？

线性语言 : 对于 which Linear grammar是可能的( ⊆ CFG) 例如
L1 = {anbn | n ≥ 0 }

确定性上下文无关语言(D-CFG) :对于哪些确定性下推自动机(D-PDA)是可能的，例如
L2 = {anbncm | n≥0，m≥0}
L2 是明确的。

A CF grammar that is not linear is nonlinear.
L_nl = {w: n_a(w) = n_b(w)} is also a Non-Linear CFG.

——
3.
非确定性上下文无关语言(N-CFG) : 对于其中 only Non-Deterministic Push-Down-Automata(N-PDA)是可能的，例如
L3 = {wwR | w ∈ {a, b}* }
L3 也是线性 CFG。

--4. 模棱两可的节能灯 : CFL 的 only ambiguous CFG is possible L4 = {anbncm | n ≥ 0, m ≥ 0 } U {anbmcm | n≥0，m≥0}
L4 既是非线性的又是 Ambiguous CFG 和 Every Ambigous CFL\subseteq N-CFL。

我的问题是:
是否所有非线性、非确定性 CFL 都是 Ambiguous？如果没有那么
我需要一个非线性、非确定性 CFL 且明确的示例？

给出下面的维恩图:

还问 here

Answer 1

“在正式语言分类的背景下”

(1) L3 = {wwR | w ∈ {a, b}* }

语言 L3 是一种非确定性上下文无关语言，它也是无歧义和线性语言。

(2) LP 是括号匹配的语言。有两个终结符“(”和“)”。
Lp 的语法是:

S → SS
S → (S)
S → ()   

这种语言也是非线性的、确定性的和明确的。

语言 L 即 Lp 和 L3 的并集是明确的、非线性的(由于 Lp)和非确定性的(由于 L3)(假设两种语言的语言符号不同)。

这种语言是维恩图中语言的一个例子，我标记了 ?? .

另外正确的图如下:

An ambiguous context free language also be a liner context free