Ligature Machine

Definition

Ligature Machine invented by User:Zzo38 is a system consisting of:

• A set of symbols. (Normally, this is required to be a finite set.)
• A special begin symbol and end symbol.
• A rule table, mapping an ordered pair of symbols to the new symbol (called a ligature) and mode.
• Input list.
• Output list.

Operation starts by adding implicit begin/end symbols at the begin/end of the input list, and the start looking at the first pair (the begin symbol and the next one).

Find it in the table and perform the corresponding operation. It is replaced by the ligature symbol, and the | before and after means keep the first/second symbol before/after the ligature too; > means to advance the cursor to the next space.

Modes:

=:       *L
|=:      *FL
|=:>     F*L
=:|      *LS
=:|>     L*S
|=:|     *FLS
|=:|>    F*LS
|=:|>>   FL*S

(Above shows what happen if first symbol is called F, second symbol is called S, ligature symbol is called L, and an asterisk before the pair that will be scanned next.)

The begin symbol is only allowed as the first symbol in the input of a map, and the end symbol only as the second one. Furthermore, rules which are capable of adding/deleting begin and end symbols are not permitted.

Default rules may be considered as either a |=:> rule where the ligature matches the second symbol, or as a =:|> rule where the ligature matches the first symbol. Both cases give the same result.

Computational class

Conjecture (by User:coppro): This language can recognize exactly the regular languages, for some convenient definition of recognizing.

See also finite state transducer.

Variations

Commutative Ligature Machine

In addition to the components in the standard version, there is also a symmetric transitive binary relation defined, called a "commutativity relation".

A match considering with the rules includes not only the first and second symbol, but in between, a series of symbols all of which commute with the first symbol. The ligature symbol is then inserted immediately before the second symbol, and if the cursor is advanced to point to the ligature symbol, it is then pointing to the beginning of the series of commuting symbols.

Ligature-Counter Machine

Each cell in the input/output lists contains not only a symbol, but also a natural number.

Each rule then has, in its input, also a flag indicating whether the first cell has a zero or nonzero number, and whether the second cell has a zero or nonzero number. In its output there is an indication of one of the following, indicating the number which will be assigned to the ligature symbol:

• Zero
• First cell
• Second cell
• Increment first cell
• Increment second cell
• Decrement first cell (not if initially zero)
• Decrement second cell (not if initially zero)

Begin and end symbols are always zero.

Ligature Machine with Actions

The operation of the system is the same, except that the output of each rule has in addition, an action associated with it.

Actions are functions with two inputs and one output. When a rule is used, The action is called, using values in the cells associated with first and second symbols as inputs, and the output is then associated with the cell where the ligature symbol is placed.

Note that they are pure functions, and the types have to be the same for all actions.

Combinations

There are ways to combine its operation.

Reversing chain

This is a machine consisting of two ligature machines, with a machine that reverses its input in between.

A longer chain can consist of more than two, with reversing in between each one.

Iteration

Runs the same ligature machine multiple times. It halts once the output becomes the same as any previous output (or as the initial input).

Syntax

This is a syntax to represent the rule table in a ASCII text file:

• Comment: Start with # and lasts until the end of the line.
• Rule: Four items with spaces in between: first symbol (or * if the special begin symbol), second symbol (or * if the special end symbol), mode, ligature symbol (or * to keep the begin/end symbol which it has read; see above for restrictions).
• Symbol: The name of a symbol consists of one or more characters which are lowercase and uppercase ASCII letters, underscores, and digits.

In a rule, you can also use a question mark as the first or second symbol to mean all rules having anything in that position other than the ones otherwise explicitly specified.

Commutativity extensions:

• Relation: Define by a symbol and a space and = and space and the next symbol it commutes with.

Counter extensions:

• After the first/second symbol in rules, you can optionally add a = or + to mean zero or nonzero; if not specified, the rule applies to both.
• The mode can optionally have a =, -, or + before or after the :=. If not, then the ligature is zero. If it is, then it respectively means the same, decrement, or increment, the first or second symbol.

Action extensions:

• After the ligature symbol, optionally put ! and the action name, with no spaces in between.

Examples

Balanced parentheses

If you use A and B instead of ( and ), then this ligature-counter machine can accept balanced parentheses:

* A |=:|> X
X A +=: X
X+ B -=: X
X= * =: *

A commutative ligature machine can also do:

A = A
A B =: X
A X =: A
X A =: A
X * =: *