CS374: Principles of Programming Languages - Finite Automata Simulator (100 Points)

Purpose, Task, and Criteria

Purpose: To implement general DFA and NFA simulators driven by machine definitions loaded as data, design automata for specified languages, and carry out the subset and Thompson's constructions by hand — the execution model beneath every lexer.

Task: Build DFA and NFA simulators that read machines from JSON, design a portfolio of machines, then hand-execute the subset construction and Thompson's construction and verify each by simulation.

Criteria: Assessed on correct simulators that handle the deliberate edge cases, annotated machine designs, and hand constructions verified by simulation rather than inspection, each part worth 25 points; see the rubric below for the full breakdown.

Assignment Goals

The goals of this assignment are:
  1. To implement general DFA and NFA simulators over machine definitions loaded from JSON
  2. To design automata for specified languages and encode them as data
  3. To demonstrate the subset construction by hand and verify it by simulation
  4. To apply Thompson's construction to convert a regular expression to an NFA
  5. To connect automata to the regular expressions and lexer of the surrounding course

Background Reading and References

Please refer to the following readings and examples offering templates to help get you started:

The Assignment

In this assignment you will build the machines beneath your lexer: general simulators for DFAs and NFAs that read machine definitions as data, plus a design portfolio of machines you create, a hand-executed subset construction, and a Thompson’s construction NFA. Build in the small scaffolded steps below; each step has its own tests. The point is not just that the code works — it is that you understand why it works, which the design portfolio and writeup capture.

Getting Started

Environment and Setup

You need Python 3.10+ and the standard library only (json for machine files, argparse if you like for the CLI). Create the layout from the Deliverables section up front:

simulator.py       # loader, run_dfa, run_nfa, CLI
machines/          # one JSON file per machine
tests/             # test runner and output logs
writeup.md         # construction tables and reflection

Your First 30 Minutes

Do not start with the simulator — start with a machine. Copy the two-state parity machine JSON from Part 1 into machines/even_ones.json, then write the smallest possible run_dfa:

import json, sys

machine = json.load(open("machines/even_ones.json"))
state = machine["start"]
for symbol in sys.argv[1]:
    state = machine["delta"][state][symbol]
print("accept" if state in machine["accept"] else "reject")

Run python simulator.py 0110 (accept) and python simulator.py 101 (reject), matching the traces shown in Part 1. Once this ten-line core works, Steps 1a and 1b are a matter of wrapping it in validation, error handling, and --trace — you already know the heart of it is right.

Suggested Pacing

This assignment is handed out on Tuesday of week 4 and due on Tuesday of week 5 — a one-week turnaround, so start the day it is assigned:

Checkpoint You should have
Week 4 (Tue) — assigned Loader/validator and DFA simulator working (Steps 1a–1b); DFA 1 designed
Week 4 (Thu) Part 1 portfolio complete; epsilon-closure and NFA simulator working (Steps 2a–2b)
Weekend Part 2 portfolio complete; Part 3 subset construction table and verified DFA
Week 5 (Tue) — due Part 4 Thompson’s construction verified; writeup assembled and submitted

Part 1: DFA Design and Simulation (25 points)

Machine Format

All machines are JSON files with the following keys:

Key Type Meaning
states list of strings all state names
alphabet list of strings all input symbols (each a single character)
start string the initial state
accept list of strings the accepting states
delta object transition function

For DFAs, delta is a nested object: delta[state][symbol] gives the next state. Every (state, symbol) pair in the alphabet must appear.

Example — the two-state parity machine for “even number of 1s”:

{
  "states": ["even", "odd"],
  "alphabet": ["0", "1"],
  "start": "even",
  "accept": ["even"],
  "delta": {
    "even": {"0": "even", "1": "odd"},
    "odd":  {"0": "odd",  "1": "even"}
  }
}

Trace on "0110": even → even → odd → even → even. Accepts. ✓
Trace on "101": even → odd → even → odd. Rejects. ✓

Step 1a: Loader and Validator

Write load_machine(path) that reads a JSON file and validates:

  • The start state appears in states.
  • Every accept state appears in states.
  • For a DFA, every (state, symbol) pair defined in delta references only declared states and alphabet symbols.
  • Collect all validation errors (not just the first) and raise a single MachineError listing them.

Step 1b: DFA Simulator

Implement run_dfa(machine, s) -> bool. Rules:

  • Any symbol in s that is not in the machine’s alphabet is an immediate reject; print a reason (do not crash).
  • The empty string "" is valid input; it tests whether the start state is an accept state.
  • With flag --trace, print the current state after processing each symbol.

Step 1c: DFA Design Portfolio

