DFA-er only uses the characters
.-01!, and every other character is simply ignored and may be treated as a comment.
DFA-er begins by splitting the program on the first
! it encounters.
The code it encounters before the first
! creates the DFA and is treated as follows:
||Create a failing state named |
||Create an accepting state named |
||Add a transition from the most recently created state to the state named |
The code it encounters after the first
! runs input on the DFA and is treated as follows:
||Take input from the user to be input to the DFA. Each character in the string the user gives is fed as its ASCII value into the DFA|
Once the last input is read into the DFA, it will halt. If it halts in an accepting state, it will print out all of the states that it passed through while taking input. Otherwise, it will output nothing. If it ever encounters an input for which a transition does not exist, it will immediately halt and output nothing.
The first state that is created is assumed to be the starting state. If a state is put as the destination of a transition before it has been explicitly created, it will be created as a failing state. States may be defined multiple times, and the last definition determines whether it is an accepting state or not.
If multiple transitions are created from the same state on the same symbol, the last transition determines where the transition actually occurs. That is, nondeterminism is not allowed.
- occurs between two
.'s, it is ignored, and vise versa. All
!'s except for the first one are ignored. All
1's that do not occur within
-'s are ignored.
.. is given as input, it is equivalent to
.0., and similarly when creating transitions,
--- is equivalent to
-0-0-. That is, when a binary number is not specified, it is assumed to be 0. This cannot be done when creating states, however, because it uses the
..[binary]. syntax to indicate accepting/failing.
With whitespace, for readability:
.1001000. --1100101- .1100101. --1101100- .1101100. --1101100- -1-1101111- -10-1100100- .1101111. --101100- -1-1110010- .101100. --100000- .100000. --1110111- .1110111. --1101111- .1110010. --1101100- .1100100. --100001- ..100001. ! .......1..........1....10...
A program that, given a series of 0s and 1s, will print out the series of 0s and 1s it received
.0. -110000-110000- -110001-110001- ..110000. -110000-110000- -110001-110001- ..110001. -110000-110000- -110001-110001- ! -
You can generate a cat program in DFA-er using the following python code:
with open('cat', 'w') as f: for i in range(0,256): f.write('..') f.write(bin(i)) f.write('.') for j in range(0,256): f.write('-') f.write(bin(j)) f.write('-') f.write(bin(j)) f.write('-') f.write('!-')
For the full program (1.32 MB), see here
DFA-er, as its name suggest, has the same power as a DFA, or Finite-state automaton.