這個語法代表什麼語言？

Question

我相信這是一種以a開頭並以b結尾的語言，但我不確定。

G = (V,∑,P,S) where V={A,B,S,T}, ∑={a,b}, 
P = { S → ε | T | AB, T → aTb | ε, A → aA | Aaa | ε, B → bB | ε } 

Answer 1

看看開始。對於第一次替代，有三種可能性。如果它是S -> ε，你就完成了。所以該語言包含空字ε。如果第一個替換爲S -> T，T會發生什麼情況？簡單的，T可以變成ε或aTb，其他非終端不可能參與，所以生產產生子語言（我會留下你的工作，這是作業）。最後，如果第一個替代是S -> AB呢？看看從A resp開始的製作。 B，右側con只能包含一個非終結符，您開始的一個並且代入A可能會添加一個或兩個a，用B代替末尾（ε）或添加另一個b。那麼a和b哪些組合可以到達？ ba屬於該語言嗎？爲什麼要分開。爲什麼不？

提示：S -> AB -> Aε = A -> aA -> aε = a有效，所以非空字不必以b結尾。