非线性，不确定性和不确定性CFL的示例? [英] Example of Non-Linear, UnAmbiguous and Non-Deterministic CFL?

问题描述

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

In the Chomsky classification of formal languages, I need some examples of Non-Linear, Unambiguous and also Non-Deterministic Context-Free-Language(N-CFL)?

1. 线性语言:对于哪个线性语法可能(⊆CFG)，例如
   L ₁ = {a ⁿ b ⁿ | n≥0}

1. Linear Language: For which Linear grammar is possible( ⊆ CFG) e.g.
   L₁ = {aⁿbⁿ | n ≥ 0 }

确定性上下文无关语言(D-CFG):例如，对于确定性下推自动机(D-PDA)可能是可行的，
L ₂ = {a ⁿ b ⁿ c ^m | n≥0，m≥0}
L ₂ 是明确的.

Deterministic Context Free Language(D-CFG): For which Deterministic Push-Down-Automata(D-PDA) is possible e.g.
L₂ = {aⁿbⁿc^m | n ≥ 0, m ≥ 0 }
L₂ is unambiguous.

CF语法为

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)的语言，例如
L ₃ = {ww ^R | w∈{a，b} ^* }
L ₃ 也是线性CFG.

-- 3. Non-Deterministic Context Free Language(N-CFG): For which only Non-Deterministic Push-Down-Automata(N-PDA) is possible e.g.
L₃ = {ww^R | w ∈ {a, b}^* }
L₃ is also Linear CFG.

-4. 歧义CFL :only ambiguous CFG is possible
的CFL L ₄ = {a ⁿ b ⁿ c ^m | n≥0，m≥0} U {a ⁿ b ^m c ^m | n≥0，m≥0}
L ₄ 既是非线性CFG，又是歧义CFG，每个歧义CFL \ subseteq N-CFL.

--4. Ambiguous CFL: CFL for which only ambiguous CFG is possible
L₄ = {aⁿbⁿc^m | n ≥ 0, m ≥ 0 } U {aⁿb^mc^m | n ≥ 0, m ≥ 0 }
L₄ is both non-linear and Ambiguous CFG And Every Ambigous CFL \subseteq N-CFL.

我的问题是:
是否所有非线性，不确定性CFL都是模棱两可的?如果没有的话 我需要一个非线性，不确定性CFL且也明确的示例吗?

My Question is:
Whether all non-linear, Non-Deterministic CFL are Ambiguous? If not then I need a example that is non-linear, non-deterministic CFL and also unambiguous?

下面给出维恩图:

也请此处

推荐答案

在正式语言的乔姆斯分类法中"

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

"IN CONTEXT OF CHOMSHY CLASSIFICATION OF FORMAL LANGUAGE"

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

• 语言L ₃ 是一种不确定的上下文无关语言，它也是不含糊和线性的语言.

• Language L₃ is a Non-Deterministic Context Free Language, its also Unambiguous and Liner language.

(2) L _p 是括号匹配的语言.有两个终端符号("和)".
L _p 的语法是:

(2) L_p is language of parenthesis matching. There are two terminal symbols "(" and ")".
Grammar for L_p is:

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

• 该语言也是非线性，确定性和明确的.

Language L 是明确的，非线性的(由于L _p )和不确定(由于L ₃ )(假设两种语言的语言符号不同).

Language L that is union of L_p and L₃ is unambiguous, nonlinear (due to L_p), and non-deterministic (due to L₃) (Assuming language symbols for both languages are different).

此语言是Venn图表中我标记为??的语言的示例.

This Language is an example of language in Venn-diagram for which I marked ??.

下面是正确的图:

一种模棱两可的上下文无关语言也是一种班轮上下文免费

这篇关于非线性，不确定性和不确定性CFL的示例?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！