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

Regex to NFA converter: Thompson’s construction step by step

Type a regular expression and this converter builds the equivalent nondeterministic finite automaton (NFA) with Thompson’s construction. Step through it one sub-expression at a time, read off the transition table, then run strings through the finished NFA to see which states are live after every symbol.

Interactive: Thompson-construction stepper and NFA string testerUpdated

Regex to NFA converterThompson’s construction, one sub-expression at a time.

Examples:

States are numbered in the order they are created. Orange: the fragment just built. ε-transitions consume no input.

Pseudocode

  1. for each sub-expression, innermost first:
  2. symbol c: new s, f; s –c→ f
  3. ε: new s, f; s –ε→ f
  4. RS: accept(R) –ε→ start(S)
  5. R|S: new s, f; s –ε→ start(R), start(S); accept(R), accept(S) –ε→ f
  6. R*: new s, f; s –ε→ start(R), f; accept(R) –ε→ start(R), f
  7. R+: as R*, but without the s –ε→ f skip
  8. R?: new s, f; s –ε→ start(R), f; accept(R) –ε→ f
  9. the last fragment’s s and f are the start and accepting state

Result

Test many strings

Convert this NFA to a DFA

Transition table

How to write the expression

The converter understands the operators of formal language theory, which are a small core of the regular expressions in programming languages.

WriteMeaningExample
abconcatenation: a then babb matches only abb
a|bunion (alternation): a or bcat|dog
a*Kleene star: zero or more a(ab)* matches ε, ab, abab, …
a+one or more a0+ matches 0, 00, 000, …
a?optional: zero or one acolou?r
( )grouping(a|b)*abb
εthe empty string(a|ε)b is the same as a?b
\*, \|, …a literal special charactera\+b matches a+b

Precedence runs from tightest to loosest: the postfix operators *, + and ?, then concatenation, then |. So ab|c* means (ab)∣(c∗)(ab) \mid (c^*). Every other character is a literal symbol of the alphabet, and spaces are ignored. An empty alternative stands for ε, so a| matches a or the empty string. Character classes such as [a-z], anchors and back-references are not part of the theory and are not supported; write (a|b|c) instead of [abc].

Thompson’s construction in five rules

Ken Thompson described this construction in 1968 for a text editor’s search command. It builds the NFA bottom-up, one small fragment per sub-expression. Each fragment has exactly one start state and one accepting state, and nothing ever leaves its accepting state, so fragments can be plugged together like pieces of track.

  1. A symbol cc becomes two states joined by one cc-transition.
  2. ε becomes two states joined by an ε-transition, which moves without reading input.
  3. Concatenation RSRS links the accepting state of RR’s fragment to the start of SS’s with an ε-transition.
  4. Union R∣SR \mid S adds a new start state with ε-transitions into both fragments, and a new accepting state that both fragments lead into.
  5. Star R∗R^* adds new start and accepting states, a back edge from the end of RR to its beginning (repeat), and a skip edge from the new start to the new end (zero times). R+R^+ drops the skip edge; R?R? drops the back edge.

Because every rule adds at most two states, an expression with mm symbols and operators gives an NFA with at most 2m2m states, and every state has at most two outgoing transitions. That linear size is why the construction is still used: the NFA is small, quick to build, and easy to simulate.

Worked example: ab|c

The parser reads this as (ab)∣c(ab) \mid c, so the construction runs innermost first: fragments for a (states 0, 1), b (2, 3), their concatenation (an ε-edge 1 → 2), the fragment for c (4, 5), and finally the union, which adds start state 6 and accepting state 7. That is 8 states and 8 transitions. Load ab|c in the converter and step through it to see exactly this order.

What the diagram shows

  • States are numbered in creation order, so the numbers tell you which sub-expression made them, as in most textbooks.
  • The layout follows the expression. Alternatives of a union are stacked, back edges of a star loop over the top of their fragment, and skip edges pass underneath.
  • In Run a string mode the highlighted states are all the states the NFA could be in after reading the input so far. An NFA accepts if any of them is accepting when the input runs out.

The default expression, (a|b)*abb (strings over a and b that end in abb), gives 14 states and 16 transitions, 11 of them ε-moves. Of the strings abb, aabb, babb, ab, abba, it accepts abb, aabb, babb.

Why some textbooks get fewer states Some presentations of Thompson’s construction merge the accepting state of RR with the start of SS when concatenating, instead of joining them with an ε-edge. That saves one state per concatenation and gives the same language. This converter keeps the ε-edge so that every rule only ever adds states and edges, which makes each step easy to follow.

From NFA to DFA

An NFA is easy to build but awkward to run directly, because it can be in many states at once. The next step in a lexer generator or regex compiler is the subset construction, which turns the NFA into a deterministic automaton whose states are sets of NFA states. The NFA to DFA converter takes the same expression and steps through it, and the DFA simulator lets you edit and test the result. The theory behind all three tools is in from regular expressions to automata.

References

  1. K. Thompson, “Programming techniques: Regular expression search algorithm”, Communications of the ACM 11(6), 1968. doi:10.1145/363347.363387
  2. A. V. Aho, M. S. Lam, R. Sethi and J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Pearson, 2006. Section 3.7.
  3. M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2012. Section 1.3.