檢查是否正規語言給CF語法

Question

我有這樣的語法
S->aSbA S->e A->aB B->bA

我怎麼能確定如果語言是正常嗎？我的問題是，A和B沒有終端字符，所以我不知道它會產生什麼語言。

Answer 1

有沒有這方面的一般方法。對於上下文無關語言來說，規律性是不可判定的問題。

在您的具體情況下，正如J厄爾斯指出的那樣，您唯一可以推導出的詞是空白詞。所有使用不同於S - > e的規則的派生都不會終止。因此，語言是有限的，因此是規則的。