Design, encode as JSON, annotate each state with one sentence explaining what it “remembers,” and test each machine below with at least four accepted strings and four rejected strings:

DFA 1 — Even ones: strings over {0, 1} containing an even number of 1s (include 0 ones as even).
Worked example: "0110" → 2 ones (even) → accept; "111" → 3 ones (odd) → reject.

DFA 2 — Ends in ab: strings over {a, b} that end with the suffix ab.
Worked example: "aab" → accept; "ba" → reject; "ab" → accept; "" → reject.
Hint: you need at least three states — track what suffix of ab has been seen most recently.

DFA 3 — Binary divisible by 3: strings over {0, 1} (big-endian binary) whose numeric value is divisible by 3. Include the empty string (value 0, divisible) and "0".
Worked example: "110" = 6 → accept; "111" = 7 → reject; "0" = 0 → accept.
Hint: three states, each representing the current remainder mod 3.

Part 2: NFA Design and Simulation (25 points)

NFA Machine Format

For NFAs, delta maps "state,symbol" string keys to lists of states. The special symbol "eps" denotes an epsilon (ε) transition. A state may have zero or more targets for any symbol.

Example fragment:

"delta": {
  "q0,a": ["q0", "q1"],
  "q0,eps": ["q2"],
  "q1,b": ["q2"]
}

Step 2a: Epsilon-Closure

Implement eps_closure(machine, states) -> frozenset. This is a small graph reachability computation:

  • Start with the given set of states.
  • Repeatedly follow "eps" transitions until no new states are discovered.
  • Handle cycles (a state may epsilon-transition back to itself or to a predecessor).

Example: If q0 -ε→ q1, q1 -ε→ q2, and q2 -ε→ q0, then eps_closure(m, {"q0"}) = {"q0", "q1", "q2"}.

Step 2b: NFA Simulator

Implement run_nfa(machine, s) -> bool:

  1. Compute the epsilon-closure of {start} as the initial set of active states.
  2. For each symbol in s, compute the union of all delta["state,symbol"] lists over all active states, then take the epsilon-closure of that union.
  3. Accept if the final active set intersects the accept set.

Step 2c: NFA Design Portfolio

Design, encode, and test each NFA below with at least four accepted and four rejected strings:

NFA 1 — Ends in ab: the same language as DFA 2, but designed as an NFA. Use nondeterminism to “guess” where the suffix begins (fewer states, ε-free version possible with 3 states).

NFA 2 — Contains aa: strings over {a, b} containing the substring aa somewhere.
Worked example: "baaab" → accept; "ababab" → reject.
Hint: nondeterministically guess where aa occurs.

NFA 3 — Third-from-last is a: strings over {a, b} whose third-from-last symbol is a.
Worked example: "aab" → the 3rd-from-last of "aab" is a → accept; "bab" → 3rd-from-last is b → reject.
Hint: with NFA, guess nondeterministically where the last three symbols begin — the machine needs only 4 states.

Part 3: Subset Construction — NFA to DFA (25 points)

Apply the subset construction to NFA 3 (third-from-last is a) to produce an equivalent DFA.

Step 3a: Hand Construction (in your writeup)

Draw the construction table with these columns:

Powerset State on a on b Accepting?
{q0} … … No/Yes
…      

Rules:

  • Start with eps_closure({q0_nfa}).
  • For each unmarked powerset state, compute its transitions and epsilon-close the results.
  • Mark a powerset state as accepting if it contains any NFA accept state.
  • Continue until no unmarked states remain.

Document how many DFA states result, and whether any are unreachable.

Step 3b: Encode and Verify

Encode the resulting DFA as JSON. Run both the original NFA and the new DFA over the same test suite (all eight strings from Part 2, NFA 3). They must agree on every string — acceptance and rejection. Report any disagreement as a bug.

Part 4: Thompson’s Construction for a Regex (25 points)

Apply Thompson’s construction to the regular expression a(b|c)*d.

Background

Thompson’s construction builds an NFA by composing small fragments:

  • Single character x: one start state → one accept state, labeled x.
  • Concatenation AB: connect the accept state of fragment A to the start of fragment B with ε.
  • Union A|B: new start with ε-transitions to both A and B; both A and B’s accept states ε-transition to a new shared accept.
  • Kleene star A*: new start with ε to A’s start and to a new accept; A’s accept ε-transitions back to A’s start and also to the new accept.

Step 4a: Construction Steps (in your writeup)

Show each sub-expression and its fragment:

  1. Fragment for a.
  2. Fragment for b.
  3. Fragment for c.
  4. Fragment for b|c (union of 2 and 3).
  5. Fragment for (b|c)* (Kleene star of 4).
  6. Fragment for d.
  7. Concatenation: a then (b|c)* then d.

