Closure Properties, Pumping Lemma & Decision Algorithms
Open in the Padhaiko app2.7 Closure Properties of Regular Languages
Closure of Regular Languages under Standard Operations
The class of regular languages (languages accepted by finite automata) is closed under:
- Union ()
- Concatenation ()
- Kleene Star ()
- Complementation ()
- Intersection ()
a. Closure under Union
Let and be two NFAs with disjoint state sets (). We construct a new -NFA such that by introducing a new start state with -transitions to and :
Concrete Example (Book pp. 80–82):
- Let accept :
| State | a | b |
|---|---|---|
| →q0 | q1 | q3 |
| q1 | q3 | q2 |
| q3 | q3 | q3 |
| *q2 | q2 | q2 |
- Machine-checked
- ✓ accepts ab
- ✓ accepts aba
- ✓ accepts abb
- ✓ accepts abab
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ba
- ✓ rejects aa
- Let recognize strings over ending with
10:
| State | 0 | 1 | ε |
|---|---|---|---|
| →q00 | {q00} | {q11} | ∅ |
| q11 | {q22} | {q11} | ∅ |
| *q22 | ∅ | {q11} | ∅ |
- Machine-checked
- ✓ accepts 10
- ✓ accepts 010
- ✓ accepts 110
- ✓ accepts 1010
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 01
- ✓ rejects 11
- Then the union -NFA for is:
| State | a | b | 0 | 1 | ε |
|---|---|---|---|---|---|
| →s | ∅ | ∅ | ∅ | ∅ | {q0, q00} |
| q0 | {q1} | {q3} | ∅ | ∅ | ∅ |
| q00 | ∅ | ∅ | {q00} | {q11} | ∅ |
| q1 | {q3} | {q2} | ∅ | ∅ | ∅ |
| q3 | {q3} | {q3} | ∅ | ∅ | ∅ |
| *q2 | {q2} | {q2} | ∅ | ∅ | ∅ |
| q11 | ∅ | ∅ | {q22} | {q11} | ∅ |
| *q22 | ∅ | ∅ | ∅ | {q11} | ∅ |
- Machine-checked
- ✓ accepts ab
- ✓ accepts aba
- ✓ accepts 10
- ✓ accepts 010
- ✓ accepts 110
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ba
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 11
b. Closure under Concatenation
Let and be two NFAs with . We construct an -NFA accepting by connecting every final state to via an -transition:
Using the same automata and from above, the concatenation automaton for has , , and the bridge edge :
| State | a | b | 0 | 1 | ε |
|---|---|---|---|---|---|
| →q0 | {q1} | {q3} | ∅ | ∅ | ∅ |
| q1 | {q3} | {q2} | ∅ | ∅ | ∅ |
| q3 | {q3} | {q3} | ∅ | ∅ | ∅ |
| q2 | {q2} | {q2} | ∅ | ∅ | {q00} |
| q00 | ∅ | ∅ | {q00} | {q11} | ∅ |
| q11 | ∅ | ∅ | {q22} | {q11} | ∅ |
| *q22 | ∅ | ∅ | ∅ | {q11} | ∅ |
- Machine-checked
- ✓ accepts ab10
- ✓ accepts aba10
- ✓ accepts abb010
- ✓ accepts ab110
- ✓ rejects ε
- ✓ rejects ab
- ✓ rejects 10
- ✓ rejects ba10
- ✓ rejects ab11
c. Closure under Kleene Star
Let be an NFA. We construct a new -NFA such that as follows:
- Introduce a new start state and make an accepting state so that .
- Add an -transition to initialize .
- Add feedback -transitions from every final state back to so that after reading one string in , computation can repeat for additional strings in :
d. Closure under Complementation
Let be a regular language accepted by a complete DFA . Because every string drives a complete DFA to a unique state , interchanging the final and non-final states produces a DFA
that accepts a string if and only if rejects . Hence , proving that regular languages are closed under complementation.
Concrete Example (Book pp. 84–85):
- The DFA accepts strings over that start with
ab:
| State | a | b |
|---|---|---|
| →q0 | q1 | q3 |
| q1 | q3 | q2 |
| q3 | q3 | q3 |
| *q2 | q2 | q2 |
- Machine-checked
- ✓ accepts ab
- ✓ accepts aba
- ✓ accepts abb
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aa
- ✓ rejects ba
- Interchanging final and non-final states () gives the complement DFA accepting all strings that never start with
ab:
| State | a | b |
|---|---|---|
| →*q0 | q1 | q3 |
| *q1 | q3 | q2 |
| *q3 | q3 | q3 |
| q2 | q2 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts a
- ✓ accepts b
- ✓ accepts aa
- ✓ accepts ba
- ✓ accepts baa
- ✓ rejects ab
- ✓ rejects aba
- ✓ rejects abb
e. Closure under Intersection
Let and be two regular languages over accepted by finite automata and . By De Morgan's law for sets,
Since regular languages are already proved closed under complementation () and union (), is also a regular language. (Equivalently, if and are DFAs, their product DFA with directly recognizes .)
2.7.1 Minimization of DFA using Table-Filling Method (Myhill–Nerode Theorem)
DFA Minimization via the Table-Filling Algorithm
DFA minimization converts a given DFA into an equivalent DFA having the minimum possible number of states by identifying and merging indistinguishable (equivalent) states:
- Construct Pair Table: Remove any unreachable states, and draw a triangular table of all unordered pairs of distinct states .
- Base Marking (0-Distinguishable): Mark every pair where one state is accepting and the other is non-accepting ( or ).
- Inductive Marking: Repeatedly scan the remaining unmarked pairs . If there exists an input symbol such that the target pair is already marked, then mark . Continue iterating until a full pass produces no new markings.
- Merge Equivalent States: Any pair that remains unmarked consists of indistinguishable (equivalent) states; combine all mutually unmarked states into single merged states to form the minimized DFA.
Minimize a 5-State DFA using the Table-Filling Method
Minimize the following DFA:
| State | 0 | 1 |
|---|---|---|
| →A | B | C |
| B | B | D |
| C | B | C |
| D | B | E |
| *E | B | C |
- Machine-checked
- ✓ accepts 011
- ✓ accepts 1011
- ✓ accepts 0011
- ✓ accepts 011011
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 01
- ✓ rejects 11
- ✓ rejects 010
Since is the only accepting state (), first mark all pairs containing : , , , and .
Check and for each unmarked pair:
- : on ; on (currently unmarked).
- : on ; on ( stays unmarked).
- : on ; on (currently unmarked).
- : on ; on (marked) mark .
- : on ; on (marked) mark .
- : on ; on (marked) mark .
Now test the remaining unmarked pairs , , and :
- : on ; on (now marked) mark .
- : on ; on (unmarked).
- : on ; on (now marked) mark .
| State | ||||
|---|---|---|---|---|
| — | ||||
Only remains unmarked, so and are merged into a single start state AC :
| State | 0 | 1 |
|---|---|---|
| →AC | B | AC |
| B | B | D |
| D | B | E |
| *E | B | AC |
- Machine-checked
- ✓ accepts 011
- ✓ accepts 1011
- ✓ accepts 0011
- ✓ accepts 011011
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 01
- ✓ rejects 11
- ✓ rejects 010
States and are equivalent and merge into , yielding a 4-state minimized DFA with states .
2.8 Pumping Lemma for Regular Languages
Pumping Lemma for Regular Languages
Statement: Let be a regular language. Then there exists a constant (called the pumping length or pumping constant, equal to the number of states of a DFA recognizing ) such that every string with can be decomposed into three substrings satisfying:
- ,
- (i.e., ), and
- for all integers .
Proof (via the Pigeonhole Principle):
- Since is regular, it is accepted by some deterministic finite automaton . Let be the number of states of .
- Let be any string in of length . Consider the sequence of configurations during the first transitions of on :
- In these first steps, the automaton visits state occurrences . Because has only distinct states (pigeonholes) and visited state indices (pigeons), by the Pigeonhole Principle there exist two indices and with such that
- Define the three parts of as:
- Because , we have , establishing condition (1).
- Because , the substring has length , establishing condition (2).
- Because takes from to , takes around a cycle from back to , and takes from to an accepting state in , repeating any number of times (including , which removes ) still leaves in state before reading . Therefore for every , establishing condition (3).
2.9 Decision Algorithms for Regular Languages
Three fundamental algorithmic decision problems for regular languages are solved as follows:
- Converting Among Representations:
- NFA / -NFA DFA via the Subset Construction (and DFA NFA trivially since every DFA is already an NFA).
- Regular Expression -NFA via Thompson's Construction, and Finite Automaton Regular Expression via Arden's Theorem (or state elimination).
- Testing Emptiness (): Given a finite automaton , treat its state diagram as a directed graph and perform breadth-first or depth-first reachability from the start state . If at least one accepting state is reachable from , then ; if all accepting states are disconnected from , then . (Equivalently, for an -state DFA, iff accepts at least one string of length .)
- Testing Membership (): Convert the specification of into a DFA and simulate on input starting from . In deterministic transitions, reaches a state ; output "Yes" if and "No" if .
- Testing Equivalence of Two DFAs (): Given two DFAs and :
- Method A (Table-Filling / Distinguishability): Run the DFA minimization table-filling algorithm on the combined state set . Then if and only if the pair of start states remains unmarked (indistinguishable).
- Method B (Symmetric Difference Emptiness): Using closure under complementation, union, and intersection, construct a DFA for the symmetric difference
Then if and only if , which is decided by the emptiness test.
2.10 Closure Properties and Closures of Relations
Closure of a Set under Relations and Reflexive, Symmetric & Transitive Closures
Let be a domain, , and be an -ary relation on . A subset is closed under if whenever and . Any statement of the form "the set is closed under relations " is called a closure property of .
For a binary relation on a finite set with :
- Reflexive Closure: The smallest reflexive relation on containing :
- Symmetric Closure: The smallest symmetric relation on containing :
- Transitive Closure (): The smallest transitive relation on containing , consisting of all pairs connected by a non-trivial directed path of length in :
Worked Illustration (Book pp. 93–94): Let and . Then:
- Reflexive closure: Since ,
- Symmetric closure: Since ,
- Transitive closure: Since and compose to give ,
Solutions to Important Questions (Questions 37–45, Book pp. 129–137)
Important Question 37 — Prove Square-Length Language is Not Regular [2074 Chaitra]
Show that the language is not regular using the Pumping Lemma.
Suppose for contradiction that is regular with pumping constant . For any with , there must exist a decomposition with , , and for all .
Choose , which has . For any split with and , we have . Pumping with gives , whose length satisfies
Since lies strictly between the consecutive perfect squares and , , a contradiction.
Taking and () with , , (, ):
- For : (contradiction).
- For : (contradiction).
Hence is not regular.
For , , so ; hence is not regular.
Important Question 38 — Prove L = {w in {a,b}* : n_a(w) = n_b(w)} is Not Regular [2071 Shrawan]
Show that is not regular by using the Pumping Lemma for regular languages.
Assume is regular with pumping constant . Choose , which has equal numbers of 's and 's and length .
For any decomposition satisfying and , the prefix lies entirely within the leading block , so for some . Then for (or ),
because the number of 's no longer equals the number of 's. (In the book's numerical illustration with and , taking gives and .)
Pumping changes the count of one symbol without matching the other, so and is not regular.
Important Question 39 — Prove Prime-Length 0-Language is Not Regular [2079 Baishakh]
Use the Pumping Lemma for regular languages to prove that is not regular.
Assume is regular with pumping constant . Choose where is a prime with .
Let be any decomposition with and . For , the pumped string has length
Since and , the length is a composite number, so . (In the book's concrete illustration on p. 131 with and , taking gives and .)
For ( prime), is composite, so and is not regular.
Important Question 40 — Prove Factorial-Power Language is Not Regular [2078 Bhadra]
Use the Pumping Lemma for regular languages to show that is not regular.
Suppose is regular with pumping constant , and pick where . For any split with and , pumping with yields , which satisfies
Since lies strictly between consecutive factorials and , .
With and , taking () gives:
- For : (since is not a factorial).
- For : (since is not a factorial).
Hence is not regular.
, so and is not regular.
Important Question 41 — Prove Equal a's Separated by b Not Regular [2076 Ashwin, 2072 Chaitra]
Use the Pumping Lemma for regular languages to prove that is not regular.
Assume is regular with pumping constant , and choose (). For every split with and , the substring consists solely of 's from the prefix before b (). Pumping with gives (and gives ), a contradiction.
With and , taking gives:
- For : (no
b). - For : (two
b's).
Hence is not regular.
violates the Pumping Lemma and is not regular.
Important Question 42 — Prove Prime-Length 1-Language is Not Regular [2075 Chaitra]
Use the Pumping Lemma for regular languages to show that is not regular.
Suppose is regular with pumping constant , and choose for a prime . For any split with and , pumping times yields , which is composite, so . (In the book's illustration on pp. 133–134 with and , setting gives and .)
is not regular.
Important Question 43 — Prove L = {w in {0,1}* : n_0(w) = n_1(w)} is Not Regular [2073 Chaitra]
Use the Pumping Lemma to prove that is not regular.
Suppose is regular with pumping constant , and pick . Since and , we have , so and . (In the book's illustration on p. 134 with and , taking gives and .)
is not regular.
Important Question 44 — Prove Prime-Length a-Language is Not Regular [2072 Kartik]
Show that the language is not regular using the Pumping Lemma.
Assume is regular with pumping constant . For any prime and , any split with and fails at since is composite.
In the book's numerical illustration on page 135 with , , and ():
- For : .
- For : (contradiction, since is composite).
Since for (and for in the book's example), is not regular.
Important Question 45 — Minimize the Given 6-State DFA [2082 Kartik]
Minimize the given DFA:
Here the accepting states are and the non-accepting states are :
| State | 0 | 1 |
|---|---|---|
| →A | B | C |
| B | A | D |
| *C | E | F |
| *D | E | F |
| *E | E | F |
| F | F | F |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 010
- ✓ accepts 00100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 00
- ✓ rejects 11
- ✓ rejects 011
- ✓ rejects 101
Mark every pair consisting of one state in and one state in . The remaining unmarked pairs are , , , , , and .
- : on (unmarked); on (unmarked).
- : on ; on (unmarked).
- : on ; on (unmarked).
- : on ; on (unmarked).
- : on (unmarked); on (marked) mark .
- : on (now marked); on (marked) mark .
In the second iteration, , , , and produce no new markings, so the algorithm terminates:
| State | |||||
|---|---|---|---|---|---|
| — | |||||
| — | |||||
| — | — | ||||
{A, B} and {C, D, E}Combine into start state AB and combine into accepting state CDE :
(AB) | ||
(CDE) | ||
(F) |
| State | 0 | 1 |
|---|---|---|
| →AB | AB | CDE |
| *CDE | CDE | F |
| F | F | F |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 010
- ✓ accepts 00100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 00
- ✓ rejects 11
- ✓ rejects 011
- ✓ rejects 101
The minimized DFA has 3 states: start state , accepting state , and dead state .
Exercises
Exercises
List closure properties of regular language. [2078 Bhadra]
Boolean and algebraic closure properties: If and are regular languages over an alphabet , they are closed under:
- Union (): The language containing strings in , , or both.
- Concatenation (): The language .
- Kleene Star (): The language formed by zero or more repetitions.
- Complementation (): Strings over that do not belong to .
- Intersection (): Strings belonging simultaneously to both and .
Additional closure operations:
- Set Difference (): Since , difference follows from intersection and complementation.
- Reversal (): The language of all reversed strings.
- Homomorphism and Inverse Homomorphism: If is a homomorphism, both and are regular.
- Prefix, Suffix, and Substring:
Regular languages are closed under union (), concatenation (), Kleene star (), complementation (), intersection (), set difference (), and reversal ().
How can you show that the regular languages are closed under union, concatenation, and complement? Explain with the required diagram of automata. [2081 Bhadra]
Closure under Union (Construction and Automata Diagram): Let and be regular languages recognized by NFAs and with disjoint state sets. Construct a new -NFA :
- Introduce a new initial state .
- Add -transitions from to both and : .
- Retain all original states and transitions of and .
For example, uniting and gives the language :
| State | 0 | 1 | ε |
|---|---|---|---|
| →s0 | ∅ | ∅ | {q0, q1} |
| *q0 | {q0} | ∅ | ∅ |
| *q1 | ∅ | {q1} | ∅ |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 0
- ✓ accepts 1
- ✓ accepts 00
- ✓ accepts 11
- ✓ accepts 000
- ✓ accepts 111
- ✓ rejects 01
- ✓ rejects 10
- ✓ rejects 010
- ✓ rejects 101
- ✓ rejects 001
Closure under Concatenation (Construction and Automata Diagram): Construct an -NFA :
- The start state is (the start state of ).
- The final states are (the final states of ).
- For every accepting state , add an -transition to the start state of : .
For example, concatenating and yields :
| State | 0 | 1 | ε |
|---|---|---|---|
| →q0 | {q0} | ∅ | {q1} |
| *q1 | ∅ | {q1} | ∅ |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 0
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 001
- ✓ accepts 011
- ✓ accepts 000111
- ✓ rejects 10
- ✓ rejects 110
- ✓ rejects 010
- ✓ rejects 100
- ✓ rejects 0101
Closure under Complementation (Construction and Automata Diagram): Let be recognized by a complete DFA where is totally defined. Construct the complement DFA :
- Keep states , alphabet , transition function , and start state identical.
- Invert the accepting status: every accepting state becomes non-accepting, and every non-accepting state becomes accepting ().
For example, taking the complement of strings ending in 0 over gives strings ending in 1 or the empty string :
| State | 0 | 1 |
|---|---|---|
| →*q0 | q1 | q2 |
| q1 | q1 | q2 |
| *q2 | q1 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 11
- ✓ accepts 001
- ✓ accepts 111
- ✓ rejects 0
- ✓ rejects 10
- ✓ rejects 00
- ✓ rejects 110
- ✓ rejects 010
Given NFAs and : (1) for union, add a new start state with -transitions to and and set ; (2) for concatenation, add -transitions from every to with start state and final states ; (3) for complementation of a complete DFA , swap accepting and non-accepting states to obtain .
Prove that the set of regular languages are closed under complementation and intersection operations. [2078 Kartik, 2078 Bhadra]
Proof of closure under Complementation: Let be a regular language over . By definition, there exists a deterministic finite automaton that accepts . If is not fully specified, add a dead state to make a complete total function. Construct . Because is deterministic:
Since is a valid DFA, is regular.
Proof of closure under Intersection (Cross-Product DFA): Let and be regular languages accepted by complete DFAs and . Construct the product DFA where:
Tracing string :
Since is a DFA, is regular.
Alternative algebraic proof via De Morgan's Laws: By set theory, the intersection of two sets can be expressed using union and complementation:
- Since and are regular, their complements and are regular.
- By closure under union, is regular.
- Taking the complement of that union, , is regular.
For a complete DFA recognizing , the DFA recognizes , proving closure under complementation. For two regular languages and , De Morgan's law gives ; since regular languages are closed under complementation and union, they are also closed under intersection.
State pumping lemma for regular languages. [2079 Bhadra, 2078 Bhadra]
Statement of the Pumping Lemma: Let be a regular language. Then there exists a positive integer (called the pumping length or pumping constant) such that: Every string with length can be partitioned into three parts:
satisfying the following three conditions:
- (the first two substrings together have length at most )
- (the middle substring is non-empty, i.e., )
- For all integers , (pumping zero, one, or more times produces a string that remains in )
Theoretical justification (Pigeonhole Principle): Let be a DFA with states that accepts . Processing any string of length traverses a sequence of states:
By the Pigeonhole Principle, among the first states , at least two states must be identical:
Let be the string leading from to , be the loop string from to , and be the string from to the accepting state .
- .
- .
- Bypassing the loop () or traversing it times () always ends in the accepting state , guaranteeing .
Application: The Pumping Lemma is a necessary property of regular languages. Its contrapositive is used to prove that non-regular languages (such as ) cannot be recognized by any finite automaton.
If is a regular language, there exists a pumping constant such that every string with can be written as satisfying: (i) , (ii) , and (iii) for all .
How can you prove that some languages are not regular? [2078 Kartik]
Proof by contradiction using the Pumping Lemma: The primary standard method to prove that a language is not regular is proof by contradiction using the Pumping Lemma:
- Assume regularity: Assume is regular. By the Pumping Lemma, there must exist a pumping constant .
- Select test string: Choose a specific string whose length depends on such that .
- Examine all splits: Consider every possible split that satisfies and .
- Demonstrate contradiction: Find a pumping value such that the pumped string .
Since this violates the Pumping Lemma, the initial assumption is false, proving that is not regular.
Concrete demonstration ():
- Assume is regular with pumping length .
- Choose . Here .
- Since , the substring lies strictly within the initial block of 's.
- Since , for some .
- Pump with :
The number of 's is , which is strictly greater than the number of 's ().
- Thus , contradicting the Pumping Lemma. Hence is not regular.
Alternative method: Closure Properties: One can also prove non-regularity by contradiction using closure properties: If assuming is regular implies, through operations like intersection with a known regular language or homomorphism, that a known non-regular language (like ) is regular, then cannot be regular.
By contradiction using the Pumping Lemma for regular languages: assume is regular with pumping length , select a string with , and show that for every decomposition satisfying and , there exists an integer such that .
Explain the decision properties of regular languages. [2081 Chaitra, 2078 Kartik]
Concept of decision properties: A decision property of regular languages is an algorithm (a decision procedure) that takes a formal description of a regular language (such as a DFA) and answers a specific question with a definitive Yes or No in finite time.
The three fundamental decision properties:
- Emptiness Problem ():
- Procedure: Model the DFA as a directed graph. Perform graph reachability search (BFS/DFS) starting from start state .
- Decision: If any final state in is reachable, (No); if no final state is reachable, (Yes).
- Membership Problem ():
- Procedure: Simulate the DFA on string for steps.
- Decision: If the state reached after reading is in , output Yes; otherwise output No. Time complexity is .
- Finiteness Problem (Is finite?):
- Procedure: Remove all unreachable states and dead states. Search for cycles in the remaining transition graph.
- Decision: If any cycle exists, the language contains infinitely many strings (No); if acyclic, the language is finite (Yes).
Equivalence and Containment decision properties:
- Equivalence Problem ():
- Construct the symmetric difference DFA for and test if .
- Containment Problem ():
- Construct the DFA for and test whether its language is empty.
The three primary decision properties for regular languages are: (1) Emptiness—deciding whether by checking if any accepting state is reachable from the start state ; (2) Membership—deciding whether by simulating the DFA on ; and (3) Equivalence—deciding whether by testing whether the start states are indistinguishable or whether the symmetric difference language is empty.
Write down the procedure to check the equivalence of two DFAs. [2081 Chaitra, 2080 Baishakh]
Principle of equivalence via state indistinguishability: Two DFAs and over the same alphabet recognize the same language () if and only if their initial states and are indistinguishable.
Table-filling algorithm procedure:
- Combine state spaces: Combine and into a single machine with state set (renaming states if necessary so that ).
- Set up comparison table: Create a lower-triangular grid listing all unordered pairs for distinct .
- Basis Step (Mark trivially distinguishable pairs): Mark every pair where exactly one state is accepting:
- Inductive Step (Propagate marks): Iterate through all unmarked pairs . For each symbol :
- Compute destination states and .
- If is already marked, mark . Repeat until an entire pass across the table produces no new marks.
- Evaluate start state pair:
- If is unmarked, then and the two DFAs are equivalent ().
- If is marked, the two DFAs are not equivalent.
Alternative Symmetric Difference method:
- Construct the product DFA recognizing the symmetric difference:
- In the product DFA, accepting states are .
- Test if using the reachability (emptiness) algorithm. if and only if no accepting state is reachable from .
Combine the state sets of the two DFAs and and run the table-filling distinguishability algorithm: mark all pairs where one state is accepting and the other is non-accepting, and iteratively mark any pair whose transition pair is marked for some . The two DFAs are equivalent () if and only if their start-state pair remains unmarked.