🔄 Regex to NFA

中文 EN

← All Tools

Enter Regular Expression

NFA State Diagram

What is the Regex to NFA Converter?

Uses Thompson's construction algorithm to convert regular expressions into NFAs (Nondeterministic Finite Automata) and renders state transition diagrams on Canvas. Helps understand the underlying principles of regex — a visualization tool for compiler theory and formal language study.

Core features of Regex to NFA

• Thompson's Construction: Systematic regex-to-NFA conversion

• Canvas Visualization: Draws state nodes and transition edges

• ε-Transition Labels: Clearly shows empty transitions

• State Statistics: Displays state count and transition count

• Export PNG: Save state diagrams as images

Regex to NFA in 3 steps

Step 1: Enter a regular expression. Supports a|b (alternation), ab (concatenation), a* (closure), a+ (positive closure), a? (optional), () (grouping), . (any character).

Step 2: Click "Generate NFA" — the Canvas automatically draws the state diagram. Single circles are normal states, double circles are accept states, and an arrow points to the start state.

Step 3: Review ε-transitions and character transitions. Click "Download PNG" to save the diagram for study notes or documentation.

When to use Regex to NFA

Compiler Theory Study: Visualize the regex-to-automaton conversion process, intuitively understanding each step of Thompson's construction — a supplementary tool for formal language and automata theory courses.

Regex Engine Development: When building a custom regex engine, use NFA visualization to verify the construction algorithm's correctness and quickly identify bugs.

Technical Interview Prep: Regex-to-automaton conversion is a common interview topic. Use this tool to practice and verify hand-drawn NFAs.

Extended Knowledge

Thompson's Construction Rules: ① Single char a: two states connected by an a-edge; ② Concatenation RS: R's accept state connects via ε to S's start; ③ Alternation R|S: new start connects via ε to R and S starts, R and S accepts connect via ε to new accept; ④ Closure R*: new start connects via ε to R's start and new accept, R's accept connects via ε back to R's start and to new accept.

NFA→DFA→Minimized DFA: The complete regex processing pipeline: Regex→NFA (Thompson)→DFA (Subset Construction)→Minimized DFA (Hopcroft). This tool implements the first step; subsequent steps can be done with other tools.

What is an NFA?

NFA (Nondeterministic Finite Automaton) is a computational model where each state can transition to multiple states on the same input symbol, and can make ε-transitions (move without consuming input). NFAs are equivalent representations of regular expressions.

What is Thompson's construction algorithm?

Thompson's construction, invented by Ken Thompson, systematically converts regular expressions to NFAs. It recursively combines basic elements into complex structures, where each sub-NFA has exactly one start and one accept state.

What regex syntax is supported?

Supports basic operators: concatenation (ab), alternation (a|b), closure (a*), positive closure (a+), optional (a?), grouping (()), character ranges ([a-z]), and any character (.). Backreferences and lookahead are not supported.

What does ε mean in the NFA diagram?

ε (epsilon) represents an empty transition — moving from one state to another without consuming any input character. ε-transitions are the core mechanism of Thompson's construction, used to connect sub-NFAs.

What do circles and double circles represent?

Single circles are normal states. Double circles are accept states (final states). The start state is indicated by an incoming arrow. A match succeeds when all input is consumed and the NFA is in an accept state.

How to convert NFA to DFA?

The Subset Construction algorithm converts NFA to DFA. Each DFA state corresponds to a set of NFA states (ε-closure). While DFA states may grow exponentially, DFA matching is more efficient as it requires no backtracking.

