PadhaikoAll subjects

Closure Properties, Pumping Lemma & Decision Algorithms

Theory of Computation (ENCT 203)

Open in the Padhaiko app

2.7 Closure Properties of Regular Languages

Theorem

Closure of Regular Languages under Standard Operations

The class of regular languages (languages accepted by finite automata) is closed under:

  1. Union ()
  2. Concatenation ()
  3. Kleene Star ()
  4. Complementation ()
  5. 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):

a. Closure under UnionDFA
a. Closure under Union a, b a, b a b a b q0 q1 q3 q2
Stateab
→q0q1q3
q1q3q2
q3q3q3
*q2q2q2
a. Closure under Unionε-NFA
a. Closure under Union 1 0 1 0 1 q00 q11 q22
State01ε
→q00{q00}{q11}∅
q11{q22}{q11}∅
*q22∅{q11}∅
a. Closure under Unionε-NFA
a. Closure under Union 1 0 a, b a, b ε ε a b a b 1 0 1 s q0 q00 q1 q3 q2 q11 q22
Stateab01ε
→s∅∅∅∅{q0, q00}
q0{q1}{q3}∅∅∅
q00∅∅{q00}{q11}∅
q1{q3}{q2}∅∅∅
q3{q3}{q3}∅∅∅
*q2{q2}{q2}∅∅∅
q11∅∅{q22}{q11}∅
*q22∅∅∅{q11}∅

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 :

b. Closure under Concatenationε-NFA
b. Closure under Concatenation 1 0 a, b a, b a b a b ε 1 0 1 q0 q1 q3 q2 q00 q11 q22
Stateab01ε
→q0{q1}{q3}∅∅∅
q1{q3}{q2}∅∅∅
q3{q3}{q3}∅∅∅
q2{q2}{q2}∅∅{q00}
q00∅∅{q00}{q11}∅
q11∅∅{q22}{q11}∅
*q22∅∅∅{q11}∅

c. Closure under Kleene Star

Let be an NFA. We construct a new -NFA such that as follows:

  1. Introduce a new start state and make an accepting state so that .
  2. Add an -transition to initialize .
  3. 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):

d. Closure under ComplementationDFA
d. Closure under Complementation a, b a, b a b a b q0 q1 q3 q2
Stateab
→q0q1q3
q1q3q2
q3q3q3
*q2q2q2
d. Closure under ComplementationDFA
d. Closure under Complementation a, b a, b a b a b q0 q1 q3 q2
Stateab
→*q0q1q3
*q1q3q2
*q3q3q3
q2q2q2

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)

Definition

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:

  1. Construct Pair Table: Remove any unreachable states, and draw a triangular table of all unordered pairs of distinct states .
  2. Base Marking (0-Distinguishable): Mark every pair where one state is accepting and the other is non-accepting ( or ).
  3. 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.
  4. 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.
Example 2.18

Minimize a 5-State DFA using the Table-Filling Method

Minimize the following DFA:

Worked Out Example 2.18 — Minimize a 5-State DFA using the Table-Filling MethodDFA
Worked Out Example 2.18 — Minimize a 5-State DFA using the Table-Filling Method 1 0 0 1 1 0 0 1 0 1 A B C D E
State01
→ABC
BBD
CBC
DBE
*EBC
  • Machine-checked
  • ✓ accepts 011
  • ✓ accepts 1011
  • ✓ accepts 0011
  • ✓ accepts 011011
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 01
  • ✓ rejects 11
  • ✓ rejects 010
Initialize the table and mark final vs. non-final pairs

Since is the only accepting state (), first mark all pairs containing : , , , and .

First iteration over unmarked pairs

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 .
Second iteration over remaining unmarked pairs

Now test the remaining unmarked pairs , , and :

  • : on ; on (now marked) mark .
  • : on ; on (unmarked).
  • : on ; on (now marked) mark .
State
—
Merge the unmarked pair and draw the minimized DFA

