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.

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
(Terminology note: The arrows in a DFA diagram are formally called transitions between the states.)

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

hello cs students


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
students: true
hello cs students
: true
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.

Clarifications and Limitations