CODEWITHSUNDEEP
prologdcg
izash
izash

Reputation: 61

Define a DCG in Prolog for bit strings practice problem

Before our Prolog final exam soon, I got some practice questions and I am stuck on one:

For each integer n > 0, let Ln := {s ∈ {0, 1}+ | s ends in a string from 1(0 + 1)n−1} be the set of bit-strings whose n-th to the last bit is 1. That is, Ln is described by the regular expression (0 + 1)∗1(0 + 1)n−1.

Define a DCG for the 3-ary predicate s/3 such that s(n,s,[]) is true exactly if s encodes a string in Ln.

I tried for a while to get this, but I am unsure what to do, does anyone have a solution?

Upvotes: 1

Views: 222

Answers (2)

TA_intern
TA_intern

Reputation: 2436

Let's try to make it look like the regular expression you showed, just for funzies. I will not define operators and instead "parse" the regex to something that Prolog can read without new operator definitions (I am not even sure if you can make it work just with redefining operators, maybe it isn't possible). So I will define a +//2 for "or" and *//1 for "0 or more repetitions" and n//2 for "n repetitions".

+(A, B) --> [A] | [B].
*(P) --> [] | call(P), *(P).
n(P, N) --> { length(L, N) }, n_1(L, P).
n_1([], _) --> [].
n_1([_|L], P) --> call(P), n_1(L, P).

With those available I can write a query that roughly resembles your problem statement:

?- length(L, _), phrase(( *(+(0,1)), [1], n(+(0,1), 1) ), L).
L = [1, 0] ;
L = [1, 1] ;
L = [0, 1, 0] ;
L = [0, 1, 1] ;
L = [1, 1, 0] ;
L = [1, 1, 1] ;
L = [0, 0, 1, 0] ;
L = [0, 0, 1, 1] ;
L = [0, 1, 1, 0] . % it goes on

Note that here I set the n to be equal to 2, so in n//2 I am using 2 - 1 = 1.

EDIT: I noticed that the *//1 I defined is just a special case of n//2. So you can actually do this:

?- phrase(n(+(0,1), N), L).
N = 0,
L = [] ;
N = 1,
L = [0] ;
N = 1,
L = [1] ;
N = 2,
L = [0, 0] ;
N = 2,
L = [0, 1] ;
N = 2,
L = [1, 0] ;
N = 2,
L = [1, 1] ;
N = 3,
L = [0, 0, 0] .

In other words, you can leave the N argument a free variable and you will get strings of increasing length, with the length in N.

Upvotes: 2

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

Here's a DCG for (0 + 1)*:

zero_or_one -->
    [0].
zero_or_one -->
    [1].

many_zero_or_one -->
    [].
many_zero_or_one -->
    zero_or_one,
    many_zero_or_one.

Upvotes: 2

Related Questions