BF-PDA

From Esolang

BF-PDA is a simple programming language by User:ihope127, designed to be of use in a compression algorithm. The instructions are as follows:

@ Flips the bit on top of the stack.
. Outputs the bit on top of the stack (doesn't pop it).
< Pushes a 0 bit onto the stack.
> Pops a bit from the stack and throws it away.
[ While the bit on top of the stack is 1...
] End while.

If the stack ever runs out of bits, a zero is automatically pushed: that is, popping an empty stack doesn't do anything, and loops terminate when trying to peek at empty stacks.

BF-PDA can "probably" simulate any push-down automaton, and it is certainly not in a higher computational class.

A modification of this language adds a new stack which < pops from and > pushes to, however this stack has a finite length: pushing something onto it while it's full results in the bottom element being erased, and popping it while empty yields a 0-bit. The size of this stack is defined by the programmer. Equivalently, the "tape" extends to the left for some number of cells.

Another modification allows this language to store numbers up to a predefined number. For numbers greater than 2, @ is replaced with + and -, and [ loops while nonzero.