非线性,不确定性和不确定性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)?
-
线性语言:对于哪个线性语法可能(⊆CFG),例如
L 1 = {a n b n | n≥0}
Linear Language: For which Linear grammar is possible( ⊆ CFG) e.g.
L1 = {anbn | n ≥ 0 }
确定性上下文无关语言(D-CFG):例如,对于确定性下推自动机(D-PDA)可能是可行的,
L 2 = {a n b n c m | n≥0,m≥0}
L 2 是明确的.
Deterministic Context Free Language(D-CFG): For which Deterministic Push-Down-Automata(D-PDA) is possible e.g.
L2 = {anbncm | n ≥ 0, m ≥ 0 }
L2 is unambiguous.
A CF grammar that is not linear is nonlinear.
Lnl = {w: na(w) = nb(w)} is also a Non-Linear CFG.
-
3.
不确定性上下文无关语言(N-CFG):可能使用only Non-Deterministic Push-Down-Automata(N-PDA)
的语言,例如
L 3 = {ww R | w∈{a,b} * }
L 3 也是线性CFG.
--
3.
Non-Deterministic Context Free Language(N-CFG): For which only Non-Deterministic Push-Down-Automata(N-PDA)
is possible e.g.
L3 = {wwR | w ∈ {a, b}* }
L3 is also Linear CFG.
-4. 歧义CFL :only ambiguous CFG is possible
的CFL
L 4 = {a n b n c m | n≥0,m≥0} U {a n b m c m | n≥0,m≥0}
L 4 既是非线性CFG,又是歧义CFG,每个歧义CFL \ subseteq N-CFL.
--4. Ambiguous CFL: CFL for which only ambiguous CFG is possible
L4 = {anbncm | n ≥ 0, m ≥ 0 } U {anbmcm | n ≥ 0, m ≥ 0 }
L4 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 3 = {ww R | w∈{a,b} * }
"IN CONTEXT OF CHOMSHY CLASSIFICATION OF FORMAL LANGUAGE"
(1) L3 = {wwR | w ∈ {a, b}* }
- 语言L 3 是一种不确定的上下文无关语言,它也是不含糊和线性的语言.
- Language L3 is a Non-Deterministic Context Free Language, its also Unambiguous and Liner language.
(2) L p 是括号匹配的语言.有两个终端符号("和)".
L p 的语法是:
(2) Lp is language of parenthesis matching. There are two terminal symbols "(" and ")".
Grammar for Lp is:
S → SS
S → (S)
S → ()
- 该语言也是非线性,确定性和明确的.
Language L 是明确的,非线性的(由于L p )和不确定(由于L 3 )(假设两种语言的语言符号不同).
Language L that is union of Lp and L3 is unambiguous, nonlinear (due to Lp), and non-deterministic (due to L3) (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屋!