Regular Language Properties: Closure, Decision Tests, and Worked Examples

DFA questions, closure statements, and pumping-lemma proofs can look unrelated. Each one asks what finite memory can recognise or decide. Three kinds of tool answer it: constructions that build new regular languages from old ones, graph checks that decide emptiness and equivalence, and proofs that settle regularity in either direction.

1. Regular language properties: what the term covers

Over an alphabet such as Σ = {0,1}, a language is regular when a DFA, NFA, or regular expression describes it. Its properties cover closure under operations, decidable questions, and proof tools.

Keep three examples in view:

• L_even = {w ∈ {0,1}* | w contains an even number of 1s} needs two parity states.

• L_end0 = {w ∈ {0,1}* | w ends in 0} needs one state for "currently ends in 0" and another for "does not".

• L_equal = {0^n1^n | n ≥ 0} is not regular because matching two unbounded counts needs more than finite memory.

Every finite language is regular, while infinite languages may be regular or nonregular: {0, 01, 110} is finite and regular, 0*1* is infinite and regular, but L_equal is infinite and nonregular. If state tracing is unclear, revise Finite Automata: DFA vs NFA and Subset Construction first.

2. Closure properties, built instead of memorised

The closure properties of regular languages are easiest to remember through their constructions.

Build L_even ∩ L_end0. DFA A starts and accepts in E, with other state O; 0 stays put and 1 toggles E ↔ O. DFA B starts in non-final N and accepts in Z; from either state, 0 → Z and 1 → N.

Only q1 accepts the intersection. Trace 1010 as q0 --1→ q2 --0→ q3 --1→ q0 --0→ q1; it accepts with two 1s and a final 0. Trace 100 as q0 --1→ q2 --0→ q3 --0→ q3; it ends in 0 but rejects with one 1.

The same product proves more. For L_even ∪ L_end0, accept q0, q1, and q3. For L_even - L_end0, accept only q0. For complement, first agree on one alphabet, complete the DFA with a dead state, and only then flip finality.

3. Decision properties from paths, cycles, and products

Decision properties of regular languages reduce to finite checks:

• Membership: trace the input.

• Emptiness: check whether any final state is reachable from the start.

• Infiniteness: find a reachable cycle from which a final state remains reachable.

• Universality: complement a complete DFA and test emptiness.

• Equivalence: test whether the symmetric-difference product is empty.

• Inclusion L(A) ⊆ L(B): test whether L(A) ∩ complement(L(B)) is empty.

For an NFA, determinise when the check needs a complete DFA.

Consider the DFA for aa*b (one or more a’s followed by a single b). State q0 is the start, q2 is the only accept state, and qd is dead. Its transitions are q0: a→q1, b→qd; q1: a→q1, b→q2; q2: a→qd, b→qd; and qd: a→qd, b→qd.

For aab, trace q0→q1→q1→q2 proves membership. Emptiness is false because ab reaches q2. Infiniteness holds because the reachable a loop at q1 can reach q2 on b, generating a^m b for every m ≥ 1. Universality is false because b reaches qd. The loop at qd proves nothing about infiniteness, because no accepting state is reachable from it.

4. How to prove regularity, and how to disprove it

To prove regularity, exhibit a DFA, NFA, regular expression, or right-linear grammar, or apply closure to known regular languages. A few accepted strings prove nothing general.

For L_equal, assume it is regular and let its pumping length be p. Choose s = 0^p1^p, so |s| ≥ p. For every allowed split s = xyz with |xy| ≤ p and |y| > 0, y lies wholly inside the first zero block. Therefore y = 0^k for some 1 ≤ k ≤ p.

Pump down with i = 0. Then xz = 0^(p-k)1^p, which has p-k zeros and p ones. Since k ≥ 1, p-k < p, so xz ∉ L_equal. This contradiction proves that L_equal is nonregular.

The pumping lemma is necessary for regular languages, not sufficient. A correct disproof chooses a string from p, handles every permitted decomposition, then pumps to break membership. The proof above pumps down to i = 0; Regular Expressions and Pumping Lemma: Worked Proof states the three conditions in full and runs the pump-up version on a^n b^n.

5. Myhill-Nerode as a state lower-bound tool

Two prefixes need different DFA states when some continuation makes one completed string accepted and the other rejected. A regular language has finitely many such distinguishable classes, and their number equals the state count of its minimal DFA.

For L_mod3, where the number of 1s is divisible by 3, prefixes ε, 1, and 11 represent residues 0, 1, and 2. Distinguish ε from 1 using suffix 11: 11 is rejected, while 111 is accepted. Distinguish ε from 11 using the empty suffix. Distinguish 1 from 11 using suffix 1: again, 11 is rejected and 111 is accepted. Any DFA therefore needs at least three states.

A matching DFA has r0, r1, and r2; r0 starts and accepts, 0 leaves every state unchanged, and 1 cycles r0→r1→r2→r0. Thus three states are both sufficient and necessary. 10101 contains three 1s and ends at r0, so it is accepted. 1100 contains two and ends at r2, so it is rejected.

6. Traps that make correct-looking answers fail

Separate regular 0*1*, which permits unequal block lengths, from nonregular {0^n1^n}, which requires equal counts. A cycle proves infiniteness only if reachable and able to lead to acceptance. Complement is relative to a stated alphabet, so Σ={0,1} and Σ={0,1,2} are different universes.

7. How GATE-style questions test regular language properties

Typical prompts ask you to judge closure, trace a product automaton, test emptiness or equivalence, find a pumping-proof flaw, or justify a minimum state count. Try these checks:

1. L1 ∩ complement(L2) is regular when both languages are regular over the same alphabet, by complement and intersection closure.

2. The product above accepts 1010 and rejects 100, as its two traces show.

3. {0^n1^n} needs a nonregularity proof, not a DFA sketch.

4. The modulo-3 language needs exactly three states, by a three-class lower bound and a three-state construction.

5. A dead-state self-loop does not prove infiniteness because it cannot reach acceptance.

Use this solving order: write the alphabet and condition, choose a construction, graph check, or proof tool, test boundary strings including ε, then state why the result follows. For the rest of the Theory of Computation syllabus in exam order, start from the GATE CS exam preparation category.

8. Short version, practice set, and next step

DFA, NFA, and regular expressions are equivalent. Closure builds regular languages. Reachability, productive cycles, and products answer decision questions. Automata and closure prove regularity; pumping and Myhill-Nerode prove nonregularity or state lower bounds.

Predict before reading each answer:

1. In L_even - L_end0, only q0 accepts. Hence ε and 11 are accepted, while 110 is rejected.

2. The language of the DFA for aa*b is infinite because the q1 loop is productive.

3. Odd 0 parity combined with even 1 parity needs a four-state 2×2 product.

4. The split x=ε, y=0, z=0^(p-1)1^p is only one split. The proof above covers every y=0^k permitted by |xy|≤p.

For a structured exam route, use GATE Guidance by Sanchit Sir. For core CS coverage across multiple exams, consider the ZERO TO HERO complete CS course. Keep the practical sequence fixed: construct → trace → justify.