Узнать пролог сейчас! Пример практики DCG

Я прохожу через Learn Prolog Now! как самостоятельное изучение, и теперь я узнаю об определенных граммамах. У меня возникают трудности с одной из задач Практической сессии. The task гласит:Узнать пролог сейчас! Пример практики DCG

Формального язык по ^п б ^2m с ^2m д ^п состоит из всех строк следующего вида: непрерывная блок через с последующей ненарушенным блоком из б с последующим ненарушенным блоком с с последующим ненарушенным блоком д с, например, что и д блоки точно такой же длины, и с и д блоки также точно такой же длины и, кроме того, состоит из четного числа с с и д с соответственно. Например, & epsilon;, abbccd и aaabbbbccccddd все принадлежат к ^п б ^2m гр ^2m д ^п. Напишите DCG, который генерирует этот язык.

Я могу написать правила, которые генерируют ^п д ^п, б ^2m гр ^2m, и даже ^п б ^2m и с ^2m г ^н ... но я не могу показаться, чтобы объединить все эти правила в ^п б ^ого с ^ого д ^п. Ниже приведены мои правила, которые могут генерировать ⁿ d ⁿ и b ^2m c ^2m.

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

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

Является ^п б ^2м с ^2м d ^п действительно CFG, и можно написать DCG не используя только то, что учили на уроке (никаких дополнительных аргументов или код , и т.д)? Если да, может ли кто-нибудь предложить мне некоторое руководство, как я могу присоединиться к ним, чтобы я мог решить данную задачу?

источник

2010-06-08 Timothy

@Timothy, ваш ответ работает, но он создает дубликаты:

?- length(S,_), s(S,[]). 
S = [] ; 
S = [a, d] ; 
S = [a, d] ;   % XXX 
S = [b, b, c, c] ; 
S = [a, a, d, d] ; 
S = [a, a, d, d] ;  % XXX

Это может быть исправлено путем удаления одного пункта, оставив DCG:

s --> x. 
s --> a,s,d. 

x --> []. 
x --> b,b,x,c,c. 

% a, b, c, d the same

Это создает:

?- length(S,_), s(S,[]). 
S = [] ; 
S = [a, d] ; 
S = [b, b, c, c] ; 
S = [a, a, d, d] ; 
S = [a, b, b, c, c, d] ; 
S = [a, a, a, d, d, d] ; 
S = [b, b, b, b, c, c, c, c] ; 
S = [a, a, b, b, c, c, d, d] ; 
S = [a, a, a, a, d, d, d, d] ;

источник

2010-06-12 12:04:12

Как о чем-то вроде:

n(L,N) --> n(L,N,0). 

n(_,N,N) --> [], !. 
n(L,N,K) --> L, {K1 is K + 1}, n(L, N, K1). 

abbccd(N,M) --> 
    {M1 is 2*M}, 
    n("a",N), 
    n("b",M1), 
    n("c",M1), 
    n("d",N). 

gen :- 
    forall((
      between(1,4,N), 
     between(1,4,M), 
     phrase(abbccd(N,M),S), 
     string_to_atom(S,A) 
      ), 
      writeln(A)).

исполняющего:

?- gen. 
abbccd 
abbbbccccd 
abbbbbbccccccd 
abbbbbbbbccccccccd 
aabbccdd 
aabbbbccccdd 
aabbbbbbccccccdd 
aabbbbbbbbccccccccdd 
aaabbccddd 
aaabbbbccccddd 
aaabbbbbbccccccddd 
aaabbbbbbbbccccccccddd 
aaaabbccdddd 
aaaabbbbccccdddd 
aaaabbbbbbccccccdddd 
aaaabbbbbbbbccccccccdddd 
true.

источник

2010-06-08 13:53:32 Xonix

Спасибо, Xonix. Это работает, но, к сожалению, он использует концепции, которые не рассматриваются до конца (кодовые блоки, разрезы и т. Д.). Я честно считаю, что это невозможно, используя только простые правила ... или, если это так, это не стоит усилий, потому что в «реальном мире» можно использовать другие концепции, как в вашем примере. – Timothy

Я полагаю, что я понял это ...

s --> x. 
s --> a,d. 
s --> a,s,d. 

x --> []. 
x --> b,b,x,c,c. 

a --> [a]. 
b --> [b]. 
c --> [c]. 
d --> [d]. 

?- s([],[]). 
Yes 

?- s([a,b,c,c,d],[]). 
No 

?- s([a,a,a,b,b,c,c,d,d,d],[]). 
Yes

Забавно смотреть на решение и думать, «Я ломал себе голову над этого?» Но я думаю, что это половина удовольствия от изучения чего-то нового, особенно когда это что-то вроде логического программирования, исходящего из императивного программирования.

источник

2010-06-10 04:00:26 Timothy

Это тяжело, но окупается. Логическое программирование (и ленивое FP) знание esp. служил мне при изучении концепции итератора в C++, Java и Python. –

Узнать пролог сейчас! Пример практики DCG

ответ

Смежные вопросы