Sentences can be generated from a grammar by the following procedure:

• Start with the sentence symbol, < S> .

• Repeat until no nonterminal symbols remain:
  • Choose a nonterminal symbol in the current string.

  • Choose a production that begins with that nonterminal.

  • Replace the nonterminal by the right-hand side of the production.

< s> 
< np>  < vp> 
< art>  < noun>  < vp> 
the < noun>  < vp> 
the dog < vp> 
the dog < verb>  < np> 
the dog < verb>  < art>  < noun> 
the dog < verb>  the < noun> 
the dog bit the < noun> 
the dog bit the boy

Contents    Page-10    Prev    Next    Page+10    Index