Only remains unmarked, so and are merged into a single start state AC :

Worked Out Example 2.18 — Minimize a 5-State DFA using the Table-Filling MethodDFA
Worked Out Example 2.18 — Minimize a 5-State DFA using the Table-Filling Method 0 1 0 1 0 1 0 1 AC B D E
State01
→ACBAC
BBD
DBE
*EBAC
  • Machine-checked
  • ✓ accepts 011
  • ✓ accepts 1011
  • ✓ accepts 0011
  • ✓ accepts 011011
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 01
  • ✓ rejects 11
  • ✓ rejects 010
Answer:

States and are equivalent and merge into , yielding a 4-state minimized DFA with states .


2.8 Pumping Lemma for Regular Languages

Theorem

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:

  1. ,
  2. (i.e., ), and
  3. for all integers .

Proof (via the Pigeonhole Principle):

  1. Since is regular, it is accepted by some deterministic finite automaton . Let be the number of states of .
  2. Let be any string in of length . Consider the sequence of configurations during the first transitions of on :
  1. 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
  1. Define the three parts of as:

2.9 Decision Algorithms for Regular Languages

Three fundamental algorithmic decision problems for regular languages are solved as follows:

  1. 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).
  2. 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 .)
  3. 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 .
  4. 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

Definition

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 :

  1. Reflexive Closure: The smallest reflexive relation on containing :
  1. Symmetric Closure: The smallest symmetric relation on containing :
  1. 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:


Solutions to Important Questions (Questions 37–45, Book pp. 129–137)

Example

Important Question 37 — Prove Square-Length Language is Not Regular [2074 Chaitra]

Show that the language is not regular using the Pumping Lemma.

State the Pumping Lemma and assume is regular

Suppose for contradiction that is regular with pumping constant . For any with , there must exist a decomposition with , , and for all .

General proof for arbitrary and any valid split

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.

Concrete numerical illustration (Book pp. 129–130)

Taking and () with , , (, ):

  • For : (contradiction).
  • For : (contradiction).

Hence is not regular.

Answer:

For , , so ; hence is not regular.

Example

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 and choose a test string

Assume is regular with pumping constant . Choose , which has equal numbers of 's and 's and length .

Show contradiction for every valid decomposition

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 .)

Answer:

Pumping changes the count of one symbol without matching the other, so and is not regular.

Example

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 and choose a prime length

Assume is regular with pumping constant . Choose where is a prime with .

Show contradiction by pumping to a composite length

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 .)

Answer:

For ( prime), is composite, so and is not regular.

Example

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.

Assume is regular and choose with

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 , .

Concrete numerical illustration (Book p. 132)

With and , taking () gives:

  • For : (since is not a factorial).
  • For : (since is not a factorial).

Hence is not regular.

Answer:

, so and is not regular.

Example

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.

General proof for arbitrary

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.

Concrete numerical illustration (Book pp. 132–133)

With and , taking gives:

  • For : (no b).
  • For : (two b's).

Hence is not regular.

Answer:

violates the Pumping Lemma and is not regular.

Example

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.

Apply the prime-length pumping argument

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 .)

Answer:

is not regular.

Example

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.

Choose and pump

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 .)

Answer:

is not regular.

Example

Important Question 44 — Prove Prime-Length a-Language is Not Regular [2072 Kartik]

Show that the language is not regular using the Pumping Lemma.

General and numerical proof

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).
Answer:

