Search code examples
prologautomatonfinite-state-automaton

PROLOG a particular finite-state-automaton

I can't find an answer for the following problem. The automaton accept strings like "A:5739." or "C::399\4342)", and these reminds me the path of the file system, but i am not sure about that.

Problem text:

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

  • Well the first two clauses are simply how an NDFA is always executed: each time we lookup the next character in the list, and pass this through a delta/3 predicate to obtain a new state until we reached the end of the sequence, after which we can verify if the state is an accepting state.

    Next we see that start is the initial state, and that type is the only accepting state.

    The remainder of the program describes the delta/3 transitions. We can vizualize this, for instance using 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.]" ];
}

    This produces the following image:

    enter image description here

    Based on this diagram, we see that it accepts the language (regex notation):

    [A-Z]:(\:)*[A-Za-z0-9][A-Za-z0-9\]*[A-Za-z0-9.]

    So it accepts strings that start with a character A-Z, followed by a colon (:) followed by zero or more backslash-colons (:\) followed by an alphanumerical character followed by zero or more characters in the word group [A-Za-z0-9\.] followed by at least one alphanumerical character.

    So for example:

    X:\:0Azz0qdqd012QcCQCA
D:\:QA
B:\:\:QT
C:QWR.
C:\:a\q\b\QWR.
C:tempdir\bla\qux.
C:tempdir\bla\.
C:.

    It can only contain a dot as the last character. Furthermore the backslash can not be the last character. It is a basic file path language, although with some restructions.