Skip to content
Tape‑n‑Trace
PracticeSearch 26 tools

← All case studies

Mobile number validator

CO2BTL 3 – ApplySDG 9 — Industry, Innovation & InfrastructureModule 2

An Indian mobile number: ten digits, the first between 6 and 9. "h" stands for a high leading digit and "d" for any digit, so the machine is a chain of ten states rather than a chain of ten states each with ten outgoing edges. The abstraction is the whole trick — the language over real digits is the same shape.

The expression

hddddddddd

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

dhd, hdhdhdhdhdhdhdhdhdhd, h{{q0}}{{}}{{q1,q2}}{{q3,q4}}{{q5,q6}}{{q7,q8}}{{q9,q10}}{{q11,q12}}{{q13,q14}}{{q15,q16}}{{q17,q18}}{{q19}}
Try
dhd, hdhdhdhdhdhdhdhdhdhd, h{{q0}}{{}}{{q1,q2}}{{q3,q4}}{{q5,q6}}{{q7,q8}}{{q9,q10}}{{q11,q12}}{{q13,q14}}{{q15,q16}}{{q17,q18}}{{q19}}

Input

0 of 10 read

Narration

{{q0}}

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

Hopcroft 2e, §2.2.4

Accepted

Run many strings

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