Finite State Machines as a Knowledge Base

A finite state machine (FSM) is a simple computer model. Its memory can be in one of a finite number of states. Its instructions have the form

transition(State0, E, Guard = true, State1),

This means "if the FSM is in State0 when event E occurs, and if Guard is true, then the FSM transitions to State1."

We can depict a FSM as a graph with nodes representing states and arrows transitions:

In this model State1 is the initial state, and State4 is the final state.

A sequence of events is recognized by an FSM if, starting in its initial state, the FSM is in a final state after all events in the sequence are processed.

In formal language theory we learn that any set of strings that can be recognized by a FSM can be defined by a regular expression and vice-versa.

In software engineering FSMs are used to model the lifecycles of objects. For example, the states of a thread's lifecycle might include running, terminated, blocked, and sleeping.

In language processing FSMs are used to recognize tokens. In other words, FSMs are scanners.

For example, identifier tokens might be defined as:

identifier ::= [a-zA-Z][a-zA-Z0-9]*

Here's the corresponding identifier FSM:

Notes:

·       Next = the next character in the input list.

·       Any non-alphanumeric character sends the non-final FSM to the dead state where it gets stuck.

Problems

Problem 1

Every FSM (every directed graph for that matter) can be defined by a prolog predicate:

transition(A, C, B)

This means: in state A if the next character is C, then the FSM will transition to state B.

Define and test the identifier FSM as a Prolog transition predicate.

Hint: SWI Prolog provides the following useful predicates:

is_alpha(C) // = true if C is a letter
is_digit(C) // = true if C is a digit

Problem 2

Define and test the predicate:

moves(A, CharList, B)

This means: starting in state A, an FSM (any FSM), will end up in state B after processing every character in CharList.

For example, for the FSM above:

?- moves(state0, ['a', '3', 'b', 'J'], state1).
true

Hint:

It might be helpful to read through the notes on list processing in Prolog.

Problem 3

Define and test the predicate:

accept(someString)

This predicate is true when someString is accepted by the identifier FSM, and false otherwise.

For example:

?- accept("r9b3X").
true ;
false.

?- accept("3Rfn").
false.

?- accept("b3$m")
false.

Hint:

Prolog provides the predicate:

string_chars(someString, someList)

This is true when someList is the list of characters appearing in someString. For example:

?- string_chars("abc", X).
X = [a, b, c].