主页 / 问题 / 1273058
Accepted
user435351
Asked:2022-04-21 23:06:53 +0800 CST2022-04-21 23:06:53 +0800 CST

自动机的序幕

  • 772

如何在prolog中找到一个接受非确定性有限自动机的长度为k的单词（如果有很多，一个就足够了）？我这样写机器：

states([q0, q1, q2]).
symbols([a, b]).
transition(q0, a, q1).
transition(q0, b, q2).
transition(q1, a, q2).
transition(q1, b, q0).
transition(q2, a, q1).
transition(q2, b, q2).
startState(q0).
finalStates([q2]).
prolog

1 个回答

  1. Best Answer

    在您的符号中，解决方案是：

    states([q0, q1, q2]).
symbols([a, b]).
transition(q0, a, q1).
transition(q0, b, q2).
transition(q1, a, q2).
transition(q1, b, q0).
transition(q2, a, q1).
transition(q2, b, q2).
startState(q0).
finalStates([q2]).

search(0, S, []) :-
    finalStates(FinalStates),
    member(S, FinalStates).
search(N, S1, [Head|Tail]) :-
    N > 0,
    transition(S1, Head, S2),
    M is N - 1,
    search(M, S2, Tail).

test(N, Transitions) :-
    startState(S),
    search(N, S, Transitions).

    $ swipl -s automata.pl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.2.3)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- test(4, X).
X = [a, a, a, a] ;
X = [a, a, b, b] ;
X = [a, b, a, a] ;
X = [a, b, b, b] ;
X = [b, a, a, b] ;
X = [b, a, b, b] ;
X = [b, b, a, a] ;
X = [b, b, b, b] ;
false.
    • 0

相关问题