Regular Expressions & Equivalence with Finite Automata
Open in the Padhaiko app2.5 Regular Expressions and Regular Languages
Inductive Definition of Regular Expressions and L(α)
Let be a finite alphabet. The regular expressions over and the languages they denote via the interpretation function are defined inductively as follows:
- Basis:
- is a regular expression denoting the empty language: .
- is a regular expression denoting the empty-string language: .
- Each symbol is a regular expression denoting the singleton language: .
- Induction: If and are regular expressions over , then:
- Concatenation: is a regular expression with .
- Union (Alternation): (also written ) is a regular expression with .
- Kleene Star (Closure): is a regular expression with .
- Extremal Clause: Nothing is a regular expression over unless it is obtained by a finite number of applications of rules (1) and (2).
A language is called a regular language if and only if for some regular expression over .
Algebraic Laws for Regular Expressions
For any regular expressions (or languages) :
| Law Category | Identities |
|---|---|
| Commutative & Associative Laws | , , |
| Identities & Annihilators | , , |
| Distributive Laws | , |
| Idempotent Law | |
| Closure Laws | , , , , |
Applications of Regular Expressions
- Regular Expressions in UNIX / POSIX:
.(dot) matches any single character.[A-Z]matches any uppercase ASCII letter;[A-Za-z0-9]matches any alphanumeric character.- A character class is shorthand for the union .
[+-0-9.]matches sign characters, digits, and the decimal point.
- Lexical Analysis in Compilers: The lexical analyzer (scanner) uses regular-expression specifications to partition source code into tokens (identifiers, keywords, numeric constants, operators, and punctuation).
- Pattern Matching & Text Search: Utilities such as
grep, text editors, and web-search indexers use regular expressions to locate patterns in large text corpora.
Worked Out Examples on Regular Expressions & Equivalence (Book Examples 2.14–2.17)
Writing Regular Expressions for 10 Languages
Write a regular expression for each of the following languages:
- .
- Strings over having length exactly 3.
- Strings over having length at least 3.
- Strings over having length at most 3.
- Strings over containing an odd number of zeros.
- Strings over having even length.
- Strings where the number of 's in is divisible by 3.
- All strings in with more than 2 's (at least three 's).
- Strings over ending with
0and not containing11as a substring. - Strings over containing an even number of zeros.
- Item 1 (even 's followed by odd 's): Pairs of 's are generated by , and an odd number of 's is :
- Item 2 (length exactly 3): Each of the 3 positions is :
- Item 3 (length at least 3): Three mandatory symbols followed by any string in :
- Item 4 (length at most 3): Union of lengths and :
- Item 6 (even length over ): Concatenation of zero or more 2-bit blocks:
- Item 5 (odd number of zeros): One mandatory
0(surrounded by arbitrary 's) followed by any number of pairs of0's:
- Item 7 (number of 's divisible by 3): Either zero 's () or a positive multiple of three 's interspersed with 's:
- Item 8 (more than two 's, i.e., at least three 's):
- Item 9 (ending with
0and no11substring): Every1must be immediately followed by0, so every non-empty valid string is a sequence of0and10blocks:
- Item 10 (even number of zeros): Zero
0's () or pairs of0's interspersed with 's:
- ; 2. ; 3. ; 4. ; 5. ; 6. ; 7. ; 8. ; 9. ; 10. .
2.6 Equivalence of Regular Expression and Finite Automata
1. Conversion from Regular Expression to Finite Automata (Thompson's Construction)
Every regular expression can be systematically converted into an equivalent -NFA by building basic 2-state machines for symbols and combining them inductively using -transitions for concatenation, union, and Kleene star.
Construct an ε-NFA for (ab ∪ ba)*
Construct a non-deterministic finite automaton for the regular expression .
First construct 2-state -NFAs for () and (), then connect them in series with an -transition to form () and ().
Add a branching state 0 with -transitions to 1 and 5:
| State | a | b | ε |
|---|---|---|---|
| →0 | ∅ | ∅ | {1, 5} |
| 1 | {2} | ∅ | ∅ |
| 5 | ∅ | {6} | ∅ |
| 2 | ∅ | ∅ | {3} |
| 3 | ∅ | {4} | ∅ |
| *4 | ∅ | ∅ | ∅ |
| 6 | ∅ | ∅ | {7} |
| 7 | {8} | ∅ | ∅ |
| *8 | ∅ | ∅ | ∅ |
- Machine-checked
- ✓ accepts ab
- ✓ accepts ba
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aa
- ✓ rejects bb
- ✓ rejects abab
Introduce a new initial/accepting state s with , and add feedback -transitions from the final states 4 and 8 back to 0:
| State | a | b | ε |
|---|---|---|---|
| →*s | ∅ | ∅ | {0} |
| 0 | ∅ | ∅ | {1, 5} |
| 1 | {2} | ∅ | ∅ |
| 5 | ∅ | {6} | ∅ |
| 2 | ∅ | ∅ | {3} |
| 3 | ∅ | {4} | ∅ |
| *4 | ∅ | ∅ | {0} |
| 6 | ∅ | ∅ | {7} |
| 7 | {8} | ∅ | ∅ |
| *8 | ∅ | ∅ | {0} |
- Machine-checked
- ✓ accepts ε
- ✓ accepts ab
- ✓ accepts ba
- ✓ accepts abba
- ✓ accepts baab
- ✓ accepts abab
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aa
- ✓ rejects bb
- ✓ rejects aba
- ✓ rejects bab
The -NFA has start state s, accepting states , forward paths and , and feedback loops and .
2. Conversion from Finite Automata to Regular Expression (Arden's Theorem)
Arden's Theorem
Let and be two regular expressions over . If does not contain the empty string (), then the regular-expression equation
has a unique solution, given by
Proof: Substituting into the right-hand side repeatedly gives
Procedure for Converting a Finite Automaton to a Regular Expression: Assume the automaton has no -transitions and a single initial state .
- Write State Equations: For each state (), write an equation expressing all incoming transitions to :
where is the union of labels on edges from to (or if no edge exists).
- Eliminate States via Substitution & Arden's Theorem: Solve the system of equations using and algebraic identities until each final state is expressed purely as a regular expression over . The union of expressions for all is the regular expression for .
DFA to Regular Expression via Arden's Theorem
Construct a regular expression corresponding to the automaton given below:
| State | a | b |
|---|---|---|
| →*q1 | q1 | q2 |
| q2 | q3 | q2 |
| q3 | q1 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts a
- ✓ accepts aa
- ✓ accepts baa
- ✓ accepts bbaa
- ✓ accepts babaa
- ✓ rejects b
- ✓ rejects ba
- ✓ rejects bb
- ✓ rejects aba
- ✓ rejects baaab
Since is both the initial state and the final state:
Substitute into equation (2):
Comparing with where and (), Arden's Theorem gives:
Applying Arden's Theorem with and :
.
3-State Binary DFA to Regular Expression
Construct a regular expression corresponding to the automaton given below:
| State | 0 | 1 |
|---|---|---|
| →q1 | q1 | q2 |
| *q2 | q2 | q3 |
| q3 | q3 | q3 |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 00100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 11
- ✓ rejects 0101
Here is the initial state and is the final state:
From equation (1), . Substituting into equation (2):
.
Solutions to Important Questions (Questions 24–36, Book pp. 122–129)
Important Question 24 — At Least One 'a' and Two 'b's [2082 Kartik]
Write a regular expression that generates all strings containing at least one a and at least two b's over .
In any valid string, the required three symbols (a, b, b) can appear in three relative orders—a...b...b, b...a...b, or b...b...a—with arbitrary strings from before, between, and after them:
.
Important Question 25 — At Least One 'a' or At Least One 'b' [2076 Ashwin]
Determine a regular expression for .
A string over contains at least one a or at least one b if and only if its length is at least ():
.
Important Question 26 — Strings Starting and Ending with the Same Symbol [2075 Chaitra]
Write a regular expression for the language in which strings start and end with the same symbol over .
Strings of length (a and b) trivially start and end with the same symbol; strings of length have the form or (including if vacuously permitted):
(or for non-empty strings).
Important Question 27 — Strings Starting and Ending with Different Symbols [2075 Ashwin]
Write a regular expression for the language in which strings start and end with different symbols over .
Either the string begins with a and ends with b, or it begins with b and ends with a:
.
Important Question 28 — Even Number of a's Followed by Odd Number of b's [2073 Chaitra]
Write a regular expression for an even number of 's followed by an odd number of 's over .
An even number of 's is , and an odd number of 's is :
.
Important Question 29 — Strings with 0101 as Substring [2072 Chaitra]
Find the regular expression for .
0101 between arbitrary binary strings.
Important Question 30 — Strings with No More Than Three a's [2072 Kartik]
Write a regular expression for all strings in with no more than three 's.
a.
Important Question 31 — Regex for Even a's Followed by Odd b's and DFA for (ab + aba)* [2081 Bhadra]
- Write a regular expression for .
- Design a DFA for the language , and check whether is accepted or not.
For part 1, . For part 2, the 5-state DFA has , start state , accepting states , and dead state :
| State | a | b |
|---|---|---|
| →*q0 | q1 | q4 |
| q1 | q4 | q2 |
| q4 | q4 | q4 |
| *q2 | q3 | q4 |
| *q3 | q1 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts ab
- ✓ accepts aba
- ✓ accepts abab
- ✓ accepts abaab
- ✓ accepts ababaab
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aa
- ✓ rejects abb
- ✓ rejects baba
, and ends in and is accepted.
Important Question 32 — Convert L = b(baa ∪ aba)* to NFA and DFA [2079 Bhadra]
Convert the regular expression into an NFA and then into an equivalent DFA.
After reading the initial b from to (accepting), the machine can loop through baa () or aba (), with :
| State | b | a |
|---|---|---|
| →q0 | {q1} | ∅ |
| *q1 | {q2} | {q4} |
| q2 | ∅ | {q3} |
| q4 | {q3} | ∅ |
| q3 | ∅ | {q5} |
| *q5 | {q2} | {q4} |
- Machine-checked
- ✓ accepts b
- ✓ accepts bbaa
- ✓ accepts baba
- ✓ accepts bbaabaa
- ✓ accepts babaaba
- ✓ accepts bbaaaba
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects ba
- ✓ rejects bb
- ✓ rejects bab
- ✓ rejects bba
phi)Since every state in the NFA above has at most one outgoing transition per symbol, subset construction yields singleton states plus the dead state :
(q0) | ||
(q1) | ||
(q2) | ||
(q3) | ||
(q4) | ||
(q5) | ||
(phi) |
| State | a | b |
|---|---|---|
| →q0 | phi | q1 |
| phi | phi | phi |
| *q1 | q4 | q2 |
| q4 | phi | q3 |
| q2 | q3 | phi |
| q3 | q5 | phi |
| *q5 | q4 | q2 |
- Machine-checked
- ✓ accepts b
- ✓ accepts bbaa
- ✓ accepts baba
- ✓ accepts bbaabaa
- ✓ accepts babaaba
- ✓ accepts bbaaaba
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects ba
- ✓ rejects bb
- ✓ rejects bab
- ✓ rejects bba
The DFA has states with accepting states and .
Important Question 33 — DFA for R = (01 ∪ 010)* [2078 Kartik, 2073 Kartik]
Design a DFA that accepts the language defined by the regular expression .
Isomorphic to (with and ), the DFA has , start state , accepting states , and dead state :
| State | 0 | 1 |
|---|---|---|
| →*q0 | q1 | q4 |
| q1 | q4 | q2 |
| q4 | q4 | q4 |
| *q2 | q3 | q4 |
| *q3 | q1 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 01
- ✓ accepts 010
- ✓ accepts 0101
- ✓ accepts 01001
- ✓ accepts 0101001
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 00
- ✓ rejects 011
- ✓ rejects 101
.
Important Question 34 — NFA and DFA for (ab ∪ bb)*a [2075 Chaitra]
Construct an NFA and convert it to its corresponding DFA for the regular expression .
Let , , and :
| State | a | b |
|---|---|---|
| →q0 | {q1} | {q4} |
| *q1 | ∅ | {q2} |
| q4 | ∅ | {q2} |
| q2 | {q3} | {q4} |
| *q3 | ∅ | {q2} |
- Machine-checked
- ✓ accepts a
- ✓ accepts aba
- ✓ accepts bba
- ✓ accepts ababa
- ✓ accepts abbba
- ✓ accepts bbbba
- ✓ rejects ε
- ✓ rejects b
- ✓ rejects aa
- ✓ rejects ab
- ✓ rejects bb
- ✓ rejects abb
phi) (q0) | ||
(q1) | ||
(q4) | ||
(q2) | ||
(q3) | ||
(phi) |
| State | a | b |
|---|---|---|
| →q0 | q1 | q4 |
| *q1 | phi | q2 |
| q4 | phi | q2 |
| phi | phi | phi |
| q2 | q3 | q4 |
| *q3 | phi | q2 |
- Machine-checked
- ✓ accepts a
- ✓ accepts aba
- ✓ accepts bba
- ✓ accepts ababa
- ✓ accepts abbba
- ✓ accepts bbbba
- ✓ rejects ε
- ✓ rejects b
- ✓ rejects aa
- ✓ rejects ab
- ✓ rejects bb
- ✓ rejects abb
The equivalent DFA has states with accepting states and .
Important Question 35 — NFA for (ab*a ∪ b*aa) [2073 Shrawan]
Construct an NFA for the language , and provide two accepted strings and two rejected strings.
Let , , and :
- Upper branch for : (when zero 's occur) and (when one or more 's occur).
- Lower branch for : (when zero 's occur) and (when one or more 's occur).
| State | Symbol | Symbol |
|---|---|---|
| State | a | b |
|---|---|---|
| →q0 | {q1} | {q4} |
| q1 | {q6} | {q2} |
| q4 | {q5} | {q4} |
| q2 | {q3} | {q2} |
| *q6 | ∅ | ∅ |
| *q3 | ∅ | ∅ |
| q5 | {q6} | ∅ |
- Machine-checked
- ✓ accepts aa
- ✓ accepts aba
- ✓ accepts abbba
- ✓ accepts baa
- ✓ accepts bbaa
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ab
- ✓ rejects abab
- ✓ rejects bba
'abab' and accepted string 'abbba'- For
"abab":
(A second rejected string is "ab", which ends in .)
- For
"abbba":
(A second accepted string is "baa", via .)
Accepted strings: "abbba", "baa"; rejected strings: "abab", "ab".
Important Question 36 — Obtain Regular Expression for 4-State DFA [2082 Kartik]
Obtain the regular expression for the given automaton:
| State | 0 | 1 |
|---|---|---|
| →*A | B | C |
| B | D | A |
| C | A | D |
| D | D | D |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 0110
- ✓ accepts 1001
- ✓ accepts 0101
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 00
- ✓ rejects 11
- ✓ rejects 0011
Here is both the start state and the sole final state, while is a non-accepting trap state:
Comparing with where and , Arden's Theorem yields:
.
Exercises
Exercises
Define regular expression. [2079 Baishakh, 2079 Bhadra, 2076 Chaitra, 2076 Ashwin]
Formal inductive definition of regular expressions: Let be a finite alphabet. The regular expressions over and the formal languages they denote () are defined recursively:
- Basis Step:
- is a regular expression denoting the empty set: .
- is a regular expression denoting the language containing only the empty string: .
- For each symbol , is a regular expression denoting the singleton language: .
- Inductive Step: If and are regular expressions denoting languages and respectively, then:
- or is a regular expression denoting Union:
- is a regular expression denoting Concatenation:
- is a regular expression denoting Kleene Closure:
- Closure Step: Nothing else is a regular expression over .
Precedence conventions: To avoid excessive parentheses, regular expression operators follow the standard precedence hierarchy (from highest to lowest):
- Kleene Star () (binds tightest)
- Concatenation ()
- Union ( or ) (binds loosest)
Illustrative examples:
- : The language of all binary strings ending with
01. - : Strings composed exclusively of an even number of
0's or an even number of1's. - : Strings beginning with , terminating with , and having alternating segments.
Over an alphabet , the regular expressions are defined inductively: (i) , , and each are regular expressions; (ii) if and are regular expressions, then (concatenation), (union), and (Kleene star) are regular expressions; (iii) nothing else is a regular expression.
State and prove Arden's Theorem for regular expressions, and state the assumptions required to apply it to a finite automaton.
Statement of Arden's Theorem: Let and be two regular expressions over an alphabet . If (meaning does not contain the empty string ), then the linear equation:
has the unique solution:
Proof that is a solution: Substitute into the right-hand side of the equation :
Thus, satisfies the equation.
Proof of uniqueness: Repeatedly substitute the equation back into the term on the right-hand side:
Because , every string in has length at least . Consequently, every string in has length at least . Now consider any string of length . For any , no string in can have length . Therefore, if and only if . This proves that is the unique solution.
Assumptions required to apply Arden's Theorem to a Finite Automaton: When using Arden's theorem to find the regular expression of a finite automaton:
- Single start state: The automaton must have a single start state , whose equation includes the term (representing the empty string read before moving, i.e., ).
- No -transitions: The state transition graph must not contain -transitions (or -cycles).
- Condition : For each diagonal equation , the expression must not generate , which is satisfied because every transition in the automaton consumes at least one input symbol ().
Arden's Theorem states that if and are regular expressions and , then the equation has the unique solution . To apply it to a finite automaton, the transition diagram must have no -transitions and must have a single initial state.
List the main algebraic laws satisfied by regular expressions (associative, commutative, identity, annihilator, distributive, idempotent, and closure laws).
Associative, Commutative, and Distributive Laws:
- Commutative Law (Union):
(Note: Concatenation is generally non-commutative, .)
- Associative Laws:
- Distributive Laws (Concatenation distributes over Union):
- Left Distributive:
- Right Distributive:
Identity, Annihilator, and Idempotent Laws:
- Identity Laws:
- is the identity for union: .
- is the identity for concatenation: .
- Annihilator (Zero) Laws:
- is the annihilator for concatenation: .
- Idempotent Law:
- Union is idempotent: . (Concatenation is not idempotent: in general.)
Closure and Star Laws:
- Basic Star properties:
- Compound identities:
Commutative: . Associative: and . Identities: and . Annihilator: . Distributive: and . Idempotent: . Closure: , , , and .