证明上下文无关文法是正则的
Prove that a context-free-grammar is regular
我知道要证明一种语言是非常规的，可以使用泵引理。我想我明白它是如何工作的，但是当要表明上下文无关语法是（或不是规则的）时，我遇到了大问题。
这里有一个 CFG 的例子，我不明白如何显示它是规则的（或非规则的）：
i) S → NP VP
ii) NP → DET N
iii) VP → TV NP
iv) N → N N
v) N → A N
vi) NP → Mary |John
vii) DET → a |the |her |his
viii) TV → bought |loves |misses
ix) N → bike |jersey |mountain |sleeve |brake |
x) A → long |hydraulic |knitted |expensive |steep
我最初的猜测是，由于第四条规则，它不是正则的，但我不知道如何使用泵引理来显示它。如果第四条规则被删除，它会是规则的吗？
所以，我的问题是：
1、以上语法是否正则？当试图表明这样的 CFG 是规则的还是非规则的时，采用什么方法？
2. 如果去掉递归规则，那么是正则还是非正则？
我希望有人有一些工具，当有人想要证明它是规则的还是不规则的时，当给出像上面这样的 CFG 时，这些工具很有用。
想指出的是有两点需要注意：
- 每个正则表达式 (RE) 也是一个 CFG，但反之则不然（参见 here）。因此，除非您的提问者知道给定的 CFG 也是一个 RE（由于问题的构造），否则它很可能不是 RE。
- 如果给定 CFG 等价于 RE（不可判定问题），则无法计算给定的 CFG 参见 here
综上所述，Am_I_Helpful 的回答没有理论依据，不应使用。
此处的其他答案指出了我认为您可能遗漏的细微差别。上下文无关文法是一组描述语言的规则，但它本身并不是一种语言。因此，询问 上下文无关文法 是否正则不是一个有意义的问题 - 这就像询问所有自然数的集合是否可以被 17 整除。
另一方面，问题 "is the language described by this CFG a regular language?" 是一个有意义的问题，在这种情况下，答案是肯定的。为了展示这一点，您需要弄清楚所描述的语言实际上是什么样的，然后可以为它构建一个 DFA/NFA，为它编写一个正则表达式，或者为它编写一个常规语法。在这种特殊情况下，经过一些思考我们可以看出语法等同于以下正则表达式：
(MJ | DET (A* N)*) TV (MJ | DET (A* N)*)
其中 MJ、DET、A、N 和 TV 是您提供的上下文无关语法中表示的列表给出的选择的简写（MJ 表示 "Mary or John."）因为您可以编写一个常规语法语言的表达式，你有的是
- 上下文无关语法，
- 那不是正规语法，但是
- 它描述了一种常规语言。
我知道要证明一种语言是非常规的，可以使用泵引理。我想我明白它是如何工作的，但是当要表明上下文无关语法是（或不是规则的）时，我遇到了大问题。
这里有一个 CFG 的例子，我不明白如何显示它是规则的（或非规则的）：
i) S → NP VP
ii) NP → DET N
iii) VP → TV NP
iv) N → N N
v) N → A N
vi) NP → Mary |John
vii) DET → a |the |her |his
viii) TV → bought |loves |misses
ix) N → bike |jersey |mountain |sleeve |brake |
x) A → long |hydraulic |knitted |expensive |steep
我最初的猜测是，由于第四条规则，它不是正则的，但我不知道如何使用泵引理来显示它。如果第四条规则被删除，它会是规则的吗？
所以，我的问题是： 1、以上语法是否正则？当试图表明这样的 CFG 是规则的还是非规则的时，采用什么方法？ 2. 如果去掉递归规则，那么是正则还是非正则？
我希望有人有一些工具，当有人想要证明它是规则的还是不规则的时，当给出像上面这样的 CFG 时，这些工具很有用。
想指出的是有两点需要注意：
- 每个正则表达式 (RE) 也是一个 CFG，但反之则不然（参见 here）。因此，除非您的提问者知道给定的 CFG 也是一个 RE（由于问题的构造），否则它很可能不是 RE。
- 如果给定 CFG 等价于 RE（不可判定问题），则无法计算给定的 CFG 参见 here
综上所述，Am_I_Helpful 的回答没有理论依据，不应使用。
此处的其他答案指出了我认为您可能遗漏的细微差别。上下文无关文法是一组描述语言的规则，但它本身并不是一种语言。因此，询问 上下文无关文法 是否正则不是一个有意义的问题 - 这就像询问所有自然数的集合是否可以被 17 整除。
另一方面，问题 "is the language described by this CFG a regular language?" 是一个有意义的问题，在这种情况下，答案是肯定的。为了展示这一点，您需要弄清楚所描述的语言实际上是什么样的，然后可以为它构建一个 DFA/NFA，为它编写一个正则表达式，或者为它编写一个常规语法。在这种特殊情况下，经过一些思考我们可以看出语法等同于以下正则表达式：
(MJ | DET (A* N)*) TV (MJ | DET (A* N)*)
其中 MJ、DET、A、N 和 TV 是您提供的上下文无关语法中表示的列表给出的选择的简写（MJ 表示 "Mary or John."）因为您可以编写一个常规语法语言的表达式，你有的是
- 上下文无关语法，
- 那不是正规语法，但是
- 它描述了一种常规语言。