Пролог: Распознать язык ^ n b ^ (n + 1) для n> = 1 - PullRequest
Новая
       33

Пролог: Распознать язык ^ n b ^ (n + 1) для n> = 1

3 голосов
/ 22 февраля 2010

Я понимаю, что мне нужно выяснить свою домашнюю работу, но, видя, что никто в классе не может понять это, мне нужна помощь.

Напишите программу на Прологе так, чтобы p(X) Значение true, если X является списком, состоящим из n За a следует n+1 b, для любого n >= 1.

Ответы [ 3 ]

2 голосов
/ 22 февраля 2010

Я не помню, как это кодировать в Прологе, но идея такова:

Правило 1: Если listsize равен 1, вернуть true, если элемент представляет собой B.

Правило 2: Если для listize задано значение 2, верните false.

Правило 3: Проверьте, является ли первый элемент в списке буквой A, а последний - буквой B. Если это так, верните решение для элементов 2 для listsize-1.

Если я правильно понял вашу проблему, это должно быть идеальным решением в стиле Пролог.

Редактировать: Я полностью забыл об этом. Я отредактировал ответ, чтобы рассмотреть случай n = 1 и n = 2. Спасибо Хиту Ханникутту.

1 голос
/ 25 февраля 2010

Вот мое заумное решение 

:-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]).

Тестирование: 

 ?- [ab].
% ab compiled 0.00 sec, -36 bytes
true.

 ?- test.
true.
1 голос
/ 22 февраля 2010

Вы должны использовать счетчик, чтобы отслеживать то, что вы нашли до сих пор. Когда вы найдете b, добавьте его к прилавку. Когда вы найдете a, вычтите один. Конечное значение вашего счетчика после прохождения всего списка должно быть равно единице, поскольку вы хотите, чтобы число b было на 1 больше, чем число a. Вот пример того, как написать это в коде: 

% 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).

Теперь, это будет делать почти , что вы хотите - это соответствует правилам для всех n >= 0, тогда как вы хотите это для всех n >= 1. В типичной форме ответа на домашнее задание я оставил вам последнее слово, чтобы вы добавили себя.

...