PROLOG a particular finite-state-automaton

Question

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

Can you show some effort of your own to solve the problem? — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Nov 8, 2017 at 15:47
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
– willeM_ Van Onsem, Commented Nov 8, 2017 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
– Fred_2, Commented Nov 8, 2017 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
– willeM_ Van Onsem, Commented Nov 8, 2017 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
– Fred_2, Commented Nov 8, 2017 at 16:11

willeM_ Van Onsem · Accepted Answer · 2017-11-08 16:13:05Z

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:

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.

Collectives™ on Stack Overflow

PROLOG a particular finite-state-automaton

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related