Finite Choice: Type-4 Grammars

Generally, the bottom of the Chomnsky heirachy is Type-3 Grammars: regular languages. He never described nor identified Type-4 Grammars. However, they further restrict regular languages by removing all possible non-terminals. Type-4 grammars have been called "Finite Choice Grammars". Finite Choice (FC), are only able to preform a simply look up to assert if a string is part of the language or not. They have no generative power.

Keywords in programming languages are often a finite choice.

Keyword ::= "return" | "if" | "else" | "then" | "end" | ...

"Parsing Techniques: A Practical Guide" by Dick Grune and Ceriel Jacobs describes this extension. This is the main (and possibly only?) source I discovered thier concept from. It doesn't seem to be described anywhere. Possibly, it's not interesting. However, in the context of an esolang, it becomes a bit more fun to play with.

For kicks and giggles, Type-5 grammars are grammars of a single string. Type-6 and up are just grammars of empty strings. The hierarchy is now completed.

June's Bitpushing VM

I ended up finding this after messing with June's multistack bit-oriented VM. The language is very much a brainfuck inspired language. It has a small set of instructions. The main ones of interest are: 1 (push one), 0 (push 0), [ (jump to matching ] if 0), ] (jump back to matching [ unconditionally).

I wanted to see how much you could do with just one stack, and immediately hit a wall. After some back and forth with her, I realized the language is less powerful than a PDA. [ will only run code if a 1 is at the top of the stack. Additionally, there is no inverse operation nor a logical-not operation.

Thus you can't do something when reading 0 with only a single stack. The choice language of [ is only {1}. But after some more back and forth with June. I found you could make a new finite-choice language.

Using the encoding {10, 01} for {0, 1}, you can make choices on 0.

[[] ...if 01... 00] [...else 10... 0]

This code basically forms an if-else. The first [ decodes the first bit. When that bit is a zero, it falls through to the second block. Additionally, the first block pushes enough 0 bits to terminate the next conditional check.

This is expressive enough to implement logical-not on a single stack:

[[]1000][010]

And even a swap without needing any additional stacks:

[[][[]010100][01100]00][[[]100100][10100]0]

This encoding scheme maps to four-value logic. It has the useful property that 00 can be used to break loops and noop. Not sure what 11 can be used for yet, but it exist.