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

Question

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

1. 线性语言：对于哪些线性文法是可能的（？CFG）例如
   L ₁ = {a ⁿ b ⁿ | ? 0 }

2. 确定性上下文无关语言（D-CFG）：对于哪些确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | ? 0，米？0 }
   L ₂是明确的。

非线性的CF 文法是非线性的。
L _nl = {w: n _a (w) = n _b (w)} 也是一个非线性 CFG。

-- 3. Non-Deterministic Context Free Language(N-CFG) : 对于哪个only Non-Deterministic Push-Down-Automata(N-PDA)是可能的，例如
L ₃ = {ww ^R | ? {a, b} ^* }
L ₃也是线性CFG。

--4. Ambiguous CFL：only ambiguous CFG is possible
L ₄ = {a ⁿ b ⁿ c ^m |的CFL ? 0，米？0 } U {a ⁿ b ^m c ^m | ? 0，米？0 }
L ₄既是非线性的又是模糊的 CFG 和每个模糊的 CFL \subseteq N-CFL。

我的问题是：
是否所有非线性、非确定性 CFL 都是模棱两可的？如果不是，那么我需要一个非线性、非确定性 CFL 且明确的示例？

给出下面的维恩图：

还在这里问

Answer 1

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

(1) L ₃ = {ww ^R | ? {a, b} ^* }

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

(2) L _p为括号匹配语言。有两个终结符“(”和“)”。
L _{p 的}语法是：

S ? SS
S ? (S)
S ? ()   

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

作为 L _p和 L ₃并集的语言L是明确的、非线性的（由于 L _p）和非确定性的（由于 L ₃）（假设两种语言的语言符号不同）。

这种语言是我标记为维恩图中的语言的一个例子??。

另外正确的图如下：

模棱两可的上下文无关语言也是线性上下文无关的