ПРОЛОГ конкретный конечный автомат

Question

Я не могу найти ответ на следующую проблему. Автомат принимает строки типа "A:5739". или "C::399\4342)", и это напоминает мне путь к файловой системе, но я не уверен в этом.

Текст задачи:

Рассмотрим следующий конечный автомат, написанный на Прологе. Что, кажется, признает?

Предположим, что есть предикат

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

Answer 1

Первые два предложения - это просто то, как всегда выполняется 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:.

Он может содержать только точку в качестве последнего символа. Кроме того, обратный слеш не может быть последним символом. Это основной язык пути к файлу, хотя и с некоторыми изменениями.