DFA File Format

A .dfa file represents a deterministic finite automaton (DFA) together with some optional input data.

You can use the cs241.DFA tool to check the syntax of these files and to process the strings in the input data with the DFA:

cs241.DFA < file.dfa

Here is an example of a DFA file for a DFA that recognizes strings of lowercase alphabet letters (a-z), spaces, and newlines that contain the substring cs. The text in italics is not part of the file, and is just there to describe how the file works.

.STATES start seen_c seen_cs! .TRANSITIONS start a b d-z \s \n start start c seen_c seen_c a-r t-z \s \n start seen_c s seen_cs seen_cs a-z \s \n seen_cs

first state listed is the initial state ! marks a state as accepting loop at 'start' on a, b, d-z, space (\s), and newline (\n) transition from 'start' to 'seen_c' on c transition from 'seen_c' to 'start' on a-r, t-z, space, and newline transition from 'seen_c' to 'seen_cs' on s loop at 'seen_cs' on a-z, space, newline

After the description of the DFA, you can optionally provide any number of input strings for the DFA to process. Here are some examples:

.INPUT
hello
cs
students
.INPUT
hello cs students

.INPUT
tactics\nand\slyrics
.INPUT
cstwofourone\s
.INPUT

.INPUT
bstwofournone

each input string starts with a .INPUT header


whitespace at the end of the final line is ignored; this input does not end with a newline


this input DOES end with a newline, but only one, not two

escape sequences are interpreted; this input contains one newline and one space

this input ends with a space, escape sequence whitespace is not trimmed

this input (blank line) is treated as the empty string

Suppose the above data (DFA description and input) is combined and stored in a file called cs.dfa. The output of cs241.DFA for this file is:

cs241.DFA < cs.dfa
hello
cs
students: true
hello cs students
: true
tactics
and lyrics: true
cstwofourone : true
: false
bstwofournone: false

The output indicates which input strings were accepted by the DFA. Note that the escape sequences \s and \n for space and newline have been replaced in the output.

Formal Specification

The DFA is encoded in two sections (states and transitions). After this, any number of optional input sections can appear.

• The states and transitions sections both must be included, and must appear in that order (states followed by transitions). The input section can be omitted if it is not needed.
• The states section consists of a header line containing the string .STATE, followed by a sequence of whitespace-separated strings representing state names.
  • The first string in the sequence is the initial state.
  • Adding an exclamation mark at the end of a state name marks it as an accepting state.
• The transitions section consists of a header line containing the string .TRANSITIONS, followed by a sequence of lines representing transition collections. A transition collection has three parts, each separated by (non-newline) whitespace:
  • The first string on the line is a state name for the from-state.
  • The last string on the line is a state name for the to-state.
  • In between is a collection of transition characters, specified as a whitespace-separated sequence of characters or ranges.
  • A character is a single printable, non-whitespace ASCII character (codes 0x21 to 0x7e), OR one of the following multi-character escape sequences:
    • \s representing a space (ASCII 0x20)
    • \n representing a line feed (ASCII 0x0a)
    • \r representing a carriage return (ASCII 0x0d)
    • \t representing a horizontal tab (ASCII 0x09)
    • \xHH representing the character with ASCII code 0xHH, where H stands for a hex digit (0-9 or a-f or A-F); codes 0x80 to 0xFF (outside the ASCII range) are not allowed
  • A range is two characters (as defined above, i.e., escape sequences included) separated by a hyphen - (ASCII 0x2D), and represents the range of ASCII characters whose codes are between the first character and second character (inclusive).
  The meaning of a transition collection is: for each character in the transition characters, there is a transition (i.e., an arrow) from the from-state to the to-state on that character.
  Nondeterministic transitions (multiple transitions for the same state-character pair) are not allowed. For example, you cannot have the transition state1 a state2 and also have state1 a state3.
  It is not necessary to specify a transition for every state-character pair. The cs241.DFA tool allows leaving transitions undefined, and will reject an input string if it would cause an undefined transition to be taken.
• An input section consists of a header line containing the string .INPUT, followed an input string.
  • The cs241.DFA tool will interpret the contents of each input section as a string to run through the DFA using the DFA recognition algorithm.
    The tool will print each input string, followed by true (if the string was accepted) or false (if it was not accepted).
    Trailing whitespace is normally trimmed from the last line of the input string, and then the terminating newline is removed. You can override this by using escape sequences like \s or \n, which are not trimmed, to specify whitespace.
  • If you write your own program that works with DFA files, you are free to ignore input sections, or to interpret them or use them in a different way.

Clarifications and Limitations

• The file format only supports transitions on ASCII characters. Non-ASCII characters will cause an error.
• This file format is for DFAs only. Technically a very similar file format could be used to describe NFAs (nondeterministic finite automata) but we do not have a course tool that handles this.
• The exclamation mark (!) used to indicate whether a state is accepting is not part of the state name. This means you cannot have a non-accepting state whose name ends with an exclamation mark.
• Exception to the above: A state name that consists of a single exclamation mark will be treated as a non-accepting state with name "!".
• You can have accepting states that end with an exclamation mark if you include two exclamation marks. For example, bang!! would correspond to a state named bang! that is accepting.
• The string .TRANSITIONS cannot be used as a state name, since it marks the end of the states section.
• Each .INPUT section header must appear on its own line, or else it may be interpreted as a part of the previous section.