You may be turned off by the cumbersome header for the constructor method for the finite automata classes. In deed, the class constructors are tedious and require the creation and specification of a number of lengthy data structures which is inconvenient at best. For this reason, TheoryAssistant uses a simpler syntax to describe and instantiate machine, one which is modeled on the GrafState syntax. GrafState is a tool developed by Prof. Bill Hollingsworth at the University of Georgia as an aid to undergraduate students in the exploration of formal languages and automata.

A DFA is a five tuple, M=(Q,S,D,q0,F), where Q is the set of states, S is an alphabet (a set of symbols), D is a transition function with domain Q cross S and range Q, q0 is the start state of the machine, and F is the set of accept states. The following is a sample description of a machine in grafstate syntax as well as a description of each of the relevant parts of the description following.

First Sample Machine Description

The following is a description of a DFA which recognizes all strings over the alphabet {0,1} which have an even length:

Q = {q0,q1};
S = {0,1};
d(q0,0)=q1;
d(q0,1)=q1;
d(q1,0)=q0;
d(q1,1)=q0;
q0=q0;
F={q0};

Now let's look closer at the individual pieces of the above description.

Line separators

White space in the description of a formal automaton is ignored. Statements (lines) are separated by semicolons.

The Title

Each machine description may contain an optional title specification. The syntax for the title description is title = "some title";. The only valid characters in a title are alphanumeric characters (a-z, A-Z, 0-9), underscores, and white space. White space IS NOT ignored in describing a title. Please note that the title is the ONLY portion of the DFA description which is optional.

The Set of States

The set of states is a required part of the description of a DFA. The syntax for the description of the set of states is Q={q1,q2,q3};. This would describe a set of states for a machine with three states. The description begins with Q= and the set of states is described by a comma separated list enclosed in squiggly brackets. See the note below in regards to the "NullState" question.

The Alphabet

The alphabet of the machine is a required part of the description of a DFA. The syntax for the description of the alphabet is S={0,1};. This would describe a set of symbols for a machine with an alphabet with just two symbols. The description begins with S= and the set of symbols is descrbied by a comma separated list enclosed in squiggly brackets.

The Transition Function

The transition function is a required part of the description of a DFA. It is described over a number of zero or more lines. Each pre-image of the transition function is mapped to an image by the following syntax: d(q,a)=q';, where (q,a) is the pre-image, and q' is the image. It is important to note that the transition function of a DFA is a well defined function. In other words, each pre-image in the domain must be related to an image in the range of the function. Often a DFA is more clearly and simply defined with a simplified transition function which only includes the "meaningful" transitions and states. In these cases there is an implicitly defined NullState is added to the set of states for the machine and the following rule is employed; for every pre-image in the domain of the transition function - for example (q,a) - for which a relation to the range is not defined, the following relation is added to the transition function: d(q,a)=NullState.

The Start State

The start state is a required part of the description of a DFA. The syntax for the description of the start state of a DFA is q0=q; where the state q is a member of the set of states Q. There can only be one start state, and it must also be a member of the set of states.

The Accept States

The set of accept states is a required part of the description of a DFA. The syntax for the description of the set of accept states is F={q1,q2,q3};. The set of accept states, F, must be a subset of the set of states, Q. The description begins with F= and the set of states is described by a comma separated list enclosed in squiggly brackets. See the note below in regards to the "NullState" question.

Machines with Implicit Reject States and Transitions

Some times all of the states and transitions describing a DFA are not necessary to understanding the function of the machine; in fact it is often the case that a machine is actually more clear when it employs an implicit "null state" or "dead state" which the machine cannot leave once it enters the state. The theory assistant syntax allows machines to be designed with an implicit null state according to the following rule: for any state, q, and any symbol, a, if no image in the transition function is explicitly defined for the pre-image (q,a) then it is assumed that the following transition is intended: d(q,a)=NullState. In this case, the NullState need not be included in the set of states either: the existence of both the NullState and any pre-image to image relationships concerning the null state are all implicitly defined.

The following is a valid description of a machine which recognizes all strings over the alphabet {0,1} which do not contain any 1's:

title="Sample_Machine2a";
Q = {q0};
S = {0,1};
d(q0,0)=q1;
q0=q0;
F={q0};

In this case the existence of the Null State is inferred and the following is an equivalent, more explicit description of the same machine:

title="Sample_Machine2b";
Q = {q0,NullState};
S = {0,1};
d(q0,0)=q1;
d(q0,1)=NullState;
d(NullState,0)=NullState
d(NullState,1)=NullState
q0=q0;
F={q0};

Next Steps

Next up, familiarize yourself with the parser class for parsing GrafState syntax, a very simple class which provides a very necessary function.