Test if Two Automata Recognize the Same Language
This tool allows you to determine if two finite automata recognize the same language.
What is Language Equivalence?
Two automata are equivalent if they recognize the same language - that is, they accept exactly the same set of strings.
This tool uses the product construction to check for equivalence. It creates a product automaton that accepts strings that are accepted by one automaton but not the other. If this product automaton's language is empty, the original automata are equivalent.
First Automaton
Define the first automaton you want to compare
States
| Name | Start | Accept | Actions |
|---|---|---|---|
| q₀ | |||
| q₁ | |||
| q₂ |
Transitions
| From | Symbol(s) | To | Actions |
|---|---|---|---|
| q₀ | a | q₁ | |
| q₁ | b | q₂ | |
| q₂ | a,b | q₂ |
Preview
Second Automaton
Define the second automaton you want to compare
States
| Name | Start | Accept | Actions |
|---|---|---|---|
| s₀ | |||
| s₁ | |||
| s₂ |
Transitions
| From | Symbol(s) | To | Actions |
|---|---|---|---|
| s₀ | a | s₀ | |
| s₀ | b | s₁ | |
| s₁ | a | s₂ | |
| s₂ | a,b | s₂ |
Preview
Predefined Examples
Choose from these example pairs of automata