const regexInput=document.getElementById('regexInput');const canvas=document.getElementById('nfaCanvas');const ctx=canvas.getContext('2d');const regexError=document.getElementById('regexError');const nfaInfo=document.getElementById('nfaInfo');const toast=document.getElementById('toast'); let stateCounter=0;let transitions=[];let states=[]; function showToast(msg){toast.textContent=msg;toast.classList.add('show');setTimeout(()=>toast.classList.remove('show'),2000);} function showError(msg){regexError.textContent=msg;regexError.classList.add('show');} function hideError(){regexError.classList.remove('show');} function newState(){const s={id:stateCounter++,x:0,y:0,isAccept:false};states.push(s);return s.id;} function addTransition(from,to,symbol){transitions.push({from,to,symbol});} function parseRegex(regex){stateCounter=0;transitions=[];states=[];let pos=0; function parseExpr(){let nfa=parseTerm();while(pos1?usableW/(count-1):0;states.forEach((s,i)=>{s.x=count===1?w/2:padding+step*i;s.y=h/2;s.isAccept=s.id===nfa.accept;});} function drawNFA(nfa){const dpr=window.devicePixelRatio||1;const rect=canvas.getBoundingClientRect();canvas.width=rect.width*dpr;canvas.height=400*dpr;ctx.scale(dpr,dpr);const w=rect.width;const h=400;ctx.clearRect(0,0,w,h);layoutStates(nfa,w,h);const stateMap={};states.forEach(s=>stateMap[s.id]=s); ctx.strokeStyle='#64748b';ctx.lineWidth=1.5;ctx.font='13px monospace';ctx.fillStyle='#22d3ee'; const drawnPairs={};transitions.forEach(t=>{const from=stateMap[t.from];const to=stateMap[t.to];if(!from||!to)return;const dx=to.x-from.x;const dy=to.y-from.y;const dist=Math.sqrt(dx*dx+dy*dy);const nx=dx/(dist||1);const ny=dy/(dist||1);const r=22;const key=t.from+'-'+t.to;const offset=drawnPairs[key]||0;drawnPairs[key]=offset+1;const curveOffset=offset*20;const startX=from.x+nx*r;const startY=from.y+ny*r;const endX=to.x-nx*r;const endY=to.y-ny*r; if(t.from===t.to){ctx.beginPath();ctx.arc(from.x,from.y-r-15,15,0.3*Math.PI,0.7*Math.PI);ctx.stroke();ctx.fillStyle='#22d3ee';ctx.fillText(t.symbol,from.x-8,from.y-r-28);return;} const midX=(startX+endX)/2;const midY=(startY+endY)/2;const perpX=-ny*curveOffset;const perpY=nx*curveOffset;const cpX=midX+perpX;const cpY=midY+perpY;ctx.beginPath();ctx.moveTo(startX,startY);ctx.quadraticCurveTo(cpX,cpY,endX,endY);ctx.stroke(); const tParam=0.95;const ax=(1-tParam)*(1-tParam)*startX+2*(1-tParam)*tParam*cpX+tParam*tParam*endX;const ay=(1-tParam)*(1-tParam)*startY+2*(1-tParam)*tParam*cpY+tParam*tParam*endY;const adx=endX-ax;const ady=endY-ay;const aLen=Math.sqrt(adx*adx+ady*ady)||1;const anx=adx/aLen;const any_=ady/aLen;ctx.beginPath();ctx.moveTo(endX,endY);ctx.lineTo(endX-8*anx+4*any_,endY-8*any_-4*anx);ctx.lineTo(endX-8*anx-4*any_,endY-8*any_+4*anx);ctx.fillStyle='#64748b';ctx.fill(); ctx.fillStyle='#22d3ee';ctx.fillText(t.symbol,cpX-5,cpY-8);}); const startState=stateMap[nfa.start];if(startState){ctx.beginPath();ctx.moveTo(startState.x-40,startState.y);ctx.lineTo(startState.x-24,startState.y);ctx.strokeStyle='#06b6d4';ctx.lineWidth=2;ctx.stroke();ctx.beginPath();ctx.moveTo(startState.x-24,startState.y);ctx.lineTo(startState.x-30,startState.y-5);ctx.lineTo(startState.x-30,startState.y+5);ctx.fillStyle='#06b6d4';ctx.fill();} states.forEach(s=>{ctx.beginPath();ctx.arc(s.x,s.y,22,0,Math.PI*2);ctx.strokeStyle=s.id===nfa.start?'#06b6d4':'#94a3b8';ctx.lineWidth=2;ctx.stroke();ctx.fillStyle='#1e293b';ctx.fill();if(s.isAccept){ctx.beginPath();ctx.arc(s.x,s.y,17,0,Math.PI*2);ctx.strokeStyle='#22d3ee';ctx.lineWidth=2;ctx.stroke();}ctx.fillStyle='#e2e8f0';ctx.font='12px sans-serif';ctx.textAlign='center';ctx.textBaseline='middle';ctx.fillText('q'+s.id,s.x,s.y);}); nfaInfo.innerHTML='States: '+states.length+'Transitions: '+transitions.length+'Start: q'+nfa.start+'Accept: q'+nfa.accept+'';} function generateNFA(){hideError();const regex=regexInput.value.trim();if(!regex){showError('Please enter a regular expression');return;}try{const nfa=parseRegex(regex);drawNFA(nfa);showToast('NFA generated');}catch(e){showError('Parse error: '+e.message);}} function loadExample(){regexInput.value='(a|b)*abb';hideError();generateNFA();showToast('Example loaded');} function clearAll(){regexInput.value='';const dpr=window.devicePixelRatio||1;const rect=canvas.getBoundingClientRect();canvas.width=rect.width*dpr;canvas.height=400*dpr;ctx.scale(dpr,dpr);ctx.clearRect(0,0,rect.width,400);nfaInfo.innerHTML='';hideError();showToast('Cleared');} function downloadPNG(){const link=document.createElement('a');link.download='nfa-'+(regexInput.value.trim()||'diagram')+'.png';link.href=canvas.toDataURL();link.click();showToast('Downloaded PNG');} document.addEventListener('keydown',function(e){if(e.ctrlKey||e.metaKey){if(e.key==='Enter'){e.preventDefault();generateNFA();}}}); window.addEventListener('load',function(){loadExample();});