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

问题

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

解决方案

语法如下 -

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

最左推导 (LMD)

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

语法如下 -

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

最右推导 (RMD)

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

语法如下 -

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