### 7.3 Exercises

Exercise  7.1 Suppose we are working with the following DCG:

s  -->  foo,bar,wiggle.
foo  -->  [choo].
foo  -->  foo,foo.
bar  -->  mar,zar.
mar  -->  me,my.
me  -->  [i].
my  -->  [am].
zar  -->  blar,car.
blar  -->  [a].
car  -->  [train].
wiggle  -->  [toot].
wiggle  -->  wiggle,wiggle.

Write down the ordinary Prolog rules that correspond to these DCG rules. What are the first three responses that Prolog gives to the query s(X,[]) ?

Exercise  7.2 The formal language a n b n −{ ϵ } consists of all the strings in a n b n except the empty string. Write a DCG that generates this language.

Exercise  7.3 Let a n b 2 n be the formal language which contains all strings of the following form: an unbroken block of a s of length n followed by an unbroken block of b s of length 2n , and nothing else. For example, abb , aabbbb , and aaabbbbbb belong to a n b 2 n , and so does the empty string. Write a DCG that generates this language.

© 2006-2012 Patrick Blackburn, Johan Bos, Kristina Striegnitz