Skip to content
Tape‑n‑Trace
PracticeSearch 26 tools

Regular expression playground

Four views of one expression, kept in step. Change the expression and the parse tree, the Thompson ε-NFA, the minimal DFA and the list of accepted strings all move together — which is the quickest way to see what a change to the expression actually did.

Try:

Union is + or |, star is *. Star binds tightest, then concatenation, then union — so 01* is 0(1*), not (01)*.

Parse tree

How the expression is read — this is the precedence, drawn.

·(0+1)*01·(0+1)*0*(0+1)*+0+100110011

Thompson ε-NFA

12 states, 14 transitions.

01εεεεεεεε0ε1εq0q1q2q3q4q5q6q7q8q9q10q11

Minimal DFA

3 states — no smaller DFA accepts this language.

010101{{q0,q2,q3,q4,q5,q7,q8},{q6}}{{q0,q1,q2,q4,q5,q7,q8,q9,q10}}{{q0,q2,q3,q4,q5,q7,q8,q11}}

The language

Every string up to length 4: 7 of 31 accepted.

  • ε
  • 0
  • 1
  • 00
  • 01
  • 10
  • 11
  • 000
  • 001
  • 010
  • 011
  • 100
  • 101
  • 110
  • 111
  • 0000
  • 0001
  • 0010
  • 0011
  • 0100
  • 0101
  • 0110
  • 0111
  • 1000
  • 1001
  • 1010
  • 1011
  • 1100
  • 1101
  • 1110
  • 1111