Prolog: Recognize a^n b^(n+1) language for n >= 1
문제
I understand that I need to figure out my own homework, but seeing that noone in the class can figure it out, I need some help.
Write a Prolog program such that
p(X)
is true ifX
is a list consisting ofn
a
's followed byn+1
b
's, for anyn >= 1
.
해결책
You should use a counter to keep track of what you have found so far. When you find an b
, add one to the counter. When you find a a
, subtract one. The final value of your counter after the whole list is traversed should be one, since you want the number of b
's to be 1 more than the number of a
's. Here's an example of how to write that in code:
% When we see an "a" at the head of a list, we decrement the counter.
validList([a|Tail], Counter) :-
NewCounter is Counter - 1,
validList(Tail, NewCounter).
% When we see an "b" at the head of a list, we increment the counter.
validList([b|Tail], Counter) :-
NewCounter is Counter + 1,
validList(Tail, NewCounter).
% When we have been through the whole list, the counter should be 1.
validList([], 1).
% Shortcut for calling the function with a single parameter.
p(X) :-
validList(X, 0).
Now, this will do almost what you want - it matches the rules for all n >= 0
, while you want it for all n >= 1
. In typical homework answer fashion, I've left that last bit for you to add yourself.
다른 팁
I don't remember how to code this in Prolog, but the idea is this:
Rule 1: If listsize is 1, return true if the element is a B.
Rule 2: If listsize is 2, return false.
Rule 3: Check if the first item in the list is an A and the last one is a B. If this is true, return the solution for elements 2 to listsize-1.
If I understood your problem correctly that should be the perfect Prolog style solution.
Edit: I totally forgot about this. I edited the answer to consider the case of n = 1 and n = 2. Thanks to Heath Hunnicutt.
Here is my abstruse solution
:-use_module(library(clpfd)).
n(L, N) -->
[L],
{N1 #= N-1
},
!, n(L, N1).
n(_, 0) --> [], !.
ab -->
n(a, N),
{N1 is N + 1
},
n(b, N1).
p(X) :- phrase(ab, X).
test :-
p([b]),
p([a,b,b]),
p([a,a,b,b,b]),
p([a,a,a,b,b,b,b]),
\+ p([a]),
\+ p([a,b]),
\+ p([a,a,b,b]),
\+ p([a,b,b,c]).
testing:
?- [ab].
% ab compiled 0.00 sec, -36 bytes
true.
?- test.
true.