上下文無關語法公式

Question

對CFG問題有些疑惑。

以下哪一項是允許這種語法

S -> aS | bA 
A -> c | cA 


A: a*bc* 
B: a*b*c* 
C: a*b*c 
D: a*bc+ 

我的困惑所在的*，這是我理解的意思0個或更多的時間內。

對於A，我看到這不起作用，因爲您可以有多個a（aS重複），接着是b（bA），接着是c。但是c不能有*，就好像你叫b（bA）一樣，A總會給出c。 *表示你可以有零。

對於B，我看到這不工作，因爲c有一個*最終適用同樣的規則。

對於C，我看到這MAYBE工作，因爲你可以有多個a（aS重複），其次是一個可能的b，其次是c。儘管由於b *我很困惑。這是否意味着它可能有多個b？如果是這樣，這將是不真實的，因爲'b'只能在上面定義的這種語法上下文中出現一次。

對於D，我發現這完全可以發生多次（aS重複），b會發生一次，並且c會發生一次或多次。

所以A不，B不，C可能嗎？D是。

這種想法是對還是錯？ *將我拋棄。

Answer 1

選項D完全代表語法，其他人總會在某個時候失敗，所以你說得對。選項A將失敗，因爲語法不允許'c'爲零，選項B和C將因爲只允許一個'b'而失敗。