2

我找不到以下问题的答案。自动机接受诸如“A:5739”之类的字符串。或“C::399\4342)”，这些提醒我文件系统的路径，但我不确定。

问题文字：

考虑以下用 Prolog 编写的有限状态自动机。 似乎认出了什么？

假设有谓词

alphanumeric/1

当它的参数是字母或数字时，这是正确的。

自动机：

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

1 回答 1

3

好吧，前两个子句只是 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.]

因此，它接受以字符 AZ 开头的字符串，后跟一个冒号 ( :)，后跟零个或多个反斜杠冒号 ( :\)，后跟一个字母数字字符，然后是单词组中的零个或多个字符，[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:.

它只能包含一个点作为最后一个字符。此外，反斜杠不能是最后一个字符。它是一种基本的文件路径语言，尽管有一些重构。

于 2017-11-08T16:13:05.117 回答