奈寻味导航网 » 文章资讯 » 使用 CFG 时使用 LMD 和 RMD 导出字符串“00101”

使用 CFG 时使用 LMD 和 RMD 导出字符串“00101”

2023-06-07 16:44:03 527

问题

使用上下文无关文法(CFG)为最左派生(LMD)和最右派生(RMD)派生字符串“00101”。

语法如下-

S->A1B
A->0A| ε
B->0B| 1B| ε

在最左边的推导中，给定的输入被扫描，然后从左到右替换为产生式规则。所以，我们必须从左到右读取输入字符串。

语法如下-

S->A1B rule1
A->0A| ε rule 2
B->0B| 1B| ε rule 3

因此，LMD将如下-

S->A1B
->0A1B rule2
->00A1B rule2
->001B rule2
->0010B rule3
->00101B rule3
->00101 rule3
Derived the string 00101 using LMD

在最右推导中，给定的输入被扫描，然后用从右到左的产生式规则替换。因此，我们必须从右到左读取输入字符串。

语法如下-

S->A1B rule1
A->0A| ε rule 2
B->0B| 1B| ε rule 3

现在，RMD将如下-

S->A1B
->A10B rule3
->A101B rule3
->A101 rule3
->0A101 rule2
->00A101 rule2
->00101 rule2
Derived the string 00101 using RMD