finite-automata - 非線形で、曖昧でなく、非決定論的な CFL の例?

Question

フォーマル言語のチョムスキー分類では、Non-Linear, Unambiguous and also Non-DeterministicContext-Free-Language(N-CFL) の例が必要ですか?

1. 線形言語:線形文法が可能なもの ( ⊆ CFG) 例:
   L ₁ = {a ⁿ b ⁿ | n ≥ 0 }

2. Deterministic Context Free Language(D-CFG) : Deterministic Push-Down-Automata(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 ₃も Linear CFG です。

--4. あいまいな CFL : only ambiguous CFG is possible
L ₄ = { a ⁿ b ^{n cm} | n ≥ 0, m ≥ 0 } U { a ⁿ b ^{m cm} | n ≥ 0, m ≥ 0 }
L ₄は非線形かつ曖昧な CFG であり、すべての曖昧な CFL \subseteq N-CFL.

私の質問は次のとおりです:
すべての非線形、非決定論的 CFL は曖昧ですか? そうでない場合は、非線形で非決定論的な CFL であり、明確な例が必要ですか?

以下にベン図を示します。

ここでも質問

Answer 1

「フォーマル言語のチョムシー分類の文脈で」

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

• 言語 L ₃ は、非決定論的文脈自由言語であり、明確でライナーな言語でもあります。

(2) L _pは、括弧の一致の言語です。2 つの終端記号 "(" と ")" があります。
L _pの文法は次のとおりです。

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

• この言語は非線形で、決定論的で、曖昧さもありません。

_{L p}と L ₃の結合である言語Lは、明確で、非線形 (L _pによる) であり、非決定論的 (L ₃による) です (両方の言語の言語記号が異なると仮定します)。

この言語は、私がマークしたベン図の言語の例です??。

また、正しい図は次のとおりです。

あいまいな文脈自由言語は、ライナー文脈自由でもあります