Walnut file format

File kinds

Walnut accepts three kinds of .txt files:

1. Automaton (Moore-style: acceptance is a state output)
2. Transducer (Mealy-style: output is on transitions)
3. TRUE/FALSE single-line files (true or false only)

These automata are usually deterministic, but non-deterministic is supported.

A file starts with optional comments/blank lines, then either:

• a single line true or false (and nothing else), or
• one alphabet declaration line, followed by state/transition blocks.

Comments are lines starting with #. Blank lines are okay anywhere. Extra whitespace is ignored.

---

1) The number system declaration (header line)

Accepted token forms

• Number systems

  • msd_2, lsd_10, msd2, lsd16
  • Also msd or lsd without an explicit base are accepted by the regex, but it’s safer to specify the base explicitly.
  • For number-system inputs Walnut expects digits that at least include 0 and 1 (this is validated).

• Explicit sets

  • { 0, 1, 2 } or { +1, -1, 0 }
  • Duplicates are removed.

Examples

msd_2
msd_2 {0,1,2}
lsd_10 lsd_10
{0,1} {0,1,2,3}

The number of tokens on this line determines the arity (tuple size) expected for each transition input.

---

2) Automaton files

2.1 State declarations

One line per state, after the alphabet line:

<stateId> <output>

• <stateId>: non-negative integer
• <output>: integer (conventionally 0 = rejecting, 1 = accepting)
• The first declared state becomes the initial state q0.
• You may declare states in any order; they must be declared somewhere in the file if used as a destination.

Example

0 0       # state 0 is non-accepting
1 1       # state 1 is accepting

2.2 Transitions

Lines of the form:

<input_tuple> -> <destination_list>

• The input tuple must have exactly as many components as the alphabet arity.
• Components are integers or * (wildcard).
• The destination list is one or more state IDs (space-separated). Multiple IDs means nondeterministic transition.

Examples

0 -> 0
1 -> 1
1 -> 3 4
* -> 5

Wildcards: * expands to “all symbols” for that component. If multiple components use *, Walnut expands to the Cartesian product.

---

3) Transducer files

Transducers differ only in two places: the state line and the transition line.

3.1 State declarations

Just the state ID (there’s no per-state output):

<stateId>

Example:

0
1
2

3.2 Transitions (with output on the transition)

<input_tuple> -> <destination_list> / <output>

• <output> must be a single integer.
• Inputs and destinations follow the same rules as automata.
• For a given (state, input_letter) there should effectively be one output.

Examples

0 -> 0 / 1
1 -> 1 / 0
* 0 -> 2 / 7

All other validations (arity, declared states, etc.) still apply.

---

4) Special true / false files

A file that is exactly:

true

or

false

(with only comments/whitespace otherwise) is treated as a universal acceptor or universal rejector respectively. No alphabet or states follow.