Regular Language Properties: Formula Sheet and Revision Notes for GATE CS
Keep each regular-language rule beside its conditions. Revise identities, trace a product DFA and practise the quantifier order that makes a pumping-lemma proof work.
KnowledgeGate Team
Exam prep & CS education

Remembering the closure table is easy; remembering when a rule applies takes more care. A missing transition or a wrongly chosen pumping split can spoil an otherwise correct answer. This regular-language revision sheet pairs rules with conditions and uses, then checks them through a small construction and a non-regularity proof.
Regular languages: definitions and identities to recall
An alphabet Sigma is a finite set of symbols; Sigma* contains all finite strings over it. The empty string epsilon has length zero, while the empty set contains no strings. Concatenation AB = {uv : u in A, v in B}; L* = union over k>=0 L^k, with L^0 = {epsilon}.
DFAs, NFAs, regular expressions and regular grammars describe exactly the regular languages. Choose whichever makes regularity easiest to establish. For fuller explanations, read Decision Properties of Regular Languages: DFA Tests. Keep each identity beside its construction condition, then use the compact revision routine.
Identity | Condition and use |
|---|---|
L union empty set = L | Any L; remove an empty alternative. |
L times empty set = empty set times L = empty set | Any L; concatenation needs a string from both operands. |
L times {epsilon} = {epsilon} times L = L | Any L; epsilon adds no symbols. |
(empty set)* = {epsilon} | Zero repetitions still contribute epsilon. |
{epsilon}* = {epsilon} | Repeating epsilon changes nothing. |
L+ = LL* | Any L; express one or more repetitions. |
Thus empty set and {epsilon} differ: their sizes are zero and one. Every finite language is regular, for example {0,11}; regular languages can also be infinite, like 0*.
Closure formula sheet: conditions beside each rule
Here A and B are regular languages over the same fixed alphabet Sigma.
Operation | Condition and construction | When to use |
|---|---|---|
A union B, A intersection B | Product DFA; accept either, or both, components respectively. | Combine alternatives or requirements. |
A-B | Product DFA; accept A and reject B. | Exclude forbidden strings. |
A symmetric-difference B = (A-B) union (B-A) | Product DFA; accept exactly one component. | Find disagreements. |
Sigma* - A | Swap final/non-final states in a complete DFA. | Negate a condition. |
AB, A* | Use epsilon-NFA constructions. | Sequence or repeat patterns. |
A-reversal | Reverse NFA edges; old start becomes final, new epsilon-start enters old finals. | Reverse accepted strings. |
h(A) | Replace symbols by their homomorphic images. | Encode or erase symbols. |
h-inverse(A) | Simulate the image of each input symbol. | Recognise inputs whose images belong to A. |
A homomorphism h maps each symbol to a string and extends by concatenation. For h(0)=ab and h(1)=epsilon, h(01)=abepsilon=ab and h(10)=epsilonab=ab, so h({01,10})={ab}.
Finite unions and intersections preserve regularity; arbitrary infinite ones need not. The union union over n>=0 {0^n1^n} is non-regular although each singleton is regular.
Product DFAs with m and n states have at most mn states; an n-state NFA gives at most 2^n subsets. These are upper bounds, not minimum-state claims. Review Closure Properties of Regular Languages: Operations and DFA for the constructions. Use the construction toolbox together with decision and pumping checks during revision.
Worked product DFA: even-length strings ending in one
Take A to accept even-length strings and B to accept strings ending in 1. A has parity states E (even) and O (odd); B has N (not ending in 1, including epsilon) and Y (ending in 1).
Pairing them gives four states EN, EY, ON and OY. Start at EN and accept only EY, because the string must have even length and end in 1.
State | Input 0 | Input 1 |
|---|---|---|
EN | ON | OY |
EY | ON | OY |
ON | EN | EY |
OY | EN | EY |
Trace 0111: EN -> ON -> EY -> OY -> EY, so the string is accepted. Trace 1010: EN -> OY -> EN -> OY -> EN, so it is rejected because it ends in 0. The construction uses 2 x 2 = 4 product states; it is not a minimum-state claim.
Decision tests: reduce the question to reachability
Question | Test and use |
|---|---|
Is w in A? | Simulate w; check the final state. |
Is A empty? | Check that no accepting state is reachable from the start. |
Is A universal? | For a complete DFA, test whether its complement is empty. |
Is A subseteq B? | Test A-B for emptiness; find any containment violation. |
Is A=B? | Test A symmetric-difference B for emptiness; find any distinguishing input. |
A DFA accepts infinitely many strings iff a directed cycle is reachable from the start and can reach an accepting state. In the worked DFA, EN -> OY -> EY on 11, and EY and OY form a 1-cycle. Hence 11, 1111, 111111, ... are accepted. A reachable dead-state loop alone proves nothing about infinity of the accepted language.
Pumping lemma: preserve the quantifier order
If L is regular, there exists p >= 1 such that every w in L with |w| >= p has some split w = xyz satisfying |xy| <= p, |y| >= 1 and xy^i z in L for every integer i >= 0.
For L = {0^n1^n2^n : n >= 0}, assume regularity and choose its pumping length p. Let w = 0^p1^p2^p. Every legal y lies inside the first p zeros, so y = 0^k for some 1 <= k <= p. Choose i = 0: xz = 0^(p-k)1^p2^p. The three blocks no longer have equal counts, so xz is outside L. This contradicts the lemma for every legal split.
For illustration only, set p = 3 and split 000111222 as x = 0, y = 00, z = 111222. Then |xy| = 3 and |y| = 2. Pumping down gives xz = 0111222, with 1 zero, 3 ones and 3 twos. Pumping up gives xyyz = 00000111222, with 5 zeros, 3 ones and 3 twos. Neither string belongs to L.
Revision traps and the repair for each
Complement: swapping finals in an incomplete DFA misses absent transitions. Add a rejecting sink and complete first. For an NFA, determinise and complete before swapping finals.
Quantifiers: one convenient split failing does not refute the lemma. Constrain every legal y. Failure to find a contradiction does not prove regularity; construct a recogniser or expression, or apply closure.
Operands: a regular result need not have regular operands. With N={0^n1^n : n>=0}, N union Sigma*=Sigma* is regular although N is not.
Language classes and bounds: do not transfer context-free non-closure rules to regular languages, or mistake construction bounds for proven minima.
How exam questions test these rules
The IIT Guwahati GATE 2026 CS syllabus, Section 6 includes finite automata, regular expressions and languages, and pumping lemma. Exam-style checks apply the rules in three common ways:
Does epsilon belong to (empty set)*? Yes: zero-fold concatenation contributes epsilon.
Is 2^5 = 32 necessarily the minimal DFA size for a five-state NFA? No: it is a subset-construction upper bound.
Is equality of regular languages decidable? Yes: test symmetric-difference emptiness.
Use GATE CS preparation resources to organise this topic within broader revision.
Short version and the next revision step
Construct to prove regularity. Use complete DFAs for complement and product reasoning. Respect every legal split when disproving regularity with pumping.
Try a ten-minute revision: three minutes to recreate the closure table, four to trace the product DFA and three to reproduce the pumping proof. For an optional structured-preparation next step, explore GATE Guidance by Sanchit Sir.
Keep learning
C Fundamentals Formula Sheet for GATE CS: Rules, Traces and Revision Notes
Revise the C rules that most often change an answer. Use compact tables, worked traces, address formulas, memory notes, and a practical error checklist.
Regular Expressions Formula Sheet: Rules, Worked Examples and Revision Notes
Remembering the symbols is only the first step. Use these identities, language templates and a complete ending-01 DFA example to check what a regular expression actually generates.
Lexical Analysis Formula Sheet: Tokens, Regular Expressions and DFA Revision Notes
Keep the rules that matter under time pressure in one place, then apply them to regex counting, DFA construction, a 17-character scanner trace, and fallback.
Grammar and CFG Formula Sheet: Rules, Worked Example and GATE Revision Notes
Revise CFGs in problem-solving order through precise rules, use cues, one consistent worked grammar, an LL(1) table, normal forms and a final audit routine.





