EntCSExplore. Visualise. Understand.

Everything on the site.

Big-O notationAlgorithms · Count the steps in real loops, then compare n, n log n, n² and 2ⁿ on a live chart.RecursionAlgorithms · Watch frames push and pop on the call stack for factorial and Fibonacci.BFS vs DFSAlgorithms · A queue against a stack: draw a graph and see which order each search visits it in.Sorting algorithmsAlgorithms · Seven sorts on the same input, with comparison, swap and write counts side by side.Binary searchAlgorithms · Halve the range, probe the middle, repeat: with lo, mid and hi drawn on the array.Sets, relations and functionsDiscrete maths · Shade any set expression on a Venn diagram and test a relation for its properties.Proof by inductionDiscrete maths · Four worked proofs revealed one step at a time, and a broken one to diagnose.CombinatoricsDiscrete maths · An exact nPr and nCr calculator, and a Pascal’s triangle that shows its own addition rule.Boolean algebraDiscrete maths · The laws, De Morgan, and normal forms, with a truth-table generator built in.Finite-state machinesTheory · Build a DFA in a table, see it drawn, and run strings through it one symbol at a time.Domain theoryTheory · Why recursion needs least fixed points, and how CPOs, Scott continuity and powerdomains supply them.Truth table generatorTools · Expression in, truth table out: with DNF, CNF, a minimal form and LaTeX.Graph traversal visualiserTools · Draw a graph, then animate BFS, DFS and Dijkstra with the frontier shown.Recursion tree visualiserTools · Paste a recursive function or a recurrence and see its call tree and call count.Gradient descentML maths · Drag the starting point, set the learning rate, and watch it converge or blow up.Vectors and embeddingsML maths · Bend the plane with a 2×2 matrix and measure how close toy word vectors are.Softmax and cross-entropyML maths · Edit the logits and watch the probabilities, the loss and the gradient update live.Attention mechanismML maths · Q, K and V for three tokens, a live score heatmap, and the weighted sum of values.Formatting a CS paper in LaTeXLaTeX · Page limits, \documentclass, front matter, theorem environments and the bibliography.Camera-ready checklistLaTeX · Fonts embedded, PDF/A, copyright form, source bundle, and why final versions get rejected.LaTeX templatesLaTeX · Where the official classes live, plus a minimal article template you can copy.Boolean algebra calculatorTools · A Boolean expression simplifier that names the law used at every step.K-map solverTools · Fill in a Karnaugh map and see the groups, the minimal SOP and POS, and the essential terms.Logic gate simulatorTools · Wire up gates, flip the switches, and get the truth table and expression of your circuit.Regex to NFA converterTools · Type a regular expression and watch Thompson’s construction build its NFA, fragment by fragment.NFA to DFA converterTools · Enter an NFA or a regex and step through the subset construction, then minimise the DFA.DFA simulatorTools · Edit a DFA, run strings through it step by step, batch-test them and share the machine as a link.Regular expressions to automataTheory · Regex to NFA to DFA to minimal DFA, worked through on one example with every set shown.The halting problemTheory · Why no program can tell whether every program halts, with the paradox program played out.Pigeonhole principleDiscrete maths · n pigeons, k holes: why some hole gets ⌈n/k⌉, and the surprising things that follows from it.Dijkstra’s algorithmAlgorithms · Shortest paths with a priority queue: a worked table, a proof, and a graph you can redraw.Hash functionsAlgorithms · Keys in, buckets out: hash a word four ways, then watch chaining and probing handle collisions.Sorting algorithm visualizerTools · Up to seven sorts race on the same data, then step through any one of them line by line.LaTeX table generatorTools · Type or paste a table, merge cells, pick booktabs, and copy clean tabular code.Combination calculatorTools · Exact nCr with the cancelling shown, combinations with repetition, and a full list for small n.Permutation calculatorTools · nPr, nʳ, anagrams like MISSISSIPPI and round-table seatings, with exact working.AlgorithmsSection · Step-through visualisations of sorting, searching, recursion, graph traversal, Dijkstra’s algorithm, hash functions and Big-O growth, with pseudocode that follows along.Discrete mathsSection · Sets, relations and functions, proof by induction, counting, the pigeonhole principle and Boolean algebra, explained with worked examples and interactive checkers.TheorySection · Finite-state machines, regular expressions and automata, the halting problem, and the mathematical semantics of programming languages, explained from first principles.ML mathsSection · Gradient descent, vectors and embeddings, softmax and cross-entropy, and attention, each with a formula, a worked numeric example and a live version.ToolsSection · Free browser tools: truth tables, Boolean simplification, K-maps, logic gates, nCr and nPr, regex to NFA to DFA, sorting and graph visualisers, and LaTeX tables.LaTeXSection · How to format a CS conference or workshop paper in LaTeX, a camera-ready checklist, and a minimal template you can adapt.
Free tool

NFA to DFA converter: subset construction with steps

