线性文法，推导出一个词

Question

假设给定一个右线性文法，你将如何展示派生一个词的步骤？例如，如果我有语法：

S -> aA
A -> bA
A -> aB
B -> cB
B -> a

我想构造 abbbacca 这个词。我将如何显示我的步骤派生？会不会是：

S => A => A => A => A => B => B => B

或更类似于：

aA => abA => abbA => abbbA => abbbaB => abbbacB => abbbaccB => abbbacca

Answer 1

正在将评论转换为答案以便问题可以从未回答的列表中消失...

表格

S => aA => abA => abbA => abbbA => abbbaB => abbbacB => abbbaccB => abbbacca

是更常用、更可取的推导方式。对于额外的学分，尤其是对于较大的语法，显示在推导箭头上应用的规则的标签可能也很有用，例如

S =(1)=> aA

当然，要使它真正有用，规则必须有标签！

Linear grammar, derive a word