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

Question

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

1. 线性语言：线性语法是可能的（⊆ CFG），例如
   L ₁ = {a ⁿ b ⁿ | n≥0}

2. 确定性上下文无关语言（D-CFG）：确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 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 | w ∈ {a, b} ^* }
L ₃也是线性CFG。

--4。模棱两可的 CFL : only ambiguous CFG is possible
L ₄ = {a ⁿ b ⁿ c ^m |的 CFL n ≥ 0, m ≥ 0 } U {a ⁿ b ^m c ^m | n ≥ 0, m ≥ 0 }
L ₄既是非线性又是模糊 CFG 和每个模糊 CFL \subseteq N-CFL。

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

给定下面的维恩图：

也在这里问

Answer 1

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

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

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

(2) L _p是括号匹配的语言。有两个终端符号“（”和“）”。
L _p的语法是：

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

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

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

这种语言是我标记的维恩图中的语言示例??。

正确的图表如下：

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