Finite Automata Simulator

A DFA / NFA / ε-NFA simulator written in pure Python.
Define an automaton in a plain-text file, then check which strings its language accepts.

---

Overview

This project implements a small engine for the three classic models of finite-state computation taught in a Formal Languages and Automata course:

Model	Meaning	Detected when
DFA	Deterministic finite automaton	every (state, symbol) pair has exactly one target and there are no ε-moves
NFA	Nondeterministic finite automaton	at least one (state, symbol) pair has several targets
ε-NFA	NFA with epsilon transitions	at least one transition is labelled e

You never declare the type yourself — the engine inspects the transition function and picks the right simulation strategy automatically.

Features

• Automatic classification of the input automaton as DFA, NFA or ε-NFA.
• Subset-construction simulation on the fly — an NFA is run by tracking the whole set of simultaneously active states, so no explicit determinisation step is needed.
• Epsilon-closure support for ε-NFAs, computed with an iterative depth-first search.
• Verbose trace mode that shows every fork and every ε-expansion step by step.
• Interactive REPL for testing strings by hand after the built-in test batch runs.
• Zero dependencies — the Python 3 standard library is all you need.

Quick start

git clone https://github.com/edwarderzegovina/finite-automata-simulator.git
cd finite-automata-simulator
python3 DFAapp.py

The program loads input3.txt, prints the parsed automaton, runs a batch of built-in test strings and then drops you into interactive mode.

To run a different definition, either edit input3.txt or change the filename in DFAapp.py:

parser.load_from_file('input2.txt')

Interactive commands

Input	Effect
0101	Test the string and print ACCEPTED / REJECTED.
0101!	Test with a verbose trace (NFA / ε-NFA only).
(empty line)	Test the empty string ε.
quit	Exit.

Example session

Using the bundled input3.txt, which recognises every binary string ending in 01:

==================================================
Automaton Type: ε-NFA
Alphabet: {'0', '1', 'e'}
States: {'q0', 'start', 'q2', 'q1'}
Initial State: q0
Final States: {'q2'}
Transitions:
  δ(q0, 0) = q0
  δ(q0, 0) = q1
  δ(q0, 1) = q0
  δ(q1, 1) = q2
  δ(start, ε) = q0
==================================================

Testing strings:
  '0'    -> ✗ REJECTED (Final states: {'q0', 'q1'})
  '01'   -> ✓ ACCEPTED (Final states: {'q0', 'q2'})
  '10'   -> ✗ REJECTED (Final states: {'q0', 'q1'})
  '0101' -> ✓ ACCEPTED (Final states: {'q0', 'q2'})

And the same string with the verbose trace enabled (0101!):

==================================================
NFA Processing (with forking): '0101'
==================================================
Initial: {'q0'} (after ε-closure)
  Step 1 [FORK]: From q0 --0--> ['q0', 'q1'] (created 2 branches)
  Active states: {'q0', 'q1'} (running 2 parallel instances)
  Step 2: From q0 --1--> q0
  Step 2: From q1 --1--> q2
  Active states: {'q0', 'q2'} (running 2 parallel instances)
  Step 3 [FORK]: From q0 --0--> ['q0', 'q1'] (created 2 branches)
  Active states: {'q0', 'q1'} (running 2 parallel instances)
  Step 4: From q0 --1--> q0
  Step 4: From q1 --1--> q2
  Active states: {'q0', 'q2'} (running 2 parallel instances)

Final states: {'q0', 'q2'}
✓ ACCEPTED (found accepting state(s): {'q2'})
==================================================

Drawn as a state diagram, that automaton is:

stateDiagram-v2
    direction LR
    [*] --> q0
    q0 --> q0: 0, 1
    q0 --> q1: 0
    q1 --> q2: 1
    q2 --> [*]

Loading

Input file format

A definition file is a sequence of sections. Each section opens with a name followed by :, contains a single line of data, and closes with End. Blank lines are ignored and section names are case-insensitive.

Sigma:
{0, 1, e}
End

States:
{start, q0, q1, q2}
End

Finale:
{q2}
End

Trans:
{(start, e, q0),(q0, 0, q0),(q0, 1, q0),(q0, 0, q1),(q1, 1, q2)}
End

Sections

Section	Required	Contents
Sigma	✔	The input alphabet Σ, as a set: {0, 1}.
States	✔	The set of states Q: {q0, q1, q2}.
Finale	✔	The set of accepting states F ⊆ Q: {q2}.
Trans	✔	The transition function δ, as a set of triples (from, symbol, to).

Transitions

Each transition is a 3-tuple (source, symbol, target). Whitespace around the components is ignored, so (q0, 0, q1) and (q0,0,q1) are equivalent.

Listing the same (source, symbol) pair more than once is exactly how nondeterminism is expressed — (q0, 0, q0) together with (q0, 0, q1) makes the machine fork on 0.

Epsilon transitions

The letter e denotes ε. Add it to Sigma and use it as the symbol of a transition:

{(start, e, q0)}

Note that ε is a label, not a real input symbol — the simulator handles ε-edges through the epsilon-closure and never consumes a character for them.

Important

The initial state is not declared explicitly. It is inferred as the lexicographically smallest state name in States. Name your entry state so that it sorts first — q0 is the safe convention.

This is why, in input3.txt, the state literally named start is not the entry point: 'q0' < 'start' in string order, so q0 is chosen and the (start, e, q0) edge is never taken. The language recognised is the same either way.

Included examples

File	Type	Language recognised
input.txt	DFA	ε, or any binary string ending in 1.
input2.txt	NFA	Binary strings whose third symbol from the end is 1.
input3.txt	ε-NFA	Binary strings ending in 01.

How it works

The code is split into three single-responsibility modules:

DFAapp.py  ──▶  TextParser.py  ──▶  Automaton.py
  (CLI)          (parsing)           (simulation)

TextParser reads the definition file into a dictionary of sections, validates that the required ones are present, and converts the {...} set notation and (...) tuple notation into native Python set and list objects. Transition parsing tracks parenthesis depth so that the commas inside a tuple are not confused with the commas separating tuples.

Automaton stores δ as a dictionary mapping (state, symbol) to a list of targets — a list rather than a single value, which is what makes nondeterminism representable at all. On construction it classifies itself and then simulates accordingly:

• DFA path — walk a single current state through the string. Rejects early with a diagnostic if a symbol is outside Σ or no transition is defined.
• NFA path — maintain a set of active states. For each input symbol, take the union of the targets of every active state, then apply the epsilon-closure to the result. The string is accepted if the final set intersects F.
• epsilon_closure — an iterative DFS over ε-edges using an explicit stack, so deeply chained ε-transitions cannot overflow the call stack.

Because the active-state set is bounded by |Q|, simulating an NFA costs O(|w| · |Q|²) in the worst case, without ever materialising the exponentially large equivalent DFA.

Project structure

.
├── Automaton.py    # Classification + DFA/NFA/ε-NFA simulation
├── TextParser.py   # Definition-file parsing and validation
├── DFAapp.py       # Entry point: batch tests + interactive REPL
├── input.txt       # Example: DFA
├── input2.txt      # Example: NFA
└── input3.txt      # Example: ε-NFA (loaded by default)

Known limitations

• The initial state is inferred by sorting rather than declared (see the note above).
• The definition file is read from a filename hard-coded in DFAapp.py; there is no CLI argument for it yet.
• Only one automaton per file is supported.

Related

A companion project extending the same architecture to push-down automata lives at pda-simulator.

License

Released under the MIT License.