13.6 Applications in Natural Language

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

13.6.5 Enforcing Constraints

Natural language imposes constraints which, for example, disallow sentences such as “A students eat.” Words in a sentence must satisfy some agreement criteria. “A students eat.” fails to satisfy the criterion of number agreement, which specifies whether the nouns and verbs are singular or plural.

Number agreement can be enforced in the grammar by parametrizing the non-terminals by the number and making sure that the numbers of the different parts of speech agree. You only need to add an extra argument to the relevant non-terminals.

% A sentence is a noun phrase followed by a verb phrase.

sentence(L0,L2,Num,s(NP,VP))
    noun_phrase(L0,L1,Num,NP)
    verb_phrase(L1,L2,Num,VP).

% A noun phrase is empty or a determiner followed by adjectives followed by a noun followed by an optional prepositional phrase.

noun_phrase(L,L,Num,nonp).
noun_phrase(L0,L4,Num,np(Det,Mods,Noun,PP))
    det(L0,L1,Num,Det)
    adjectives(L1,L2,Mods)
    noun(L2,L3,Num,Noun)
    pp(L3,L4,PP).

% A verb phrase is a verb, followed by a noun phrase, followed by an optional prepositional phrase.

verb_phrase(L0,L3,Num,vp(V,NP,PP))
    verb(L0,L1,Num,V)
    noun_phrase(L1,L2,N2,NP)
    pp(L2,L3,PP).

% An optional prepositional phrase is either nothing or a preposition followed by a noun phrase. Only the null case is given here.

pp(L,L,nopp).

% Adjectives is a sequence of adjectives. Only the null case is given here.

adjectives(L,L,[]).

% The dictionary.

det([aL],L,singular,indefinite).
det([theL],L,Num,definite).
noun([studentL],L,singular,student).
noun([studentsL],L,plural,student).
verb([eatsL],L,singular,eat).
verb([eatL],L,plural,eat).
Figure 13.10: Grammar to enforce number agreement and build a parse tree
Example 13.38.

The grammar of Figure 13.10 does not allow “a students,” “the student eat,” or “the students eats,” because all have number disagreement, but it allows “a green student eats,” “the students,” or “the student,” because “the” can be either singular or plural.

To parse the sentence “the student eats,” you issue the query

𝘢𝘴𝘬 sentence([the,student,eats],[],Num,T)

and the answer returned is

Num=singular,
T=s(np(definite,[],student,nopp),vp(eat,nonp,nopp)).

To parse the sentence “the students eat,” you issue the query

𝘢𝘴𝘬 sentence([the,students,eat],[],Num,T)

and the answer returned is

Num=plural,
T=s(np(definite,[],student,nopp),vp(eat,nonp,nopp)).

To parse the sentence “a student eats,” you issue the query

𝘢𝘴𝘬 sentence([a,student,eats],[],Num,T)

and the answer returned is

Num=singular,
T=s(np(indefinite,[],student,nopp),vp(eat,nonp,nopp)).

Note that the only difference between the answers is whether the subject is singular and whether the determiner is definite.