Deadfish PDA

From Esolang
Jump to navigation Jump to search

Deadfish PDA is a version of Deadfish by User:BoundedBeans that resembles a push-down automaton.


The numbers in Deadfish PDA are the states, however unlike traditional Deadfish, you cannot bypass the 1-byte limit by squaring. You can't go below -1, and you can't go above 256. You also can't have values of -1 or 256.

So this is a 256 state machine. That's a lot of states! Luckily we can just store this as an integer. When a program attempts to go below 0 or above 255, the program halts. The user can also define more halt states.

There are 3 aspects that can be used:

  1. Input. Input can be either X, Y, Z, or ?. (4 character input alphabet) ? can be typed in directly, but any character that is not XYZ? will also be treated as ?.
  2. The states.
  3. The top of the stack. This can either be A, B, C, or ! (4 character stack alphabet). An empty stack returns !.


The program takes an input before each step. If input is not given, treat as ?. Use the input, the state, and the top of the stack, look for it in the cases; if it is found, run the respective transition. If the current case is not listed, run the default transition.


Programs have alternating line structure, consisting of transitions and cases. It starts and ends with a transition.

Line 1 is the default transition. This happens when no other cases are met.

All following even lines are the cases, and the odd lines following them are the transitions for those cases.

Case syntax

(state) (input letter) (top stack letter)

Example, checks if the state is 49, the input is Z, and the letter at the top of the stack is B: 49 Z B

Transition syntax

(deadfish code to alter the state, commands can be # for a no-op) (1 if it should pop the stack, 0 if not) (symbol to push onto the stack, # if no push) (1 if halt, 0 if not)

Note: Originally there was supposed to be a maximum of two deadfish commands per transition. However, while publishing this language, I have decided to allow more than two commands of deadfish code in a transition. If using zero commands of deadfish code, you must use a hashtag (a no-op) in order to prevent glitches.

Example, squares the state, pop the stack, and push !:

s# 1 ! 0

Example, decrements and outputs, don't push

do 0 # 0

Example, outputs twice, halts:

oo 0 # 1

Example, increments, squares, outputs three times, pops the stack, and pushes B:

isooo 1 B 0

Whether output is in ASCII or decimal should be a choice in the implementation.


There isn't a ton to do with this language, having a maximum of 256 states, 4 input symbols, and 4 stack symbols, and the fact that any sort of multi-case category has to be repeated with all of the possibilities (for example checking if the state is 5 requires writing every combination of input and stack symbols with state 5, all with the same transition). However, some basic pushdown automata can be recreated.

"Y" x times, "Z" x times

(Outputs 0 if the input matches, 1 if it doesn't) (Output should be chosen as decimal now that there is an option)

io 0 # 1
0 Y !
ii 0 # 0
2 Y !
dd 0 A 0
0 Y A
# 0 A 0
0 Z A
iii 1 # 0
3 ? A
ddo 0 # 1
3 Z A
# 1 # 0
3 Z !
i 0 # 0
4 ? !
ddddo 0 # 1
4 Z !
dddo 0 # 1
4 Y !
dddo 0 # 1
2 Z !
do 0 # 1
3 Y A
ddo 0 # 1
3 Y !
ddo 0 # 1


Enter X for 0 and Y for 1.

ASCII output:

o 0 # 0
0 X !
iisiiisdo 0 # 1
0 Y !
iisiiis 0 # 0

Numeric output:

o 0 # 0
0 X !
o 0 # 1
0 Y !
i 0 # 0

See also

External resources