证明上下文无关语法是规则的 [英] Prove that a context-free-grammar is regular

问题描述

我知道，要证明一种语言是非常规语言，可以使用泵激引理。我想我知道它是如何工作的，但是当涉及到上下文无关语法是（或者不是很规则）时，我遇到了很大的问题。

I know that to prove that a language is non-regular one can use the pumping-lemma. I think I understand how it works, but when it comes to showing that a context-free-grammar is (or isn't regular) I'm having big problems.

以下是我无法理解如何显示常规（或非常规）CFG的示例：

Here is an example of a CFG that I can't understand how to show is regular (or non-regular):

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

我最初的猜测是由于第四条规则，它是不规则的，但是我不知道如何使用抽水引理展示它。如果删除了第四条规则，那么它会是常规的吗？

My initial guess is that it's not regular because of the fourth rule, but I have no idea how to show it using the pumping-lemma. And if the fourth rule was removed, would it then be regular?

所以，我的问题是：
1.上面的语法是否正常？试图显示这样的CFG是常规还是非常规的方法是什么？
2.如果删除了递归规则，那么规则是否正常？

So, my questions are: 1. Is the above grammar regular? What is the approach when trying to show that such a CFG is regular or non-regular? 2. If the recursive rule was removed, is it then regular or not?

我希望有人可以使用上面提到的CFG，当有人想表明它是否正常时，该工具很有用。

I hope someone have some tools that are useful when given such a CFG as the one above, when one wants to show that it's regular or not.

推荐答案

这里的其他答案都指向我认为您可能会丢失的细微差别。上下文无关的语法是描述语言的一组规则，但它本身不是语言。因此，询问无上下文语法是否正常不是一个有意义的问题-就像询问所有自然数的集合是否可被17整除。

The other answers here are pointing at a nuance that I think you may be missing. A context-free grammar is a set of rules that describe a language, but it itself is not a language. Therefore, asking if the context-free grammar is regular is not a meaningful question - it would be like asking whether the set of all natural numbers is divisible by seventeen.

另一方面，问题此CFG描述的语言是否为常规语言？是一个有意义的问题，在这种情况下，答案是肯定的。为了显示这一点，您需要弄清楚所描述语言的实际外观，然后可以为其构建DFA / NFA，为其编写正则表达式或为其编写常规语法。在这种特殊情况下，经过一番思考，我们可以看到语法等同于以下正则表达式：

On the other hand, the question "is the language described by this CFG a regular language?" is a meaningful question to ask, and in this case the answer is yes. To show this, you'll need to figure out what the described language actually looks like, then can either build a DFA/NFA for it, write a regex for it, or write a regular grammar for it. In this particular case, with some thought we can see that the grammar is equivalent to the following regex:

(MJ | DET (A* N)*) TV (MJ | DET (A* N)*)

其中MJ， DET，A，N和TV是您提供的上下文无关语法（MJ表示 Mary或John）中表示的列表所给出的选择的简写形式。因为您可以为语法的语言编写正则表达式，您拥有的是

where MJ, DET, A, N, and TV are shorthands for the choices given by the lists represented in the context-free grammar you provided (with MJ meaning "Mary or John.") Since you can write a regular expression for the language of the grammar, what you have is

• 上下文无关的语法，


• 这不是常规语法，但


• 描述了一种普通语言。

这篇关于证明上下文无关语法是规则的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！