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"?


1 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.

  • $\begingroup$ A good answer yet again! Thank you @Rick! Yeah, our lecturer didn't really cover it either. I think the words "recursive inference" is mentioned like once or twice in her material and yet she expects us to do exercises on it. $\endgroup$
    – Skillzore
    May 16, 2016 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.