A file format for finite automata

This file format can be used in some of the assignments. Save every automaton in a separate text file using the UTF-8 character encoding.

A valid file must contain the following information, in the given order:

• One line with the alphabet Σ (or, in the case of ε-NFAs, Σ ∪ {ε}):

  The line must contain the name of every element in Σ (or Σ ∪ {ε}), separated by (and optionally preceded and/or followed by) whitespace. The element ε must be called ε or eps. No name may be given twice.

  Let us assume that the elements are given in the following order: c₁, …, c_n.

• Then one line per state. Each line should contain the following information, in the given order, separated by (and optionally preceded and/or followed by) whitespace:

  • If the state is an initial state: → or ->.

  • If the state is an accepting state: *.

  • The name s of the state.

  • If the automaton is a DFA with transition function δ: The states δ(c₁), …, δ(c_n), separated by whitespace.

  • If the automaton is an NFA, with or without ε-transitions, with transition function δ: The sets δ(c₁), …, δ(c_n), separated by whitespace. Sets of states are represented in the following way:

    • The character {.

    • A whitespace-separated list (optionally preceded and/or followed by whitespace) containing the name of each state in the set exactly once.

    • The character }.

Names of elements in Σ and names of states must not contain whitespace or the characters #, { or }, and must not be ε, eps, →, -> or *.

Comments are allowed. If a line contains the character #, then everything from this character to the end of the line is ignored.

Lines containing nothing but whitespace and/or comments are allowed and ignored.

Examples

Consider the DFA with the following transition table:

This DFA can (for instance) be represented in the following way:

       a  b  c
→ * s₀ s₁ s₀ s₂
    s₁ s₂ s₁ s₁
  * s₂ s₂ s₂ s₂

As a second example, consider the following NFA without ε-transitions:

This NFA can (for instance) be represented in the following way:

     a    b    c
→ s₀ {s₀} {s₁} {s₀ s₂}
  s₁ {}   {s₃} {s₂}
  s₂ {}   {s₁} {s₄}
  s₃ {s₄} {}   {s₃}
* s₄ {}   {s₄} {}

Now consider the ε-NFA with the following transition table:

This ε-NFA can (for instance) be represented in the following way:

# An ε-NFA.

ε a b

→ s₀ {} {s₁} {s₀ s₂}
s₁ {s₂} {s₄} {s₃}
s₂ {} {s₁ s₄} {s₃}
s₃ {s₅} {s₄ s₅} {}
s₄ {s₃} {} {s₅}
* s₅ {} {s₅} {s₅}