PDA-er
PDA-er is an esoteric programming language created by User:Largejamie in March 2021 whose programs create and then run input on a Push-down 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]-[binary_3]-[binary_4]- |
Add a transition from the most recently created state to the state named [binary_4] that occurs on [binary_1], pops [binary_2] from the stack and pushes [binary_3] to the stack. [binary_1], [binary_2], and [binary_3] may all be blank, indicating epsilon-transitions.
|
The code it encounters after the first ! runs input on the PDA and is treated as follows:
| Character | Description |
|---|---|
.[binary]. |
Input [binary] to the PDA, following the appropriate transition
|
- |
Take input from the user to be input to the PDA. Each character in the string the user gives is fed as its ASCII value into the PDA |
Because PDAs are nondeterministic, there are often many possible ways to reach an accepting state when given a particular input (sometimes infinite). PDA-er will begin finding all possible paths to an accepting state on the given input, in order of the length of path. The first number encountered after the ! specifies which accepting path should be output. So if the first input is 1 (or 0), the shortest path will be output. If there are no possible accepting paths, nothing will be output.
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.
Nondeterminism is allowed, meaning you can have multiple transitions on a state involving the same symbol. You may also use epsilon-transitions (transitions that occur with no input being read), and transitions that do not pop/push to the stack.
The stack is empty when the program begins.
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.. That is, when a binary number is not specified as an input, it is assumed to be 0. This cannot be done when creating states or when declaring what symbol is read/popped/pushed on a transition, however.
Examples
Hello, world!
This program is as short as possible because it uses epsilon transitions between every single state and prints out the 35th output, which corresponds to "Hello, world!" There are many other possible "Hello, world!" programs, including some that will run faster because they are deterministic (see DFA-er's Hello, world! program for an example).
With whitespace, for readability:
.1001000. ----1100101- .1100101. ----1101100- .1101100. ----1101100- ----1101111- ----1100100- .1101111. ----101100- ----1110010- .101100. ----100000- .100000. ----1110111- .1110111. ----1101111- .1110010. ----1101100- .1100100. ----100001- ..100001. ! .100011.
Condensed:
.1001000.----1100101-.1100101.----1101100-.1101100.----1101100-----1101111-----1100100-.1101111.----101100-----1110010-.101100.----100000-.100000.----1110111-.1110111.----1101111-.1110010.----1101100-.1100100.----100001-..100001.!.100011.
Balanced?
Outputs Balanced! if it receives a balanced set of parentheses, otherwise outputs nothing.
.1.---1-- .0. -101000--0-- -101001-0--- --1--1000010- .1000010.----1100001- .1100001.-0---1101100- -1---1101110- .1101100.----1100001- .1101110.----1100011- .1100011.----1100101- .1100101.----1100100- .1100100.----100001- ..100001. ! .. - .0. .1.
Computational Class
PDA-er, as its name suggest, has the same power as a PDA, or Push-down automaton.
See PDA-er Pushdown Automaton Proof.
Similar Languages
PDA-er is syntactically similar to DFA-er, which is a similar language that runs on a Finite-state automaton instead of a Push-down automaton.