Algorithms for regular languages

1. Is a subset of a regular language always regular?
   Stuck? Peek at 2.4.1 Closure properties of regular languages

   • Closed: ∪ ∩ − complement, concat, *, ⁺, reversal, homomorphism, inverse homomorphism, quotient (by any language), prefix, suffix, substring, substitution, finite ∪/∩.
   • Not guaranteed: infinite ∪/∩, subset, superset.
   • Prove non-regular: L ∩ R non-regular (R regular) ⇒ L non-regular.

   Read lesson 2.4.1

2. When is L(M) infinite, in graph terms?
   Stuck? Peek at 1.1.2 Extended transition function and regular languages

   • δ̂(q, ε) = q; δ̂(q, wa) = δ(δ̂(q, w), a); δ̂(q, xy) = δ̂(δ̂(q, x), y).
   • L(M) = { w : δ̂(q₀, w) ∈ F }. Regular ⇔ accepted by some DFA. All finite languages are regular.
   • From the graph: empty ⇔ no reachable final; Σ* ⇔ all reachable states final; infinite ⇔ cycle on a path start→final.
   • Prove correctness with state meanings + induction on |w|.

   Read lesson 1.1.2

3. How many states does the minimal DFA have, and is it unique?
   Stuck? Peek at 1.3.3 Myhill–Nerode theorem

   • x ≡_L y ⇔ ∀z: xz ∈ L ⇔ yz ∈ L. Right-invariant equivalence.
   • L regular ⇔ finite index; index = #states of minimal DFA (incl. dead class).
   • Infinitely many pairwise distinguishable strings ⇒ not regular. aⁿbⁿ: strings aⁱ separated by bⁱ.

   Read lesson 1.3.3

A compiler team wants a tool that checks their token patterns: “Does this pattern match anything at all? Does it match infinitely many strings? Are these two patterns the same?”. For regular languages every one of these questions has a procedure that always finishes with the right answer. Later phases will show that for stronger machines, some of these questions have no such procedure at all — so this list is worth knowing exactly.

A DFA has n states. To check whether its language is infinite by testing strings, which lengths would you need to test?

Prediction check

Lengths n to 2n − 1. If any string of those lengths is accepted, its run repeats a state (pigeonhole), so there is a loop you can pump forever ⇒ infinite. Conversely, if L is infinite it contains such a string. (The graph method is faster: look for a cycle on a path from q₀ to F.)

Membership: is w ∈ L?

Run the DFA on w: |w| steps. (From an NFA: track the set of states. From a regex: convert first.)

Emptiness: is L = ∅?

L(M) = ∅ iff no accepting state is reachable from q₀ — BFS on the diagram. Equivalent test: L ≠ ∅ iff M accepts some string of length < n.

Finiteness: is L finite?

Remove states that are unreachable or cannot reach F (“useless”). L is infinite iff the remaining graph has a cycle. Or: test lengths n … 2n − 1.

Universality: is L = Σ*?

Complement the (complete) DFA and test emptiness. Equivalently: every reachable state is accepting.

Equivalence: L(M₁) = L(M₂)?

Two methods: (1) minimize both and compare (unique minimal DFA); (2) build the product for the symmetric difference (L₁ − L₂) ∪ (L₂ − L₁) and test emptiness. Containment L₁ ⊆ L₂: test L₁ ∩ L̅₂ = ∅.

Cost notes

From an NFA, emptiness and membership stay cheap; complement-based questions (universality, equivalence) may need the subset construction first, which can be exponential. GATE asks only whether a procedure exists, and for regular languages the answer is always yes.

Putting it together

• Membership, emptiness, finiteness, universality, equivalence and containment all have always-terminating algorithms for regular languages.
• Most reduce to reachability in a (product) DFA.
• From NFAs, complement-based questions may need the subset construction first.

question            procedure (DFA with n states)                   always terminates?
 w ∈ L ?            run the DFA, |w| steps                          ✔
 L = ∅ ?            BFS: is some accepting state reachable?         ✔
 L finite ?         trim useless states, look for a cycle           ✔
 L = Σ* ?           complement, then emptiness                      ✔
 L₁ = L₂ ?          minimize & compare, or symmetric diff empty     ✔
 L₁ ⊆ L₂ ?          L₁ ∩ complement(L₂) = ∅                         ✔

We can answer questions about a given regular language. But how do we prove a language is not regular when no DFA is given? Myhill–Nerode is one tool; the pumping lemma — built on pigeonhole — is the one GATE expects. Next.

1. MCQ

   L(M) is empty iff:

   1. M has no accepting state
   2. no accepting state is reachable from q₀
   3. M has a dead state
   4. M has a cycle
2. NAT

   For a DFA with 6 states, testing lengths from n to 2n−1 means checking strings of lengths 6 to what?

   Write your answer before opening the key.

3. MSQ

   For DFAs M₁, M₂, which are answerable by an always-terminating algorithm?

   1. L(M₁) = L(M₂)?
   2. L(M₁) ⊆ L(M₂)?
   3. Is L(M₁) finite?
   4. Is L(M₁) ∩ L(M₂) = ∅?
4. MCQ

   To test universality (L = Σ*) of a DFA:

   1. test if q₀ ∈ F
   2. complement and test emptiness
   3. test for a cycle
   4. minimize and count states

• emptiness test
• finiteness test
• universality test
• equivalence test
• containment test
• useless state (cannot reach F)
• always-terminating algorithm

1. How to test L(M) = ∅?
   Reveal answer

   Check whether any accepting state is reachable from q₀.
2. How to test L(M) finite?
   Reveal answer

   Remove useless states; infinite iff a cycle remains.
3. How to test L₁ = L₂ for DFAs?
   Reveal answer

   Minimize and compare, or check the symmetric difference is empty.