01
Expression Builder
Compose a regular expression using the symbol palette below, then inspect its NFA/DFA structure and properties in real time.
Literals
Operators
Snippets
Enter a regular expression above to see its analysis.
02
String Generator
Enumerate all strings accepted by a regular expression up to any length, in BFS order.
Enter a regular expression and click Generate.
03
String Tester
Test whether individual strings or batches of strings are accepted or rejected by a regular expression.
Batch results will appear here.
04
Equivalence Checker
Two REs are equivalent iff they define the same language. Uses Thompson's NFA β Subset DFA β BFS product automaton.
β‘?
Enter two regular expressions and click Check Equivalence.
05
Reference Guide
Notation, operator table, algebraic laws, and the algorithm pipeline used by this tool.
Notation
| Notation | Meaning | Example | Accepts |
|---|---|---|---|
a | Literal symbol | a | a |
Ξ΅ | Empty string | Ξ΅ | "" |
β
| Empty set | β
| nothing |
r+s | Union | a+b | a or b |
rs | Concatenation | ab | ab |
r* | Kleene star | a* | Ξ΅, a, aa, ... |
r! | One or more | a! | a, aa, aaa, ... |
r? | Zero or one | a? | Ξ΅ or a |
(r) | Grouping | (ab)* | Ξ΅, ab, abab, ... |
Algebraic Laws
| Law | Identity |
|---|---|
| Annihilation | rβ
= β
r = β
|
| Identity (concat) | rΞ΅ = Ξ΅r = r |
| Identity (union) | r+β
= r |
| Commutativity | r+s = s+r |
| Associativity | (r+s)+t = r+(s+t) |
| Idempotency | r+r = r |
| Distributivity | r(s+t) = rs+rt |
| Star idempotent | (r*)* = r* |
| Star of empty | β
* = Ξ΅ |
| Star of Ξ΅ | Ξ΅* = Ξ΅ |
| Plus definition | r! = rr* |
| Question definition | r? = r+Ξ΅ |
| Arden's Lemma | L = rL+s β L = r*s |
Algorithm Pipeline
01
Parsing
Recursive-descent parser builds an abstract parse tree respecting precedence: grouping > repetition > concatenation > union.
β
02
Thompson's NFA Construction
Each sub-expression maps to an NFA fragment with exactly one start and one accept state. Fragments are composed via union, concatenation, and star constructions using Ξ΅-transitions.
β
03
Ξ΅-closure & Subset Construction
Each DFA state is a set of NFA states reachable via Ξ΅-transitions. BFS over subsets builds the complete DFA. A DFA state is accepting iff any NFA state in it is accepting.
β
04
Equivalence via Product Automaton
BFS over pairs (qβ, qβ) of DFA states from both machines. If any pair has one accepting and one rejecting, the witness input string distinguishes the two languages.
Complexity
| Operation | Complexity |
|---|---|
| Parsing | O(n) |
| Thompson's NFA | O(n) states, O(n) transitions |
| Subset DFA | O(2βΏ) states worst case |
| NFA simulation | O(nΒ·|w|) |
| Equivalence check | O(|DFAβ| Γ |DFAβ|) |