1或2右侧变量上下文免费语言

Question

我有两个问题要问，我也有一些关于它的想法。

1）每个规则的右手边有1个终端或变量的X上下文无关文法（X-CFG）。

2）Y-CFG有2个终端或变量在每个规则的右侧。

问题：

一）他们产生任何非正规的语言吗？证明。

b）它们是否生成所有常规语言？证明。

答案：

一）我觉得对于X-CFG，它们不能产生任何非经常因为它可以只能生成字符串的数量有限，使他们不能产生任何非正规语言。

b）有无限数量的常规语言，如^ *。我们不能用CFG生成无限的字符串，所以我们可以说它不能生成所有的正则语言。

我对不对？

我不知道问题b。

Answer 1

考虑在Y-CFG：

 
S → aA 
S → ab 
A → Sb 

这是不是一个Y型CFG满足您的约束，并产生一个非正规的语言？一个^Ñ b ^Ñ使得n> = 1

另见this，因为它规定：

每个正规文法是上下文无关，但不是所有的上下文无关文法是常规。并用一个例子来解释一下为什么要帮助它。

所以我相信无论你的答案是错的，如果我理解正确的问题。

UPDATE

每一个正规文法是上下文无关。那么接下来的问题是我们可以定义所有CFG的使用2个变量（t是端和N为非终端）：

 
S → SS 
S → t 
S → N 
S → tN 
S → Nt 

因此，我们可以定义的东西，终止，事情从多个出发串长出来，事情在前面增长，在后面增长的东西。 CFG中的每种情况都是如此。所以我会说是的，你可以生成所有的常规语言。