首页 文章

导出有限自动机识别的语言的常规语法

提问于
浏览
1

我无法找到有限自动机识别的语言的常规语法 . 我面临的关键问题是常规语法和无上下文语法之间的混淆 . 我似乎无法区分它们之间的差异,我发现它们在某些方面非常相似,例如歧义 .

任何人都可以解释如何获得FA认可的语言的常规语法?

2 回答

  • 2

    当我们谈论常规语法时,我们可能会谈论(严格地)常规语法或(扩展)常规语法 . 这些不同的概念或多或少精确地对应于DFA和具有空转换的广义NFA .

    此外,常规语法要么是正则的,要么是常规的 . 我发现正确的常规语法更容易思考,但你的里程可能会有所不同 .

    给定DFA,可以生成(严格)正确的常规语法,如下所示:

    • N = Q;语法的非终结符集是DFA的状态集 .

    • S = q0;语法的起始符号是DFA的初始状态 .

    • P将包含 生产环境 X:= aY表示非终结符号X和Y以及字母符号a当且仅当DFA在输入a上从状态X转换为状态Y时 .

    • P将包含 生产环境 X:= a表示非终结符号X和字母符号a当且仅当DFA从状态X转换到输入a处的某个接受状态时 .
      当且仅当状态q0在DFA中接受时,

    • P将包含 生产环境 q0:= e .

    上述结构试图避免添加不必要的空制作 . 如果我们不介意有很多空制作,另一种方法是省略步骤4,在步骤5中,当且仅当X是接受状态时,添加转换X:= e . 这具有相同的效果 .

    给定具有空转换的广义NFA,可以生成(扩展的)右对齐语法,如下所示:

    • N = Q;语法的非终结符集是gNFA-e的状态集 .

    • S = q0;语法的起始符号是gNFA-e的初始状态 .
      当且仅当gNFA-e在输入w上从状态X转换到状态Y时,

    • P将包含非终结符号X和Y的生成X:= wY和字母表中的字符串w .
      当且仅当状态X在gNFA-e中接受时,

    • P将包含 生产环境 X:= e .

    基本上,正如在rici的链接答案中,常规语法只是有限自动机中存在的相同基础信息的替代符号 . 这与正则表达式根本不同,正则表达式是用于表示常规语言的根本不同(但是等效)的表示法 .

  • -1

    我理解它的方式是CFL是以有限的方式描述无限集合以及描述语言语法的好方法 .

    CFL和常规语言...... All regular languages are context free, but not necessarily vice versa. 为什么?

    我们可以通过使用 pumping lemma 来证明这一点,并使用{a ^ n b ^ n |描述的上下文自由语言 . n≥0}表示它是 not regular but it is a CFL ,因为它是由语法G =(V,Σ,R,Start)生成的,其中:

    • V:一组有限的变量或非终结符E.g V =

    • Σ:与V不相交的有限集,称为字母或终端E.gΣ= {a,b}

    • R:是一套 生产环境 规则,每条规则E.g R = {S→aSb,S→ε}

    • S:起始变量E.g Start =

    注意 string w is derived ambiguously in a context-free grammar G if it has two or more different leftmost derivations . 如果语法G模糊地产生一些字符串,那么语法G是不明确的,有时,当我们有一个模糊的语法时,我们可以找到一个生成相同语言的明确语法 . 请注意,某些无上下文的语言只能由不明确的语法生成 - 称为 inherently ambiguous .

    此外,任何无上下文的语言都是由 Chomsky Normal Form 中的无上下文语法生成的 . 要检查字符串是否是CFL的一部分,我们可以使用 Cocke-Younger-Kasami algorithm .

    Sipser,M . (2006)是一本很好的读物 . 计算理论导论(第2卷) . 波士顿:汤姆森球场技术 .

相关问题