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 .
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的链接答案中,常规语法只是有限自动机中存在的相同基础信息的替代符号 . 这与正则表达式根本不同,正则表达式是用于表示常规语言的根本不同(但是等效)的表示法 .
我理解它的方式是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卷) . 波士顿:汤姆森球场技术 .