Gummy Bear

Gummy Bear is a string-rewriting esolang.
== Overview ==
Source code consists of zero or more rules.
Each rule consists of four strings of bits, separated by dots. For example:
 101.1111..1
This is a single rule. It has four strings of bits: 101, 1111, (empty) and 1. It is also allowed to have four empty strings in a single rule:
 ...
The first string in a rule may optionally start with # character.
The second string in a rule may optionally end with # character.
Instead of third and fourth string, a single ~ character can appear (for example 10.1~ is a valid rule).
== I/O format ==
Input is a string of zero or more bits. Output is also a string of zero or more bits.
== Computation ==
First, we take the input string and prepend a single dot . character. For example, if the input string is 101, we will have
 .101
This is our main string. Computation consists of rewriting the main string until program halts.
There will always be a single dot in the main string. The dot divides the main string into left and right part.
=== Iteration ===
We perform these steps iteratively.
First, find the first rule whose first string represents the end of the left part of the main string and whose second string represents the start of the right part of the main string. If such rule cannot be found, terminate the program. If the found rule has ~ instead of third and fourth string, remove the matched substring from the main string and terminate the program.
==== Example 1 ====
Given the rules:
 101.11.0.10 // First rule
 101.10.1.11 // Second rule
and the main string:
 1101.10010
we will pick the second rule, because the second string of the first rule does not represent the start of the right part of the main string.
Once such rule is found, in the main string replace the matched substrings corresponding to the first and second rule strings with the third and fourth rule strings, respectively.
In the example above, after this iteration the main string will be
 11.11010
because 101 is replaced with 1 and 10 is replaced with 11.
==== Example 2 ====
Rules:
 1.0~
 01.000.0.11
Main string:
 0101.000
The first rule will be picked (both rules can be matched, but we pick the one that appears first in the source code). The rule has ~ character, so we remove 1.0 from the main string and terminate the program. The output is
 01000
=== Start/end patterns ===
If the first string of a rule starts with #, it means that the first string of that rule can be matched only on the start of the main string.
If the second string of a rule ends with #, it means that the second string of that rule can be matched only on the end of the main string.
For example, given the following two rules:
 #0... // First rule
 0... // Second rule
and the following main string:
 10.0010
Only the second rule can be matched, because the first rule can be matched only on the beginning of the main string, but because the main string has extra 1 on the beginning, the first rule cannot be applied.
== Output ==
Once program halts (no rules can be applied, or explicitly terminated by a ~ rule), the output is the main string without the dot character.
== Examples ==
In each example we provide the source code, sample input and output, and finally the computation steps for that particular input.
=== Cat ===
Source code:
 // noop
Input: 110101
Output: 110101
Explanation: if there are no rules in the source code, nothing can be applied and the program terminates immediately. Since the main string is the input prepended with a single dot character and the output is the main string without the dot character, therefore the output is the same as input.
=== Invert bits ===
Source code:
 .0.1.
 .1.0.
Input: 0101110
Output: 1010001
Computation steps:
 +----------------------------+
 | | |
 | Main string | Rule applied |
 | | |
 |============================|
 | | |
 | .0101110 | .0.1. |
 | | |
 |-------------|--------------|
 | | |
 | 1.101110 | .1.0. |
 | | |
 |-------------|--------------|
 | | |
 | 10.01110 | .0.1. |
 | | |
 |-------------|--------------|
 | | |
 | 101.1110 | .1.0. |
 | | |
 |-------------|--------------|
 | | |
 | 1010.110 | .1.0. |
 | | |
 |-------------|--------------|
 | | |
 | 10100.10 | .1.0. |
 | | |
 |-------------|--------------|
 | | |
 | 101000.0 | .0.1. |
 | | |
 |-------------|--------------|
 | | |
 | 1010001. | / |
 | | |
 +----------------------------+
=== Reverse bits ===
Source code:
 #..00.
 00.0.0000.
 00.1.0100.
 00.#.01.
 001..01.0
 101..01.1
 #01..10.
 10.0000.0010.00
 10.0001.0110.00
 10.0100.0010.01
 10.0101.0110.01
 10.001.01.101
 10.011.01.111
 10.00#.01.10
 10.01#.01.11
 10.1.11.1
 10.#~
 11.10.011.
 11.11.111.
 11.#~
