tag -- a Tag system processor

This program is a portable implementation of Emil Post's Tag systems [0].

Synopsis
  tag [OPTIONS]... [FILE] [INPUT]

Description
  Compile production rules of a Tag system given in FILE, run the system with given INPUT word, and print each step to standard output until the system halts.

  The syntax of production rules is as follows; each line starts with a character ("head"), followed by one or more spaces, and ends with a possibly empty word ("tail").  No two different rules have the same head.  Neither head nor tail can contain spaces.  Empty lines and ones starting with spaces are ignored.

  No spaces is allowed in any INPUT word.

  The behavior of a Tag system is determined by a constant, positive integer D called the deletion number.  D is 2 unless specified otherwise by -d option.  At each step of production, the only state of a Tag system is its current word, say W.  By default, the system halts if either (1) the length of W is less than D or (2) W's first character does not belong to the set of heads.  However, if -e option is specified, it halts only if either W is empty or (2) holds.  The rule which head matches with the leading character is applied; the updated word for next step is the concatenation of W and the tail of the matched rule, except its first D characters.

  -d D
         specify the deletion number D (default 2)

  -e
         halt only on the empty word regardless of the deletion number

  -i, --indent
         indent output, the depth of indentation is the deletion number multiplied by the step number

  -m, -m LENGTH
         exit if the length of the current word exceeds LENGTH (default 100)

  -n, -n NUM
         exit if the number of steps reaches NUM (default 100)

  -q, --quiet
         suppress output

  -h, --help
         display this help and exit

  --version
         output version information and exit

  Exit status is 0 if it halts, 1 if it exits due to -m or -n option's effect, 2 otherwise.

Example
  Production rules of a well-known 2-Tag system for Collatz (sub)sequences can be encoded in the following three lines:

  a bc
  b a
  c aaa

  Note that the leading spaces of the above rules are only for pretty formatting and must be avoided at a rule line.  Supposing that the rule file is named collatz.txt in the current directory, invoking tag as follows computes the system starting from word "aaa":

  $ tag collatz.txt aaa
  aaa
  abc
  cbc
  caaa
  aaaaa
  aaabc
  abcbc
  cbcbc
  cbcaaa
  caaaaaa
  aaaaaaaa
  aaaaaabc
  aaaabcbc
  aabcbcbc
  bcbcbcbc
  bcbcbca
  bcbcaa
  bcaaa
  aaaa
  aabc
  bcbc
  bca
  aa
  bc
  a

Author
  Takeshi Abe <tabe@fixedpoint.jp>

License
  The MIT license

[0] https://en.wikipedia.org/wiki/Tag_system