首页 文章

非线性，非确定性和非确定性CFL的例子？

提问于
浏览 次
4

在正式语言的乔姆斯基分类中，我需要一些 Non-Linear, Unambiguous and also Non-Deterministic Context-Free-Language（N-CFL）的例子？

  • Linear Language ：对于which Linear grammar是可能的（⊆CFG），例如
    L1 = {anbn | n≥0}

  • Deterministic Context Free Language(D-CFG) ：对于哪种确定性下推式自动机（D-PDA）是可能的，例如
    L2 = {anbncm | n≥0，m≥0}
    L2是明确的 .

非线性的CF语法是非线性的 . Ln1 = {w：na（w）= nb（w）}也是非线性CFG .

    1. Non-Deterministic Context Free Language(N-CFG) ：可以使用 only Non-Deterministic Push-Down-Automata(N-PDA) ，例如
      L3 = {wwR | w∈{a，b} *}
      L3也是线性CFG .

--4 . Ambiguous CFL ：CFL为 only ambiguous CFG is possible
L4 = {anbncm | n≥0，m≥0} U {anbmcm | n≥0，m≥0}
L4既是非线性的，也是模糊的CFG和每个Ambigous CFL \ subseteq N-CFL .

My Question is:
是否所有非线性，非确定性CFL都是不明确的？如果没有，那么我需要一个非线性，非确定性CFL的例子，也是明确的？

Given Venn-diagram below:

还问here

finite-automata automata computation-theory formal-languages chomsky-hierarchy

1 回答

  • 4

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

    （1） L3 = {wwR | w∈{a，b} *}

    • 语言L3是一种非确定性的上下文无关语言，它也是明确的和线性语言 .

    （2） Lp 是括号匹配的语言 . 有两个终端符号"("和")" .
    Lp的语法是：

    S → SS
S → (S)
S → ()
    • 这种语言也是非线性的，确定性的和明确的 .

    作为Lp和L3的并集的语言 L 是明确的，非线性的（由于Lp），并且是非确定性的（由于L3）（假设两种语言的语言符号不同） .

    这个语言是维恩图中语言的一个例子，我将其标记为 ?? .

    正确的图表如下：

    An ambiguous context free language also be a liner context free

    回复于

相关问题