推导有限自动机识别的语言的正则文法
Deriving a regular grammar for the language recognised by the Finite Automata
我无法弄清楚如何为有限自动机识别的语言推导常规语法。我面临的关键问题是常规语法和上下文无关语法之间的混淆。我似乎无法区分它们之间的区别，我发现它们在某些方面非常相似，例如歧义。
谁能解释一下如何为 FA 识别的语言推导正则文法？
当我们谈论正则语法时，我们可能在谈论（严格）正则语法或（扩展) 常规文法。这些不同的概念或多或少分别对应于 DFA 和具有空转换的广义 NFA。
此外，正则文法是右正则或左正则。我发现右正则语法更容易思考，但你的里程可能会有所不同。
给定一个 DFA，一个（严格的）右正则文法可以产生如下：
- N=Q；语法的非终结符集是 DFA 的状态集。
- S = q0;语法的起始符号是DFA的初始状态。
- 当且仅当 DFA 在输入 a 上从状态 X 到状态 Y 存在转换时，P 将包含非终结符 X 和 Y 的产生式 X := aY 和字母符号 a。
- P 将包含产生式 X := a 表示非终结符 X 和字母符号 a 当且仅当 DFA 中存在从状态 X 到输入 a 上的某个接受状态的转换时。
- 当且仅当状态 q0 在 DFA 中接受时，P 将包含产生式 q0 := e。
以上构造试图避免添加不必要的空产生式。如果我们不介意有很多空产生式，另一种方法是省去第 4 步，在第 5 步中添加转换 X := e 当且仅当 X 是接受状态。这具有相同的效果。
给定一个带有空转换的广义 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 和常规语言...所有常规语言都是上下文无关的，但反之亦然。 为什么？
我们可以通过使用 抽取引理 并抽取 {a^n b^n | 描述的上下文无关语言来证明这一点n ≥ 0} 表明它不是正则的，但它是 CFL 因为它是由文法 G = (V, Σ, R, Start) 生成的，其中：
- V：一组有限的变量或非终结符，例如 V = {S}
- Σ：与 V 不相交的有限集，称为字母表或终结符，例如 Σ = {a,b}
- R: 是一组产生式规则，每条规则例如 R = {S → aSb, S → ε}
- S: 开始变量 E.g Start = {S}
注意一个字符串w在上下文无关文法G中是歧义导出的，如果它有两个或更多不同个最左边的推导。如果一个文法 G 生成一些字符串有歧义，那么它就是有歧义的，有时，当我们有一个有歧义的文法时，我们可以找到一个明确的文法来生成 same 语。请注意，某些上下文无关语言 只能 由歧义语法生成——称为固有歧义。
此外，任何上下文无关语言都是由乔姆斯基范式中的上下文无关文法生成的。要检查字符串是否是 CFL 的一部分，我们可以使用 Cocke-Younger-Kasami 算法.
Sipser, M. (2006) 是一本不错的书。计算理论导论（第 2 卷）。波士顿：汤姆森课程技术。
我无法弄清楚如何为有限自动机识别的语言推导常规语法。我面临的关键问题是常规语法和上下文无关语法之间的混淆。我似乎无法区分它们之间的区别，我发现它们在某些方面非常相似，例如歧义。
谁能解释一下如何为 FA 识别的语言推导正则文法？
当我们谈论正则语法时，我们可能在谈论（严格）正则语法或（扩展) 常规文法。这些不同的概念或多或少分别对应于 DFA 和具有空转换的广义 NFA。
此外，正则文法是右正则或左正则。我发现右正则语法更容易思考，但你的里程可能会有所不同。
给定一个 DFA，一个（严格的）右正则文法可以产生如下：
- N=Q；语法的非终结符集是 DFA 的状态集。
- S = q0;语法的起始符号是DFA的初始状态。
- 当且仅当 DFA 在输入 a 上从状态 X 到状态 Y 存在转换时，P 将包含非终结符 X 和 Y 的产生式 X := aY 和字母符号 a。
- P 将包含产生式 X := a 表示非终结符 X 和字母符号 a 当且仅当 DFA 中存在从状态 X 到输入 a 上的某个接受状态的转换时。
- 当且仅当状态 q0 在 DFA 中接受时，P 将包含产生式 q0 := e。
以上构造试图避免添加不必要的空产生式。如果我们不介意有很多空产生式，另一种方法是省去第 4 步，在第 5 步中添加转换 X := e 当且仅当 X 是接受状态。这具有相同的效果。
给定一个带有空转换的广义 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 和常规语言...所有常规语言都是上下文无关的，但反之亦然。 为什么？
我们可以通过使用 抽取引理 并抽取 {a^n b^n | 描述的上下文无关语言来证明这一点n ≥ 0} 表明它不是正则的，但它是 CFL 因为它是由文法 G = (V, Σ, R, Start) 生成的，其中：
- V：一组有限的变量或非终结符，例如 V = {S}
- Σ：与 V 不相交的有限集，称为字母表或终结符，例如 Σ = {a,b}
- R: 是一组产生式规则，每条规则例如 R = {S → aSb, S → ε}
- S: 开始变量 E.g Start = {S}
注意一个字符串w在上下文无关文法G中是歧义导出的，如果它有两个或更多不同个最左边的推导。如果一个文法 G 生成一些字符串有歧义，那么它就是有歧义的，有时，当我们有一个有歧义的文法时，我们可以找到一个明确的文法来生成 same 语。请注意，某些上下文无关语言 只能 由歧义语法生成——称为固有歧义。
此外，任何上下文无关语言都是由乔姆斯基范式中的上下文无关文法生成的。要检查字符串是否是 CFL 的一部分，我们可以使用 Cocke-Younger-Kasami 算法.
Sipser, M. (2006) 是一本不错的书。计算理论导论（第 2 卷）。波士顿：汤姆森课程技术。