2.1Regular expressions and identities
The idea
A regular expression describes a language with union, concatenation and star. Identities let you simplify or test equality.
Think of it like this: Shorthand for lists of strings: "ab*" means an a followed by any number of b's.
Why it exists
GATE often asks whether two regexes are equal, or which of four regexes matches a language.
How it works
- + is union, juxtaposition is concatenation, * is zero or more.
- Test equality with short strings that distinguish them (e.g. "ab" or "aab").
- Use identities: R + R = R, (R*)* = R*, ε + RR* = R*, (R + S)* = (R*S*)*.
- Watch out: (R + S)* is not R* + S*.
Worked example: (a + b)* versus (a*b*)*
(a*b*)* can produce any single a or b and then repeat, so it equals (a + b)*: both generate every string.
Now play with it
- →Answer the equal / not equal questions below and read each explanation.
Are the two regular expressions equal? · question 1 of 7
(a + b)* vs (a*b*)*
Check yourself
Which is NOT equal to (a + b)*?
Exam notes (the dense version)
Regexes are built from ∅, ε, symbols, union (+), concatenation and star. Useful identities: R + R = R, (R*)* = R*, ε + RR* = R*, (R + S)* = (R*S*)* = (R* + S*)*, R(SR)* = (RS)*R, ∅* = ε, R∅ = ∅.
Previous year questions: Regular Expressions & Regular Languages (14)
PYQs are grouped by topic, so this is the full set for Regular Expressions & Regular Languages; try the ones that match this subtopic. Open all 14 on the topic page.