这是CFG:
S -> T | V
T -> UU
U -> aUb | ab
V -> aVb | aWb
W -> bWa | ba
所以这将接受某种形式的:
{a^n b^n a^m b^m | n,m >= 1} U {a^n b^m a^m b^n | n,m >= 1}
这是我正在使用的代码:
in_lang([]).
in_lang(L) :-
mapS(L), !.
mapS(L) :-
mapT(L) ; mapV(L),!.
mapT(L) :-
append(L1, mapU(L), L), mapU(L1), !.
mapU([a|T]) :-
((append(L1,[b],T), mapU(L1)) ; (T = b)),!.
mapV([a|T]) :-
((append(L1,[b],T), mapV(L1)) ;
(append(L1,[b],T), mapW(L1))),
!.
mapW([b|T]) :-
((append(L1,[a],T), mapW(L1)) ;
(T = a)),
!.
截至目前,这对以下三个字符串返回 false:
[a,a,b,b,a,b] // this should be true
[a,a,a,b,b,a,a,b,b,b] // this should be true as well
[a,a,a,b,b,a,b,b,b] // this one IS false
任何帮助或见解将不胜感激,我对 Prolog 不太满意,因此自己调试它一直是一个挑战。
最佳答案
只需使用 dcg !和 library(double_quotes)
.
:- set_prolog_flag(double_quotes, chars).
s --> t | v.
t --> u, u.
u --> "a",u,"b" | "ab".
v --> "a",v,"b" | "a",w,"b".
w --> "b",w,"a" | "ba".
| ?- use_module(library(double_quotes)).
| ?- length(L,N), phrase(s, L).
L = "abab", N = 4 ? ;
L = "abab", N = 4 ? ;
L = "aabbab", N = 6 ? ;
L = "abaabb", N = 6 ? ;
L = "aababb", N = 6 ? ;
L = "abbaab", N = 6 ? ;
L = "aaabbbab", N = 8 ? ;
L = "aabbaabb", N = 8 ? ;
L = "abaaabbb", N = 8 ? ;
L = "aaababbb", N = 8 ? ...
关于prolog - 检查字符串是否包含在语言中(Prolog),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36844815/