NFA to DFA Converter

Department of Computer Science & Engineering | Automata Theory and Formal Languages

Define NFA

Sample Automata

Load pre-defined examples to explore different automata concepts

Click "Load" on any example to populate the NFA with pre-defined states, symbols, and transitions. This will replace your current automaton.

Strings ending with 'ab'

An NFA that accepts any string that ends with the substring 'ab'

States:

q0 (Start)

q2 (Final)

Symbols:

✓ Accepted Examples:

aab

bab

ababab

✗ Rejected Examples:

aba

Strings containing 'aa'

An NFA that accepts any string that contains the substring 'aa'

States:

q0 (Start)

q2 (Final)

Symbols:

✓ Accepted Examples:

aaa

baa

aab

✗ Rejected Examples:

bab

Even number of 'a's

An NFA that accepts strings with an even number of 'a's

States:

q0 (Start) (Final)

Symbols:

✓ Accepted Examples:

aabb

abab

✗ Rejected Examples:

aaa

States

Input Symbols

Transitions

Current Transitions

Convert Regular Expression to NFA

Enter a regular expression to convert it to an NFA using Thompson's construction

Regular Expression

Supported syntax:

a - Single character
ab - Concatenation
a|b - Alternation (OR)
a* - Kleene star (zero or more)
a+ - One or more
a? - Optional (zero or one)
(ab) - Grouping

Common Regex Patterns

Select a regex pattern to use as an example

`a`

Matches a single character 'a'

✓ Matches:

✗ Non-matches:

`ab`

Matches the sequence 'ab'

✓ Matches:

✗ Non-matches:

`a|b`

Matches either 'a' or 'b'

✓ Matches:

✗ Non-matches:

`a*`

Matches zero or more 'a's

✓ Matches:

aaa

✗ Non-matches:

`a+`

Matches one or more 'a's

✓ Matches:

aaa

✗ Non-matches:

`a?`

Matches zero or one 'a'

✓ Matches:

✗ Non-matches:

`(a|b)*`

Matches any sequence of 'a's and 'b's (including empty string)

✓ Matches:

aab

abb

✗ Non-matches:

abc

NFA Visualization

Add states to see the NFA graph

NFA Legend

Color coding for states and transitions

States

Regular State

Start State

Final State

Start & Final State

Transitions

Regular Transition

Self-Loop

a, b

Multiple Symbols

Badges

From

From State

To State

a → bTransition Symbol

DFA Visualization

Convert an NFA to see the DFA graph

Minimized DFA Visualization

Convert an NFA to see the DFA graph

Conversion Steps

Click "Convert to DFA" to see the step-by-step conversion process.