How we could create a context-free grammar that generates sentences of arbitrary length like: the cat died. the cat the dog chased died. the cat the dog the rat bit chased died. the cat the dog the rat the elephant admired bit chased died. this is what I think but not sure s-NP VP NP- det Nom Nom- N VP- V Det- the N- cat, dog,rat, elephant v- died, admired, bit, chased is that correct?

  • Do you care if it also generates sentences like the the the died cat dog?
    – user6726
    Apr 5, 2016 at 2:10
  • yes, it should exactly generate sentences like above, the+noun.
    – liza
    Apr 5, 2016 at 2:51

2 Answers 2


No, you need additional rules. Here are your rules (I rewrote them so I could read them):

S -> NP VP
NP -> Det Nom
Nom -> N
VP -> V
Det -> the
N -> cat, dog, rat, elephant
V -> died, admired, bit, chased

And below, I've started to make a tree for "the cat the dog chased died", but your rules give me no way to get "the dog chased" into its place as a modifier of "cat".

[S NP [VP V]]
[S NP [VP [V died]]]
[S [NP Det Nom] [VP [V died]]]
[S [NP [Det the] Nom] [VP [V died]]]
[S [NP [Det the] [Nom N]] [VP [V died]]]
[S [NP [Det the] [Nom [N cat]]] [VP [V died]]]
[S [NP [Det the] [Nom [N cat] ?? the dog chased ?? ]] [VP [V died]]]
  • Would you please draw a tree for the sentence like the cat the dog the rat the elephant admired bit chased died? I got confused. Thanks alot.
    – liza
    Apr 6, 2016 at 18:11
  • No, @liza, I'm leaving the rest of the problem for you. It will be fun. I think you can do it with just one additional rule.
    – Greg Lee
    Apr 6, 2016 at 18:35
  • I'm not convinced the relationship between the rules and the tree is clear to you. You have to use the rules to build the tree. How does the S "the dog chased" in this example get into the tree? You need to add a new rule to the rules you already have to get it into the tree.
    – Greg Lee
    Apr 6, 2016 at 19:58
  • I got it, thank you. But I have another question. I read somewhere that we creating center-embedded sentences could occur until the level 3 like the cat the dog the rat bit chased died. is that correct? why?
    – liza
    Apr 6, 2016 at 21:24
  • I don't know that there is a precise cut off at 3, but center embedded constructions do become much more difficult to understand as the level increases. It is not known why. Analogies to computer programming suggest that once a constituent has been completely analyzed, the processing resources it used during the analysis is freed up and available for other uses. But before the analysis is complete, resources are still tied up, and this can interfere with the processing of a new instance of the construction.
    – Greg Lee
    Apr 6, 2016 at 21:49

Altho' it looks like a homework question, here are some useful rules:

S ->  ε
S -> NP S VP
NP -> Det N
VP -> V
Det -> the
N -> cat
N -> dog
V -> chased
V -> died

Add more rules for other terminals (bit, admired, rat, elephant, ...). I didn't care for generating initial capitalisation or interpunctuation (you can add this if you care).

  • I don't think that we need the first line(S -> ε). is it possible to write parse tree for center-embedded sentences? should we rewrite these sentences with "that"?
    – liza
    Apr 6, 2016 at 17:19
  • The first rule says that S may be empty -- nothing there. Look at the second rule and try to match up the parts of the rule with the example "the cat died". In S -> NP S VP, the first S is for the whole example "the cat died", the NP is for "the cat", there is nothing for the following S, and VP is for "died". The first rule says it is okay for nothing to correspond to the S. (I wouldn't do it this way.)
    – Greg Lee
    Apr 6, 2016 at 20:09
  • Somehow the sentence generation must terminate. But is is probably better to have the rule S -> NP VP. This excludes the empty sentence from the "language" (in computer science sense). Apr 7, 2016 at 10:03

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.