我找不到以下问题的答案。自动机接受诸如“A:5739”之类的字符串。或“C::399\4342)”,这些让我想起了文件系统的路径,但我对此不确定。
问题文本:
Consider the following finite-state automaton written in Prolog. What seems to recognize?
Assume having the predicate
alphanumeric/1
which is true when its argument is a letter or digit.
Automaton:
accept([I | Is], S) :- delta(S, I, N), accept(Is, N). accept([], Q) :- final(Q). initial(start). final(type). delta(start, 'A', dev). delta(start, 'B', dev). delta(start, 'C', dev). ... delta(start, 'Z', dev). delta(dev, ':', n1). delta(n1, '\', dev). delta(n1, L, name) :- alphanumeric(L). delta(name, L, name) :- alphanumeric(L). delta(name, '\', name). delta(name, '.', type). delta(name, L, type) :- alphanumeric(L).
最佳答案
前两个子句就是 NDFA 始终执行的方式:每次我们查找列表中的下一个字符,并将其通过 delta/3 谓词传递以获得新状态,直到我们到达了序列的末尾,之后我们可以验证状态是否是接受状态。
接下来我们看到 start
是初始状态,而 type
是唯一的接受状态。
程序的其余部分描述了 delta/3
转换。我们可以对此进行可视化,例如使用GraphViz:
digraph finite_state_machine {
rankdir=LR;
size="8,5"
node [shape = doublecircle]; type;
node [shape = circle] start, dev, n1;
node [shape = circle, label="name"] nam;
start -> dev [ label = "[A-Z]" ];
dev -> n1 [ label = ":" ];
n1 -> dev [ label = "\\" ];
n1 -> nam [ label = "[A-Za-z0-9]" ];
nam -> nam [ label = "[A-Za-z0-9\\]" ];
nam -> type [ label = "[A-Za-z0-9.]" ];
}
这会产生以下图像:
根据此图,我们看到它接受语言(正则表达式表示法):
[A-Z]:(\:)*[A-Za-z0-9][A-Za-z0-9\]*[A-Za-z0-9.]
因此它接受以字符 A-Z 开头、后跟冒号 (:
) 、零个或多个反斜杠冒号 (:\
) 和字母数字字符,后跟词组 [A-Za-z0-9\.]
中的零个或多个字符,后跟至少一个字母数字字符。
例如:
X:\:0Azz0qdqd012QcCQCA
D:\:QA
B:\:\:QT
C:QWR.
C:\:a\q\b\QWR.
C:tempdir\bla\qux.
C:tempdir\bla\.
C:.
它只能包含一个点作为最后一个字符。此外,反斜杠不能是最后一个字符。它是一种基本的文件路径语言,尽管有一些限制。
关于PROLOG 一个特定的有限状态自动机,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47183788/