Page 160 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes 8.4.1 Phrase Structure Grammars and Automata

The representation of grammatical knowledge as phrase structure rules is common for syntactic
parsing in sentence comprehension and to some extent, the recognition of complex words. The
use of these rules is somewhat similar to production rules, but they operate on strings of
linguistic items. Phrase structure rules basically specify how an initial symbol can be recursively
expanded into a sequence of other symbols.

Example: The first rule in the rule set below specifies that a sentence (S) can be expanded
into a noun phrase (NP) followed by a verb phrase (VP), or, inversely, that a noun phrase and a
verb phrase can be reduced to a sentence.
The selection mechanism chooses among various applicable rules. Often, a symbol can be
expanded into different ways, for example in the following rule set describing how an NP can be
rewritten as either an article followed by a noun, or an article followed by an adjective, followed
by a noun.
S -> NP VP
NP -> PRONOUN
NP -> ART N
NP -> ART ADJ N
VP -> COPULA NP
PRONOUN -> she
COPULA -> is
ART -> the
ART -> a
ADJ -> nice
ADJ -> smart
N -> doctor
A deterministic system will choose only one rule, whereas a non-deterministic system may
search through a space of possibilities, using e.g. a parallel or backtracking search. When a rule
is chosen, the left hand side of the rule is replaced with the right hand side. Successive expansions
develop the structure until a solution is reached in the form of a sequence of words. The expansion
history of a particular case can be represented as a syntactic tree structure. Clearly, different
grammars give rise to different tree structures.

Figure 8.2: Syntactic Tree Structure

Phrase structure rules may operate in both directions, top-down, where the left hand sides of
rules are rewritten as their right hand sides, or bottom-up, where the right hand sides are
rewritten as the left hand sides. Depending on the form the left-hand side and the right-hand
side of the phrase structure rules can take, different types of grammars can be formally defined:
regular, context-free, context-sensitive, or unrestricted. Much research in CL is based on context-
free grammars.

154 LOVELY PROFESSIONAL UNIVERSITY