This repository contains an application called AutomataSim built for the final group project of Cpts 322 (Software Engineering Principles) at Washington State University.
AutomataSim is a graphical application for visualizing and simulating various types of finite automata:
- DFA (Deterministic Finite Automaton)
- NFA (Non-deterministic Finite Automaton)
- ε-NFA (Epsilon-NFA with epsilon transitions)
It features a custom domain-specific language (DSL) for defining automata in an intuitive format. Automata can be simulated on input strings, converted between types, and persisted to a database.
The DSL now supports multiple automata types with this syntax:
<type> <name> {
states = {s1, s2, ..., sn};
alphabet = {a1, a2, ..., am};
transitions = {
(s, a) -> s'; // For DFA
(s, a) -> {s1, s2}; // For NFA
(s, ε) -> {s1, s2}; // For ε-NFA
};
start = s;
accept = {s1, s2, ..., sk};
}
Where <type> is one of: dfa, nfa, epsilon-nfa
The original syntax is still supported for backward compatibility:
automaton <name> {
states = {<s>, <s>, ..., <s>};
alphabet = {<a>, <a>, ..., <a>};
transition_func = {
(<s>, <a>): <s>,
...
(<s>, <a>): <s>
};
start_state = <s>;
accept_states = {<s>, <s>, ..., <s>};
}
The syntax of inputted automata will be checked to ensure that the fields entered are valid finite automata.
dfa EvenOnes {
states = {even, odd};
alphabet = {0, 1};
transitions = {
(even, 0) -> even;
(even, 1) -> odd;
(odd, 0) -> odd;
(odd, 1) -> even;
};
start = even;
accept = {even};
}
nfa Contains_101 {
states = {q0, q1, q2, q3};
alphabet = {0, 1};
transitions = {
(q0, 0) -> {q0};
(q0, 1) -> {q0, q1};
(q1, 0) -> {q2};
(q2, 1) -> {q3};
};
start = q0;
accept = {q3};
}
This automata description,
automaton finite_automata {
states = {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12};
alphabet = {0, 1};
transition_func = {
(q0, 0): q1, (q0, 1): q2,
(q1, 0): q3, (q1, 1): q4,
(q2, 0): q5, (q2, 1): q6,
(q3, 0): q7, (q3, 1): q8,
(q4, 0): q9, (q4, 1): q10,
(q5, 0): q11, (q5, 1): q12,
(q6, 0): q0, (q6, 1): q1,
(q7, 0): q2, (q7, 1): q3,
(q8, 0): q4, (q8, 1): q5,
(q9, 0): q6, (q9, 1): q7,
(q10, 0): q8, (q10, 1): q9,
(q11, 0): q10,(q11, 1): q11,
(q12, 0): q12,(q12, 1): q0
};
start_state = q0;
accept_states = {q3, q7, q11};
}
will be visualized as:
-
Run the application:
./run.sh
-
Define your automaton using the DSL syntax in the text editor
-
Click "Visualize" to see the graphical representation
-
The visualization will show:
- States as circles (double circles for accepting states)
- Transitions as labeled arrows
- Start state with an incoming arrow
- For NFA/ε-NFA: Multiple transitions shown as comma-separated labels
dfa BinaryDivisibleBy3 {
states = {q0, q1, q2};
alphabet = {0, 1};
transitions = {
(q0, 0) -> q0;
(q0, 1) -> q1;
(q1, 0) -> q2;
(q1, 1) -> q0;
(q2, 0) -> q1;
(q2, 1) -> q2;
};
start = q0;
accept = {q0};
}
nfa MultipleOf3Or5 {
states = {start, mod3_0, mod3_1, mod3_2, mod5_0, mod5_1, mod5_2, mod5_3, mod5_4};
alphabet = {0, 1};
transitions = {
(start, ε) -> {mod3_0, mod5_0}; // Branch to check both conditions
// Mod 3 checker
(mod3_0, 0) -> {mod3_0};
(mod3_0, 1) -> {mod3_1};
(mod3_1, 0) -> {mod3_2};
(mod3_1, 1) -> {mod3_0};
(mod3_2, 0) -> {mod3_1};
(mod3_2, 1) -> {mod3_2};
// Mod 5 checker
(mod5_0, 0) -> {mod5_0};
(mod5_0, 1) -> {mod5_1};
(mod5_1, 0) -> {mod5_2};
(mod5_1, 1) -> {mod5_3};
(mod5_2, 0) -> {mod5_4};
(mod5_2, 1) -> {mod5_0};
(mod5_3, 0) -> {mod5_1};
(mod5_3, 1) -> {mod5_2};
(mod5_4, 0) -> {mod5_3};
(mod5_4, 1) -> {mod5_4};
};
start = start;
accept = {mod3_0, mod5_0};
}
epsilon-nfa OptionalPrefix {
states = {q0, q1, q2, q3, q4};
alphabet = {a, b};
transitions = {
(q0, ε) -> {q1, q3}; // Skip prefix or process it
(q1, a) -> {q2};
(q2, b) -> {q3};
(q3, a) -> {q3};
(q3, b) -> {q4};
};
start = q0;
accept = {q4};
}
turing-machine BinaryIncrement {
states = {scan_right, increment, halt, overflow};
input_alphabet = {0, 1};
tape_alphabet = {0, 1, _};
transitions = {
(scan_right, 0) -> (scan_right, 0, R);
(scan_right, 1) -> (scan_right, 1, R);
(scan_right, _) -> (increment, _, L);
(increment, 0) -> (halt, 1, S);
(increment, 1) -> (increment, 0, L);
(increment, _) -> (overflow, 1, S);
};
start = scan_right;
accept = halt;
reject = overflow;
}
- Automatic Layout: Automata are automatically laid out using Graphviz for optimal readability
- State Highlighting: Current states are highlighted during simulation
- Transition Labels: All transitions are clearly labeled with input symbols
- Epsilon Transitions: Shown as ε or ε-labeled arrows in ε-NFAs
- Tape Visualization: For Turing Machines, the tape and head position are shown
- Export Options: Save visualizations as PNG or PDF files
The application can automatically convert between compatible automata types:
- ε-NFA → NFA: Removes epsilon transitions
- NFA → DFA: Uses subset construction algorithm
- ε-NFA → DFA: Combines both conversions
To convert, load an automaton and use the "Convert" menu option.
64d008b (Update README with visualization instructions for different automata types)
From the root directory, run on a linux terminal:
./run.sh