使用 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