Properties of Regular Languages

Closure properties

The regular languages are closed under an operation if applying it to regular languages always gives a regular language. They are closed under nearly everything:

The last two rows explain some GATE traps: every finite language is regular, but a subset or an infinite union of regular languages need not be.

Closure gives quick proofs. If L ∩ a*b* is not regular, then L is not regular either (otherwise the intersection would be regular). For example, L = { w | w has equally many a's and b's } is not regular, because L ∩ a*b* = {aⁿbⁿ}.

The pumping lemma

A DFA with p states that reads a string of length ≥ p must visit some state twice, so the part of the string read between the two visits forms a loop that can be repeated or skipped. This gives a property that every regular language has:

The lemma is used in the contrapositive, to prove that a language is not regular. The proof is a game against an opponent:

1. The opponent picks p.
2. You pick a string s ∈ L with |s| ≥ p (choose it cleverly).
3. The opponent picks any split xyz satisfying conditions 1 and 2.
4. You pick an i with xyⁱz ∉ L.

If you can always win, L is not regular.

Example: L = {0ⁿ1ⁿ | n ≥ 0} is not regular. Pick s = 0ᵖ1ᵖ. Because |xy| ≤ p, both x and y lie inside the block of 0s, so y = 0ᵏ with k ≥ 1. Then xy²z = 0ᵖ⁺ᵏ1ᵖ has more 0s than 1s, so it is not in L.

The program below plays the opponent's side for p = 4: it tries every legal split of 0⁴1⁴ and shows that pumping up (i = 2) always leaves the language:

def in_L(w):
    n = len(w) // 2
    return w == "0" * n + "1" * n

p = 4
s = "0" * p + "1" * p
for xy_len in range(1, p + 1):
    for y_len in range(1, xy_len + 1):
        x, y, z = s[:xy_len - y_len], s[xy_len - y_len:xy_len], s[xy_len:]
        pumped = x + y * 2 + z
        print(f"x={x or 'ε':4} y={y:4} -> xy²z = {pumped:12} in L? {in_L(pumped)}")

x=ε    y=0    -> xy²z = 000001111    in L? False
x=0    y=0    -> xy²z = 000001111    in L? False
x=ε    y=00   -> xy²z = 0000001111   in L? False
x=00   y=0    -> xy²z = 000001111    in L? False
x=0    y=00   -> xy²z = 0000001111   in L? False
x=ε    y=000  -> xy²z = 00000001111  in L? False
x=000  y=0    -> xy²z = 000001111    in L? False
x=00   y=00   -> xy²z = 0000001111   in L? False
x=0    y=000  -> xy²z = 00000001111  in L? False
x=ε    y=0000 -> xy²z = 000000001111 in L? False

Other languages proved non-regular the same way: {aⁿ² | n ≥ 0} (the gaps between squares grow), {aᵖ | p prime}, {wwᴿ} (palindromes of even length), {ww}.

Decision problems

For regular languages (given as DFAs, NFAs or REs), all the natural questions can be answered by an algorithm:

Is it regular? A checklist

A finite automaton has only finitely many states, so it can count only up to a fixed bound, or modulo a fixed number. That is the key test: does recognising the language require unbounded counting or comparing?

The row { wxwᴿ } is a classic trap: since w may be a single symbol and x can absorb everything else, the language is simply the strings of length ≥ 3 that start and end with the same symbol.

Practice questions