13.6 Applications in Natural Language

13.6.1 Using Definite Clauses for Context-Free Grammars

This section shows how to use definite clauses to represent aspects of the syntax and semantics of natural language.

Languages are defined by their legal sentences. Sentences are sequences of symbols. Here we assume that a sentence is represented as a list of atoms, where there is an atom for each word in the language. More sophisticated models often represent words in terms of their parts, for example removing the ending such as “ing” and “er”.

The legal sentences are specified by a grammar.

Our first approximation of natural language is a context-free grammar. A context-free grammar is a set of rewrite rules, with non-terminal symbols transforming into a sequence of terminal and non-terminal symbols. A sentence of the language is a sequence of terminal symbols generated by such rewriting rules. For example, the grammar rule


means that a non-terminal symbol sentence can be a noun_phrase followed by a verb_phrase. The symbol “” means “can be rewritten as.”

For natural languages, the terminal symbols are typically the words of the language. If a sentence of natural language is represented as a list of words, the following definite clause means that a list of words is a sentence if it is a noun phrase followed by a verb phrase:


To say that the word “computer” is a noun, you could write


There is an alternative, simpler representation of context-free grammar rules using definite clauses that does not require an explicit append, known as a definite clause grammar (DCG). Each non-terminal symbol s becomes a predicate with two arguments, s(L1,L2), which is true when list L2 is an ending of list L1 such that all of the words in L1 before L2 form a sequence of words of the category s. Lists L1 and L2 together form a difference list of words that make the class given by the non-terminal symbol, because it is the difference of these that forms the syntactic category.

Example 13.34.

Under this representation, noun_phrase(L1,L2) is true if list L2 is an ending of list L1 such that all of the words in L1 before L2 form a noun phrase. L2 is the rest of the sentence. You can think of L2 as representing a position in a list after position L1. The difference list represents the words between these positions.

The atomic symbol


is true in the intended interpretation because “the student” forms a noun phrase.

The grammar rule


means that there is a sentence between some L0 and L2 if there exists a noun phrase between L0 and L1 and a verb phrase between L1 and L2:

L0         noun_phraseL1         verb_phrasesentenceL2

This grammar rule can be specified as the clause:


In general, the rule


says that h is composed of a b1 followed by a b2, …, followed by a bn, and is written as the definite clause


using the interpretation

L0    b1L1    b2L2Ln-1    bnhLn

where the Li are new variables.

To say that non-terminal h gets mapped to the terminal symbols, t1,,tn, one would write


using the interpretation


Thus, h(L1,L2) is true if L1=[t1,,tnL2].

Example 13.35.

The rule that specifies that the non-terminal h can be rewritten to the non-terminal a followed by the non-terminal b followed by the terminal symbols c and d, followed by the non-terminal symbol e followed by the terminal symbol f and the non-terminal symbol g, can be written as


and can be represented as


Note that the translations L2=[c,dL3] and L4=[fL5] were done manually.

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


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


% Adjectives consist of a (possibly empty) sequence of adjectives.


% An optional prepositional phrase is either nothing or a preposition followed by a noun phrase.


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

Figure 13.7: A context-free grammar for a restricted subset of English
Figure 13.8: A simple dictionary

Figure 13.7 axiomatizes a simple grammar of English. Figure 13.8 gives a simple dictionary of words and their parts of speech, which can be used with this grammar.

Example 13.36.

Consider the sentence “The student passed the course with a computer.” This is represented as a list of atoms, one for each word.

For the grammar of Figure 13.7 and the dictionary of Figure 13.8, the query

𝘢𝘴𝘬 noun_phrase([the,student,passed,the,course,with,a,computer],R).

will return


For the query,

𝘢𝘴𝘬 sentence([the,student,passed,the,course,with,a,computer],[]).

the computer first proves noun_phrase, which has a unique answer, as above. It then tries to prove verb_phrase.

This sentence has two different parses, one using the clause instance


and one using the instance


In the first of these, the prepositional phrase modifies the noun phrase (i.e., the course is with a computer); and in the second, the prepositional phrase modifies the verb phrase (i.e., the course was passed with a computer).