How to recursively infer a word/string from a context-free grammar?

Question

Give the recursive inference of the word $abcddd$ from the Context-free Grammar:

$A\rightarrow aAd\mid B$
$B\rightarrow bBd\mid C$
$C\rightarrow cC\mid cD$
$D\rightarrow Dd\mid ϵ$

This is a follow up question to this one here. Much like that question I haven't found any good information on the subject. I understand the inductive proof of an inferred word belonging to a language, but I don't know how to put it to practical use. I have found an example in our course literature, "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Motwani and Ullman, but they only have a filled out table of the inference of several words without any detailed explanation on how they got there.

I tried to mimic that table for this excersice and think I have solved it, but I don't understand what I'm doing or if I'm even doing it right. What I need is someone to explain the thinking behind this algorithm or whatever it is they are using. Here is the table I have created for the word $abcddd$:

$$ \begin{array}{ r | c | c | c | c } & \textit{String Inferred} & \textit{For language of} & \textit{Production used} & \textit{String(s) used} \\ \hline (i) & ϵ & D & D \rightarrow ϵ & - \\ (ii) & d & D & D \rightarrow Dd & (i) \\ (iii) & cd & C & C \rightarrow cD & (ii) \\ (iv) & cd & B & B \rightarrow C & (iii) \\ (v) & bcdd & B & B \rightarrow bBd & (iv) \\ (vi) & bcdd & A & A \rightarrow B & (v) \\ (vii) & abcddd & A & A \rightarrow aAd & (vi) \\ \hline \end{array} $$

To me this is just like deriving words, but backwards, if you know what I mean? So, I am doing this correctly? Why am I doing this, instead of just deriving words "as usual"?

Answer 1

You are correct to realize that this is just like deriving words, but backwards. The authors admit this when they say "However, it is often more natural to think of grammars as used in derivations, . . ."

Labeling the productions as $A\rightarrow aAd$ (1), $A\rightarrow B$ (2), $B\rightarrow bBd$ (3), $B\rightarrow C$ (4)m $C\rightarrow cC$ (5), $C\rightarrow cD$ (6), $D\rightarrow Dd$ (6), and $D\rightarrow\epsilon$ (8) we can produce this derivation $$ A\stackrel{(1)}{\Longrightarrow}aAd\stackrel{(2)}{\Longrightarrow}aBd\stackrel{(3)}{\Longrightarrow}abBdd\stackrel{(4)}{\Longrightarrow}abCdd\stackrel{(6)}{\Longrightarrow}abcDdd\stackrel{(7)}{\Longrightarrow}abcDddd\stackrel{(8)}{\Longrightarrow}abcddd $$ and reading this from right to left gives exactly the table you had.

Frankly, it's not a topic I cover when I'm teaching this material.