對於給定的語法

Question

DFA問題指定語言：編寫針對L一個完整的語法，包括四倍和生產規則

L ={x: ∃y ∈ {a, b}* : x = ay} 

答：

G={{S, A}, {a, b}, S, P} 
P: S => aA 
    A => aA | bA | λ 

我的問題是：

1. 爲什麼爲A，但沒有λ爲S？
2. 從語言定義來看，它是任何以a開頭並且只包含a和b的字符串，但是爲什麼在回答A => bA中。如果它是A => bA，是不是表示字符串以b開頭？

謝謝你這麼多

Answer 1

1.爲什麼有λ爲A，但沒有λ爲S？

λ nul可以從A派生出來，將感性從句子轉換爲句子。另外根據語言陳述，前綴子字符串y ∈ {a, b}*可以是nul（空字符串），例如"a"是一個屬於該語言的字符串。如果y包含任何符號，則語言長度將超過一個。

S不能派生λ因爲空（或者說nul字符串）不在語言中。語言中最小的字符串是單個"a"。

2.從語言定義，它是與a開始，只包含a的和b的任意字符串，但爲什麼在回答A => bA。如果它是A => bA，是不是表示字符串以b開頭？

注只有串那些可以從開始變S衍生包含在語法的語言。你不能從A開始派生（這不是開始變量）。如果你從S開始推導，你的字符串將始終以a符號開頭。

我建議你閱讀："Why the need for terminals? Is my solution sufficient enough?"我在哪裏寫的關於形式語法的基本定義。