Input: 11001
Output: 10011
Computation steps:
 +---------------------------------+
 | | |
 | Main string | Rule applied |
 | | |
 |=================================|
 | | |
 | .11001 | #..00. |
 | | |
 |---------------|-----------------|
 | | |
 | 00.11001 | 00.1.0100. |
 | | |
 |---------------|-----------------|
 | | |
 | 0100.1001 | 00.1.0100. |
 | | |
 |---------------|-----------------|
 | | |
 | 010100.001 | 00.0.0000. |
 | | |
 |---------------|-----------------|
 | | |
 | 01010000.01 | 00.0.0000. |
 | | |
 |---------------|-----------------|
 | | |
 | 0101000000.1 | 00.1.0100. |
 | | |
 |---------------|-----------------|
 | | |
 | 010100000100. | 00.#.01. |
 | | |
 |---------------|-----------------|
 | | |
 | 010100000101. | 101..01.1 |
 | | |
 |---------------|-----------------|
 | | |
 | 01010000001.1 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 0101000001.01 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 010100001.001 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 01010001.0001 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 0101001.00001 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 010101.000001 | 101..01.1 |
 | | |
 |---------------|-----------------|
 | | |
 | 01001.1000001 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 0101.01000001 | 101..01.1 |
 | | |
 |---------------|-----------------|
 | | |
 | 001.101000001 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 01.0101000001 | #01..10. |
 | | |
 |---------------|-----------------|
 | | |
 | 10.0101000001 | 10.0101.0110.01 |
 | | |
 |---------------|-----------------|
 | | |
 | 0110.01000001 | 10.0100.0010.01 |
 | | |
 |---------------|-----------------|
 | | |
 | 010010.010001 | 10.0100.0010.01 |
 | | |
 |---------------|-----------------|
 | | |
 | 01000010.0101 | 10.0101.0110.01 |
 | | |
 |---------------|-----------------|
 | | |
 | 0100000110.01 | 10.01#.01.11 |
 | | |
 |---------------|-----------------|
 | | |
 | 0100000101.11 | 101..01.1 |
 | | |
 |---------------|-----------------|
 | | |
 | 010000001.111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 01000001.0111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 0100001.00111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 010001.000111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 01001.0000111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 0101.00000111 | 101..01.1 |
 | | |
 |---------------|-----------------|
 | | |
 | 001.100000111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 01.0100000111 | #01..10. |
 | | |
 |---------------|-----------------|
 | | |
 | 10.0100000111 | 10.0100.0010.01 |
 | | |
 |---------------|-----------------|
 | | |
 | 0010.01000111 | 10.0100.0010.01 |
 | | |
 |---------------|-----------------|
 | | |
 | 000010.010111 | 10.0101.0110.01 |
 | | |
 |---------------|-----------------|
 | | |
 | 00000110.0111 | 10.011.01.111 |
 | | |
 |---------------|-----------------|
 | | |
 | 00000101.1111 | 101..01.1 |
 | | |
 |---------------|-----------------|
 | | |
 | 0000001.11111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 000001.011111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 00001.0011111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 0001.00011111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 001.000011111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 01.0000011111 | #01..10. |
 | | |
 |---------------|-----------------|
 | | |
 | 10.0000011111 | 10.0000.0010.00 |
 | | |
 |---------------|-----------------|
 | | |
 | 0010.00011111 | 10.0001.0110.00 |
 | | |
 |---------------|-----------------|
 | | |
 | 000110.001111 | 10.001.01.101 |
 | | |
 |---------------|-----------------|
 | | |
 | 000101.101111 | 101..01.1 |
 | | |
 |---------------|-----------------|
 | | |
 | 00001.1101111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 0001.01101111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 001.001101111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 01.0001101111 | #01..10. |
 | | |
 |---------------|-----------------|
 | | |
 | 10.0001101111 | 10.0001.0110.00 |
 | | |
 |---------------|-----------------|
 | | |
 | 0110.00101111 | 10.001.01.101 |
 | | |
 |---------------|-----------------|
 | | |
 | 0101.10101111 | 101..01.1 |
 | | |
 |---------------|-----------------|
 | | |
 | 001.110101111 | 001..01.0 |
 | | |
 |---------------|-----------------|
 | | |
 | 01.0110101111 | #01..10. |
 | | |
 |---------------|-----------------|
 | | |
 | 10.0110101111 | 10.011.01.111 |
 | | |
 |---------------|-----------------|
 | | |
 | 01.1110101111 | #01..10. |
 | | |
 |---------------|-----------------|
 | | |
 | 10.1110101111 | 10.1.11.1 |
 | | |
 |---------------|-----------------|
 | | |
 | 11.1110101111 | 11.11.111. |
 | | |
 |---------------|-----------------|
 | | |
 | 111.10101111 | 11.10.011. |
 | | |
 |---------------|-----------------|
 | | |
 | 1011.101111 | 11.10.011. |
 | | |
 |---------------|-----------------|
 | | |
 | 10011.1111 | 11.11.111. |
 | | |
 |---------------|-----------------|
 | | |
 | 100111.11 | 11.11.111. |
 | | |
 |---------------|-----------------|
 | | |
 | 1001111. | 11.#~ |
 | | |
 +---------------------------------+
== Interpreters ==
Interpreter
Category:Languages
Category:Turing complete
Category:Implemented
Category:2020
Category:String-rewriting paradigm