2

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).
coder
  • 12,832
  • 5
  • 39
  • 53
Fred_2
  • 249
  • 2
  • 11
  • 1
    Can you show *some* effort of your own to solve the problem? – Willem Van Onsem Nov 08 '17 at 15:47
  • 1
    I know that the automaton accepts some kind of regular language. But what seems to be missing in the question, is a fair attempt from your side. What have you tried to solve the problem? What problems did you encounter? Where are you stuck? Currently this question seems like homework copied (almost) verbatim. – Willem Van Onsem Nov 08 '17 at 15:56
  • I tried to draw the automaton, tried to write down some strings accepted by the automaton (like A:5739. or C:\:399\4342)... The example i wrote reminds me the path of the file system...could probably be connected to some language like JSON? – Fred_2 Nov 08 '17 at 16:03
  • Not JSON, since JSON is a context-free language, not a regular language. You are in the right direction. Please [edit] your question and add your though process. – Willem Van Onsem Nov 08 '17 at 16:04
  • The answer could be: The automaton recognize a path, which represent the specific position of a file or directory inside a data storage with a file system tree-structured. ? – Fred_2 Nov 08 '17 at 16:11

1 Answers1

3

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.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555