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 < input.dfa

Here is an example of a DFA file for a DFA that recognizes strings over the alphabet {a, b, ..., z} that contain cs. The text in italics is not part of the file, and is just there to describe how the file works.

a-b d-r t-z
c s
start   a b d-z  start
start   c        seen_c
seen_c  a-r t-z  start
seen_c  s        seen_cs
seen_cs a-z      seen_cs
cstwofourone bstwofournone

character ranges can be specified
or characters can be listed individually

first state listed is the initial state

! marks a state as accepting

loop at 'start' on a, b, and d-z
transition from 'start' to 'seen_c' on c

this special keyword is treated as the empty string

can list multiple inputs on one line

For this file, the output of cs241.DFA is:

$ cs241.DFA < input.dfa
hellocsstudents true
.EMPTY false
lyrics true
cstwofourone true
bstwofournone false

The output indicates which input strings were accepted by the DFA.

Formal Specification

The DFA is encoded in three sections (alphabet, states, transitions) and then the input is encoded in a fourth section.

Clarifications and Limitations