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中的每種情況都是如此。所以我會說是的，你可以生成所有的常規語言。