Convert a nondeterministic finite automaton into an equivalent deterministic one with the subset construction. Enter an NFA as a list of transitions, or a regular expression that is first turned into an NFA, then step through every ε-closure and every entry of the subset table. Tick “Minimise” to reduce the result to the smallest equivalent DFA.

Interactive: Subset-construction stepper with ε-closures and DFA minimisationUpdated

NFA to DFA converterThe subset construction, one transition at a time.

NFA

DFA being built

Pseudocode

  1. A ← ε-closure({start}); mark A as unprocessed
  2. while some DFA state T is unprocessed:
  3. for each symbol c:
  4. U ← ε-closure(move(T, c))
  5. if U is empty: no transition (dead state)
  6. else if U is new: name it and add it, unprocessed
  7. δ(T, c) ← U
  8. accepting DFA states: those containing an accepting NFA state

This step

Result

Open the DFA in the simulator

Entering an NFA

Choose From an NFA table and write one transition per line as from symbol to. State names can be any words without spaces (q0, start, s1); symbols are single characters. Write eps, ε or - as the symbol for an ε-transition. One line start q0 names the start state and one line accept q2 q3 lists the accepting states. Anything after # is a comment. Nondeterminism is written by giving several lines with the same state and symbol, as in q0 1 q0 and q0 1 q1.

With From a regex, the expression is turned into an NFA by Thompson’s construction first (see the regex to NFA converter to step through that part), and the subset construction runs on the result.

How the subset construction works

An NFA can be in several states at once. The idea, due to Rabin and Scott, is to let one DFA state stand for the whole set of NFA states the NFA could be in. Two operations do all the work:

  • ε-closure(S)\varepsilon\text{-closure}(S): every state reachable from a state in SS using only ε-transitions, including the states of SS itself.
  • move(S,c)\text{move}(S, c): every state reachable from a state in SS by one transition on the symbol cc.

The DFA’s start state is the ε-closure of the NFA’s start state. Then, for each DFA state TT not yet processed and each symbol cc, compute U=ε-closure(move(T,c))U = \varepsilon\text{-closure}(\text{move}(T, c)). If UU is a set we have not seen, it becomes a new DFA state. Either way, δ(T,c)=U\delta(T, c) = U. The construction stops when every DFA state has been processed, and a DFA state is accepting when its set contains at least one accepting NFA state.

If UU is empty, no NFA state can read cc, and the DFA moves to a dead state ∅\varnothing that rejects everything. The converter leaves the dead state out of the diagram and shows it as ∅ in the table, as the DFA simulator does.

Worked example: the second-last symbol is 1

The NFA preloaded under “From an NFA table” guesses, at some 1, that this is the second-last symbol: from q0 on 1 it may go to q1, then any symbol takes it to the accepting state q2. The subset construction gives 4 DFA states:

DFA stateNFA stateson 0on 1
→A{q0}AB
B{q0, q1}CD
*C{q0, q2}AB
*D{q0, q1, q2}CD

Each DFA state remembers the last two symbols read: that is exactly the information the NFA was guessing about. The accepting states (marked *) are the sets containing q2.

The exponential blow-up

A set of nn NFA states has 2n2^n subsets, so the DFA can be exponentially larger than the NFA. The construction only creates the subsets that are actually reachable, which is usually far fewer, but some languages really do need them all. “The kk-th symbol from the end is 1” has an NFA with k+1k + 1 states, while any DFA for it must remember the last kk symbols, which takes 2k2^k states:

kNFA statesDFA states (subset construction)after minimisation
2344
3488
451616
563232

Minimisation does not help here: these DFAs are already minimal. That is the price of determinism, and it is why practical regex engines often simulate the NFA directly, or build DFA states lazily only as the input needs them.

Minimising the DFA

The subset construction rarely gives the smallest DFA. For (a|b)*abb it produces 5 states, and minimisation merges two of them, leaving 4. The converter uses Moore’s partition refinement:

  1. Make the DFA complete by adding a dead state for missing transitions, and drop states unreachable from the start.
  2. Split the states into two groups: accepting and non-accepting.
  3. Two states stay in the same group only if, on every symbol, they move into the same group. Split any group that breaks this, and repeat until nothing changes.
  4. Each final group becomes one state of the minimal DFA.

The minimal DFA is unique up to renaming states (the Myhill–Nerode theorem), so two regular expressions describe the same language exactly when their minimal DFAs are the same machine. That gives a mechanical way to check whether a simplified regex is still correct.

Limits The NFA may have up to 30 states (80 when built from a regex) and the DFA up to 40. Those limits keep the diagrams readable; the step-through table is the clearest view of larger conversions.

Background

The full story, from Kleene’s theorem to minimal DFAs, is in from regular expressions to automata. If DFAs are new to you, start with finite-state machines.

References

  1. M. O. Rabin and D. Scott, “Finite automata and their decision problems”, IBM Journal of Research and Development 3(2), 1959. doi:10.1147/rd.32.0114
  2. E. F. Moore, “Gedanken-experiments on sequential machines”, in Automata Studies, Princeton University Press, 1956.
  3. J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006. Sections 2.3 and 4.4.