正式和非正式地描述此语法的语言

Question

我有一个问题想寻求帮助：

正式和非正式地描述以下语法G = (Σ, N, S, P)的语言：

Σ = {a,b,c}
N = {S,T,X}
S = S
P = {
  S->aTXc,
  S->bTc,
  T->aTX,
  T->bT,
  TXX->T,
  Tc->empty string,
  TXc-a>
}

此外，简要和非正式地解释该语法如何产生其语言。

提示：使用|w|x表示法描述此语法的语言。

Answer 1

我相信语法语言

S   → bTc | aTXc
T   → bT | aTX
TXX → T
Tc  → λ
TXc → a

是(a|b)+。首先，考虑使用T产生式从T推导：

T ⇒* bnT   (T → bT)
T ⇒* anTXn (T → aTX)

其中n > 0。由于T → bT和T → aTX可以任意顺序应用，因此

T ⇒* uTX|u|a

其中u的形式为(a|b)+和|u|a ≥ 0。接下来，考虑生产TXX → T：

T ⇒* uTX|u|a ⇒* uTX1(|u|a (mod 2) ≡ 1)

如果1(P) = 1为P，否则为0。将其与S作品放在一起，我们有：

S ⇒ bTc ⇒* buTX1(|u|a (mod 2) ≡ 1)c ⇒ buTc ⇒ bu
S ⇒ aTXc ⇒* auTX1(|u|a (mod 2) ≡ 1)Xc ⇒ auTXc ⇒ aua

如果|u|a (mod 2) ≡ 0和

S ⇒ bTc ⇒* buTX1(|u|a (mod 2) ≡ 1)c ⇒ buTXc ⇒ bua
S ⇒ aTXc ⇒* auTX1(|u|a (mod 2) ≡ 1)Xc ⇒ auTXXc ⇒ auTc ⇒ au

如果|u|a (mod 2) ≡ 1，其中u的格式为(a|b)+。在上述派生的最后一步中，应用更多的T产生式不会生成具有不同形式的字符串。因此，我相信所有可派生的字符串都具有(a|b)+的形式。我担心的是，您被指示使用|u|a表示法来描述语法的语言，因此这种信念可能是错误的。