Liberation

Liberation is a string-rewriting esolang which works with a string of active and passive elements.
== Overview ==
There is a main string which contains active and passive elements.
Passive elements are bits. They can be either 0 or 1.
Active elements are denoted by . and they can perform rewritings around themselves.
== Syntax ==
Source code consists of one or more rules. Each rule has a pattern on the left and a replacement on the right, separated by a hyphen.
Pattern must contain exactly one symbol . and can contain zero or more bits before and after . symbol. Before the pattern and/or after the pattern symbols # may appear - they represent start/end of the entire string.
Replacement is the new substring that will be added instead of the pattern if the pattern is matched. It can contain bits and/or arbitrary number of . symbols. It also can be empty, and that is denoted by / symbol.
Example:
 #10.1 - 1..10.
It means that each time 10.1 appears on the beginning of the main string, it will be replaced by 1..10.
== Errors ==
It is a syntax error if it is theoretically possible to match a single . symbol against multiple rules in some string.
It is a runtime error if no rule can be applied to any . and there is still at least one . in the main string.
== I/O format ==
Input is a sequence of bits. The main list is formed by simply prepending a single . symbol before the input string.
Program halts when there are no more . symbols in the string. The string of bits that is left is the output.
== Replacing ==
Replacing is performed in batchs. In each iteration (replacement) all . symbols that can be matched against a single rule are marked and their surrounding (that is matched with the pattern of the rule) is deleted, then they are replaced with the replacement of the rule.
=== Example ===
Given the following source code:
 0.1 - 0
 1.0 - 1
 11.# - 10
and the following main string before some iteration:
 100.1.01.
There are three . symbols. The first one can be matched against the first rule and the second one can be matched against the second rule. The third . cannot be matched in this iteration. Note that bit 1 between the two . symbols is common to both of them. All bits that are part of at least one matched pattern are removed and each . symbol that is successfully matched will be replaced accordingly. After this iteration the main string will be:
 10011.
In the next iteration, the third rule will be aplied and we will have:
 10010
which is also the end of the program execution.
== Examples ==
In all examples we use input string 1011 for explaining computation steps.
=== Cat ===
Program:
 . - /
Computation:
 .1011
 1011
=== Extract first bit ===
Program:
 #.# - /
 #.0 - 00.
 #.1 - 10.
 0.0 - 0.
 0.1 - 0.
 0.# - /
Computation:
 .1011
 10.011
 10.11
 10.1
 10.
 1
=== Remove first bit ===
Program:
 #.# - /
 #.0 - /
 #.1 - /
Computation:
 .1011
 011
=== Remove last bit ===
Program:
 #. - 0.
 0.00 - 00.0
 0.01 - 00.1
 0.10 - 10.0
 0.11 - 10.1
 0.0# - /
 0.1# - /
 0.# - /
Computation:
 .1011
 0.1011
 10.011
 100.11
 1010.1
 101
=== Invert bits ===
Program:
 .0 - 1.
 .1 - 0.
 .# - /
Computation:
 .1011
 0.011
 01.11
 010.1
 0100.
 0100
=== Reverse bits ===
Program:
 #. - 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.# - /
Computation:
 .1011
 00.1011
 0100.011
 010000.11
 01000100.1
 0100010100.
 0100010101.
 010001001.1
 01000101.01
 0100001.101
 010001.0101
 01001.00101
 0101.000101
 001.1000101
 01.01000101
 10.01000101
 0010.010101
 000110.0101
 00010110.01
 00010101.11
 0001001.111
 000101.0111
 00001.10111
 0001.010111
 001.0010111
 01.00010111
 10.00010111
 0110.000111
 010110.0011
 010101.1011
 01001.11011
 0101.011011
 001.1011011
 01.01011011
 10.01011011
 0110.011011
 0101.111011
 001.1111011
 01.01111011
 10.01111011
 01.11111011
 10.11111011
 11.11111011
 111.111011
 1111.1011
 11011.11
 110111.
 1101
== Interpreters ==
Interpreter
Category:Languages
Category:Turing complete
Category:Implemented
Category:2020
Category:String-rewriting paradigm