Label every state (e.g., q0 through q_n) and every ε-transition.

Step 4b: Encode and Verify

Encode the final NFA as JSON. Test it on:

  • "ad" → accept
  • "abd" → accept
  • "abcd" → accept
  • "abbbcd" → accept
  • "a" → reject (no d)
  • "bd" → reject (no leading a)
  • "acd" → accept
  • "" → reject

Deliverables

Submit a ZIP containing:

  • simulator.py — the loader, DFA simulator, and NFA simulator with CLI entry point
  • machines/ — all JSON machine files (3 DFAs, 3 NFAs, 1 subset-construction DFA, 1 Thompson’s NFA)
  • tests/ — test runner and output logs showing all test results
  • writeup.md — approximately one page covering: the subset-construction table, Thompson’s construction step-by-step, and a paragraph connecting these simulators to the lexer you will build next (which component of the lexer plays the role of your simulators?)

Ensure reproducibility by listing Python version. Run python simulator.py --help to confirm the CLI is documented.

Grading Breakdown

Component Points
Part 1: DFA Design and Simulation 25
Part 2: NFA Design and Simulation 25
Part 3: Subset Construction 25
Part 4: Thompson’s Construction and Writeup 25
Total 100

Reflection Prompts

  • For NFA 3, contrast designing the NFA with designing its equivalent DFA via subset construction: where did the complexity move?
  • Your simulators treat machines as data (loaded from JSON). Name one benefit this brought during testing that hard-coded machines would have denied you.
  • After completing Thompson’s construction, describe one way the resulting NFA differs structurally from the hand-designed NFAs in Part 2.
  • If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work? Please identify any and all portions of your submission that were not originally written by you.
  • Approximately how many hours it took you to finish this assignment (I will not judge you for this at all — I am simply using it to gauge if the assignments are too easy or hard)?

Submission

In your submission, please include answers to any questions asked on the assignment page, as well as the questions listed below, in your README file. If you wrote code as part of this assignment, please describe your design, approach, and implementation in a separate document prepared using a word processor or typesetting program such as LaTeX. This document should include specific instructions on how to build and run your code, and a description of each code module or function that you created suitable for re-use by a colleague. In your README, please include answers to the following questions:
  • Describe what you did, how you did it, what challenges you encountered, and how you solved them.
  • Please answer any questions found throughout the narrative of this assignment.
  • If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
  • Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
  • Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
  • Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
  • Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
  • Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).

Assignment Rubric

Description Pre-Emerging (< 50%) Beginning (50%) Progressing (85%) Proficient (100%)
DFA Design and Simulation (Goals 1, 2) (25%) The DFA simulator fails to run or fails most provided machines due to major structural errors The DFA simulator runs but fails on several test cases due to minor issues such as incorrect transition lookups or missing alphabet validation The DFA simulator passes the provided test cases but mishandles edge cases such as the empty string, symbols outside the alphabet, or trap states A correct DFA simulator passes all provided and hidden test cases, handles the empty string and out-of-alphabet symbols deliberately, supports trace mode, and runs all three required DFA designs with documented state meanings
NFA Design and Simulation (Goals 1, 2) (25%) The NFA simulator is missing or fails to compute epsilon-closures correctly The NFA simulator runs but produces incorrect results on several machines due to epsilon-closure errors or incorrect powerset tracking The NFA simulator passes the provided test cases but would fail on machines with epsilon cycles or machines that require epsilon closure at the final step A correct NFA simulator correctly computes epsilon-closures with cycle detection, tracks the powerset of states, and passes all provided and hidden test cases including all three required NFA designs with traced execution paths
Subset Construction (Goals 2, 3) (25%) The subset construction is not attempted or the resulting DFA is fundamentally incorrect The subset construction table is partially complete but the encoded DFA diverges from the NFA on several test strings The subset construction table is complete and the DFA is correctly encoded, but simulation agreement with the NFA is only verified on a few strings The subset construction is carried out fully by hand with every powerset state documented, the resulting DFA is encoded as JSON, and simulation agreement with the original NFA is verified programmatically across the full test suite
Thompson's Construction and Writeup (Goals 4, 5) (25%) Thompson's construction is not attempted or produces a machine that accepts clearly wrong strings Thompson's construction produces a machine for simple cases but fails on concatenation or union of sub-expressions Thompson's construction produces a correct NFA for the given regex and is verified by simulation, with limited explanation of the construction steps Thompson's construction is applied step-by-step with each fragment labeled, the final NFA is encoded as JSON, verified by simulation, and the writeup connects automata theory to the lexer pipeline with thoughtful reflection

Please refer to the Style Guide for code quality examples and guidelines.