Learn Prolog Now! DCG Practice Example

Posted by Timothy on Stack Overflow See other posts from Stack Overflow or by Timothy
Published on 2010-06-08T01:28:29Z Indexed on 2010/06/08 1:32 UTC
Read the original article Hit count: 218

Filed under:
|

I have been progressing through Learn Prolog Now! as self-study and am now learning about Definite Clause Grammars. I am having some difficulty with one of the Practical Session's tasks. The task reads:

The formal language anb2mc2mdn consists of all strings of the following form: an unbroken block of as followed by an unbroken block of bs followed by an unbroken block of cs followed by an unbroken block of ds, such that the a and d blocks are exactly the same length, and the c and d blocks are also exactly the same length and furthermore consist of an even number of cs and ds respectively. For example, ε, abbccd, and aaabbbbccccddd all belong to anb2mc2mdn. Write a DCG that generates this language.

I am able to write rules that generate andn, b2mc2m, and even anb2m and c2mndn... but I can't seem to join all these rules into anb2mc2mdn. The following are my rules that can generate andn and b2mc2m.

s1 --> [].
s1 --> a,s1,d.
a --> [a].
d --> [d].

s2 --> [].
s2 --> c,c,s2,d,d.
c --> [c].
d --> [d].

Is anb2mc2mdn really a CFG, and is it possible to write a DCG using only what was taught in the lesson (no additional arguments or code, etc)? If so, can anyone offer me some guidance how I can join these so that I can solve the given task?

© Stack Overflow or respective owner

Related posts about learning

Related posts about prolog