Self-test 2

Finding alternatives in the search tree

You are advised to complete your solutions before you look at the answers.

The following is a partial grammar for describing part of a sentence in English:

     sent :-
          noun_phrase,
          verb.

     noun_phrase :-
          noun.
     noun_phrase :-
          adjective, 
          noun.

     verb :-
          hurt.

     noun :-
          bruises.

     adjective :-
          big.

     big.
     bruises.
     hurt.

The search tree covers two possible sentences: "bruises hurt" and "big bruises hurt". Looking at the following search tree:

Which would be the first node to be "undone" and retried after finding the first successful solution using depth-first search.
Calculate how many nodes there will be in the complete search tree.

Solutions

Navigation Menu