Search code examples
grammarregular-language

Linear grammar, derive a word

Assuming a right-linear grammar is given how would you show the steps to derive a word? For example if I had the grammer:

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

And I wanted to constuct the word abbbacca. How would I show my step derivertation? Would it be:

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

or somethiong more akin to:

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

  • Converting comments to an answer so the question can disappear from the unanswered lists ...

    The form 

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

    is the more usual, and preferable, way to show the derivation. For extra credit, especially so with larger grammars, it may also be useful to show the label of the rule applied on the derivation arrow, something like

    S =(1)=> aA

    Of course, for this to be really useful the rules have to have labels !