Since for (and for in the book's example), is not regular.

Example

Important Question 45 — Minimize the Given 6-State DFA [2082 Kartik]

Minimize the given DFA:

Draw the original 6-state DFA and mark final vs. non-final pairs

Here the accepting states are and the non-accepting states are :

Important Question 45 — Minimize the Given 6-State DFA [2082 Kartik]DFA
Important Question 45 — Minimize the Given 6-State DFA [2082 Kartik] 0, 1 0 0 1 0 1 0 1 0 1 1 A B C D E F
State01
→ABC
BAD
*CEF
*DEF
*EEF
FFF
  • 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 .

First and second iterations of the table-filling algorithm
  • : 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
—
—
——
Merge unmarked pairs into {A, B} and {C, D, E}

Combine into start state AB and combine into accepting state CDE :

(AB)
(CDE)
(F)
Important Question 45 — Minimize the Given 6-State DFA [2082 Kartik]DFA
Important Question 45 — Minimize the Given 6-State DFA [2082 Kartik] 0, 1 0 0 1 1 AB CDE F
State01
→ABABCDE
*CDECDEF
FFF
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 010
  • ✓ accepts 00100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 00
  • ✓ rejects 11
  • ✓ rejects 011
  • ✓ rejects 101
Answer:

The minimized DFA has 3 states: start state , accepting state , and dead state .


Exercises

Exercises

Question 1

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:

  1. Union (): The language containing strings in , , or both.
  2. Concatenation (): The language .
  3. Kleene Star (): The language formed by zero or more repetitions.
  4. Complementation (): Strings over that do not belong to .
  5. Intersection (): Strings belonging simultaneously to both and .

Additional closure operations:

  1. Set Difference (): Since , difference follows from intersection and complementation.
  2. Reversal (): The language of all reversed strings.
  3. Homomorphism and Inverse Homomorphism: If is a homomorphism, both and are regular.
  4. Prefix, Suffix, and Substring:
Answer:

Regular languages are closed under union (), concatenation (), Kleene star (), complementation (), intersection (), set difference (), and reversal ().

Question 2

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 :

eps-NFA for Union of 0* and 1*ε-NFA
eps-NFA for Union of 0* and 1* 1 0 ε ε s0 q0 q1
State01ε
→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 :

eps-NFA for Concatenation 0* 1*ε-NFA
eps-NFA for Concatenation 0* 1* 1 0 ε q0 q1
State01ε
→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 :

DFA for Complement (Not Ending in 0)DFA
DFA for Complement (Not Ending in 0) 1 0 0 1 1 0 q0 q1 q2
State01
→*q0q1q2
q1q1q2
*q2q1q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 11
  • ✓ accepts 001
  • ✓ accepts 111
  • ✓ rejects 0
  • ✓ rejects 10
  • ✓ rejects 00
  • ✓ rejects 110
  • ✓ rejects 010
Answer:

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 .

Question 3

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:

  1. Since and are regular, their complements and are regular.
  2. By closure under union, is regular.
  3. Taking the complement of that union, , is regular.
Answer:

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.

Question 4

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:

  1. (the first two substrings together have length at most )
  2. (the middle substring is non-empty, i.e., )
  3. 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.

Answer:

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 .

Question 5

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:

  1. Assume regularity: Assume is regular. By the Pumping Lemma, there must exist a pumping constant .
  2. Select test string: Choose a specific string whose length depends on such that .
  3. Examine all splits: Consider every possible split that satisfies and .
  4. 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.

Answer:

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 .

Question 6

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:

  1. 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).
  2. 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 .
  3. 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:

  1. Equivalence Problem ():
    • Construct the symmetric difference DFA for and test if .
  2. Containment Problem ():
    • Construct the DFA for and test whether its language is empty.
Answer:

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.

Question 7

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:

  1. Combine state spaces: Combine and into a single machine with state set (renaming states if necessary so that ).
  2. Set up comparison table: Create a lower-triangular grid listing all unordered pairs for distinct .
  3. Basis Step (Mark trivially distinguishable pairs): Mark every pair where exactly one state is accepting:
  1. 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.
  2. 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:

  1. Construct the product DFA recognizing the symmetric difference:
  1. In the product DFA, accepting states are .
  2. Test if using the reachability (emptiness) algorithm. if and only if no accepting state is reachable from .
Answer:

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.

Past exam questions for Theory of Computation

← Regular Expressions & Equivalence with Finite AutomataCFG, Derivations, Parse Trees & Ambiguity →