2017-09-03 175 views
0

我有兩個問題要問,我也有一些關於它的想法。1或2右側變量上下文免費語言

1)每個規則的右手邊有1個終端或變量的X上下文無關文法(X-CFG)。

2)Y-CFG有2個終端或變量在每個規則的右側。

問題:

一)他們產生任何非正規的語言嗎?證明。

b)它們是否生成所有常規語言?證明。

答案:

一)我覺得對於X-CFG,它們不能產生任何非經常因爲它可以只能生成字符串的數量有限,使他們不能產生任何非正規語言。

b)有無限數量的常規語言,如^ *。我們不能用CFG生成無限的字符串,所以我們可以說它不能生成所有的正則語言。

我對不對?

我不知道問題b。

回答

0

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

+0

謝謝。我想如果我們右邊有1個變量(終端),這意味着我們只能生成有限的字符串。所以對於X-CFG問題(a)和(b)是錯誤的。但是如果我們右邊有兩個變量,這意味着我們可以像您的示例那樣生成一些非常規語言。 (b)部分如何? –

+0

添加了更新以進一步闡明我的想法,因爲我認爲我已經回答了部分b。 – fjoe

+0

非常感謝你。 –