大门| 1997年CS大门|问题55

考虑语法

S→ bSe
S→ PQR
P→ bPc
P→ ε
Q→ cQd
Q→ ε
R→ dRe
R→ ε

其中S、P、Q、R是非终端符号，S是起始符号； b、 c，d，e 是终端符号，“ε”是空字符串。该语法生成形式为b的字符串 ^我 C ^J D ^K E ^M 对一些人来说，我，j，k，m≥ 0

• （a） 。 价值观的条件是什么 i、 j，k，m ?
• （b） 。 找到有两个解析树的最小字符串。

答复: 说明： （a） 。 关于i，j，k，m值的条件

i+k = j+m 

其中i，j，k，m>=0

（b） 。 具有两个解析树的最小字符串=bcde 用于生成最小字符串的产品是：-

S- > bSe
S- > bSe
S- > bSe
S -> PQR
P-> null
Q ->cQd
Q -> null
R- > null 

最后你会得到像“bbbcdeee”这样的字符串 这意味着i=3，j=1，k=1，m=3，因此答案是i+k=j+m。

现在，用于生成最小字符串的产品是：-

S-> bSe 
S ->  bPQRe
S ->  bεQRe
S ->  bcQdRe
S ->  bcεdRe
S ->  bcdεe
S -> bcde 

因此最小的字符串是bcde。 因此，我们可以看到相同数量的b，c，d，e被生成。 b，c，d，e的幂分别为i，j，k，m。 因此，i，j，k，m之间的关系是：-

i+k = j+m   

这个问题的小测验