DFA-er

From Esolang
Jump to navigation Jump to search

DFA-er is an esoteric programming language created by User:Largejamie in March 2021 whose programs create and then run input on a Finite-state automaton.

Overview

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:

Character Description
.[binary]. Create a failing state named [binary]
..[binary]. Create an accepting state named [binary]
-[binary_1]-[binary_2]- Add a transition from the most recently created state to the state named [binary_2] that occurs on [binary_1]

The code it encounters after the first ! runs input on the DFA and is treated as follows:

Character Description
.[binary]. Input [binary] to the DFA, following the appropriate transition
- 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.

If a - occurs between two .'s, it is ignored, and vise versa. All !'s except for the first one are ignored. All 0's and 1's that do not occur within .'s or -'s are ignored.

If .. 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.

Examples

Hello, world!

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

Condensed:

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

Cat (binary)

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-
!
-

Cat

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

Computational Class

DFA-er, as its name suggest, has the same power as a DFA, or Finite-state automaton.

See DFA-er Finite State Automaton Proof.

Similar Languages

DFA-er is syntactically similar to PDA-er, which is a similar language that runs on a Push-down automaton instead of a finite-state automaton.

Interpreters

Interpreter in Python