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^nb^n - \{\epsilon\}$ consists of all the strings in except the empty string. Write a DCG that generates this language.

Exercise 7.3

Let $a^nb^{2n}$ be the formal language which contains all strings of the following form: an unbroken block of as of length n followed by an unbroken block of bs of length 2n, and nothing else. For example, abb, aabbbb, and aaabbbbbb belong to $a^nb^{2n}$ , and so does the empty string. Write a DCG that generates this language.