Skip to content
Tape‑n‑Trace
PracticeSearch 26 tools

← All case studies

Email and URL validation

CO1BTL 3 – ApplySDG 9 — Industry, Innovation & InfrastructureModule 1

A local part, an @, a domain, and at least one dot-separated label after it. The alphabet is abstracted so the diagram stays readable: "a" stands for any letter, and "." and "@" are themselves. Real address syntax (RFC 5322) is far larger, and notably is *not* regular once quoted local parts and nested comments are allowed — which is itself worth knowing.

The expression

aa*@aa*.aa*(.aa*)*

The machine below is its minimal DFA — 7 states over {., @, a}. Open it in the playground to see the parse tree and the ε-NFA it came from.

., @a., @, a.@a., @a.@a., @a.@a{{q0}}{{}}{{q1,q2,q4,q5,q6},{q2,q3,q5,q6}}{{q7,q8}}{{q9,q10,q12,q13,q14},{q10,q11,q13,q14}}{{q15,q16},{q23,q24}}{{q17,q18,q20,q21,q22,q30,q31},{q18,q19,q21,q22,q30,q31},{q22,q25,q26,q28,q29,q31},{q22,q26,q27,q29,q31}}
Try
., @a., @, a.@a., @a.@a., @a.@a{{q0}}{{}}{{q1,q2,q4,q5,q6},{q2,q3,q5,q6}}{{q7,q8}}{{q9,q10,q12,q13,q14},{q10,q11,q13,q14}}{{q15,q16},{q23,q24}}{{q17,q18,q20,q21,q22,q30,q31},{q18,q19,q21,q22,q30,q31},{q22,q25,q26,q28,q29,q31},{q22,q26,q27,q29,q31}}

Input

0 of 5 read

Narration

{{q0}}

Start in state {{q0}} with "a@a.a" still to read.

Hopcroft 2e, §2.2.4

Accepted

Run many strings

One string per line. A blank line means the empty string.