Symbolic AI

(1995 ACS Problem F)

A solution for this problem can be found here.

You have been given the job of writing a simple symbolic AI processor, which will be told some facts, and asked some questions. The AI processor must then try its hardest to answer the questions.

Fortunately, these facts and questions relate only to specific individuals, who are in groups (collective nouns) which perform actions (verbs) on other groups.

The grammar used is very simple: there are two types of statements and one type of question, and all nouns are made plural through the expedient of adding an s.

INPUT

Each line of the input contains either a simgle sentence or a blank. The end of the input is indicated by a line whose first character is a #. Each sentence has one of the following forms:

  • A statement of the form "as v bs.",where a and b are nouns and v is a verb. This means that everything of type a does v to everything of type b.
  • A statement of the form "a is a b.", where a and b are nouns. This means that the particular individual a is of type b.
  • A question of the form "Does a v b?", where a and b are nouns and v is a verb. This asks whether the individual a does the action v to the individual b.
    • Lines are up to 80 characters long. Words are up to 40 characters long and may consist of upper and lower case letters, although all searching is done case-insensitively. There may be more than one space between words, but there are never any spaces between words and the punctuation marks at the end of each sentence. Allow for up to 100 facts in the input.

    OUTPUT

    For each question in the input, print a single line contains 
    Yes.
    if the preceding input implies that the question is true, and 
    No.
    otherwise.
    SAMPLE INPUT
    Dogs chase cats.
Sheeps ignore glasss.
Fido is a dog.
Fluffles is a cat.
Does Fido chase Fluffles?
Does Fluffles chase Fido?
#

    SAMPLE OUTPUT
    Yes.
No.

    This problem was Problem F in the 1995 ACS Australian Programming Competition.