DFA Language
DFA Language¶
The DFA rules can be implemented in a Programming Language of their own. A simple language for coding DFA’s can be found at this website: DFA Parser.
The Language is reasonably simple. It allows us to write code that looks more like the theoretical DFA.
The language uses # for comments. Any line that starts with # is ignored.
The alphabet of the DFA must be created. A set of symbols is given starting with the command symbols=(. The symbols in your alphabet are then entered seperated by commas. The line ends with a closing ).
For the toll gate, the line would be symbols=(N,D,Q).
Next, we need to list all the possible states the machine can be in. Again the line starts with a special variable states=( followed by a comma seperated list of states.
For the toll gate, the line would be states=(c0,c5,c10,c15,c20,c25,c30).
Every DFA has exactly one start state. The start state only has one value, not a comma seperated list. The start state for the toll gate would be start=c0.
A DFA can have multiple accept states. This is another comma seperated list, this time starting with the key variable name accept=(.
Finally, the transition table must be defined. This is done with a series of conditional statements. Each line follows the format if from_state and letter then to_state.
For example, if we want to transition from state c10 to c15 when a nickel is read, we would give the line if c10 and N then c15.
The full source code for the toll gate dfa is given below.
#Mark Boady
#Drexel University
#This DFA Accepts the Language
#L={ amount of change is at least 30 cents with sigma={N,D,Q} }
#Define DFA Properties
symbols=(N,D,Q)
states=(c0,c5,c10,c15,c20,c25,c30)
start=c0
accept=(c30)
#Define Transition Table
if c0 and N then c5
if c0 and D then c10
if c0 and Q then c25
if c5 and N then c10
if c5 and D then c15
if c5 and Q then c30
if c10 and N then c15
if c10 and D then c20
if c10 and Q then c30
if c15 and N then c20
if c15 and D then c25
if c15 and Q then c30
if c20 and N then c25
if c20 and D then c30
if c20 and Q then c30
if c25 and N then c30
if c25 and D then c30
if c25 and Q then c30
if c30 and N then c30
if c30 and D then c30
if c30 and Q then c30
There is a real language for working with DFA that is more complex. It is called Regular Expressions. These are built into most programming languages. The linux command grep also uses regular expressions. If you want to learn more about full regular expressions, you can start here.