线性语法，派生一个词

Question

假设给出了右线性语法，您将如何显示派生单词的步骤？例如，如果我有语法：

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

我想构建abacca这个词。我如何展示我的步骤衍生？可不可能是：

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

当然，为了真正有用，规则必须有标签！