PadhaikoAll subjects

Regular Expressions & Equivalence with Finite Automata

Theory of Computation (ENCT 203)

Open in the Padhaiko app

2.5 Regular Expressions and Regular Languages

Definition

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:

  1. 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: .
  2. 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 .
  3. 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 CategoryIdentities
Commutative & Associative Laws, ,
Identities & Annihilators, ,
Distributive Laws,
Idempotent Law
Closure Laws, , , ,

Applications of Regular Expressions

  1. 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.
  2. 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).
  3. 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)

Example 2.14

Writing Regular Expressions for 10 Languages

Write a regular expression for each of the following languages:

  1. .
  2. Strings over having length exactly 3.
  3. Strings over having length at least 3.
  4. Strings over having length at most 3.
  5. Strings over containing an odd number of zeros.
  6. Strings over having even length.
  7. Strings where the number of 's in is divisible by 3.
  8. All strings in with more than 2 's (at least three 's).
  9. Strings over ending with 0 and not containing 11 as a substring.
  10. Strings over containing an even number of zeros.
Expressions for block structure and length constraints (Items 1–4 & 6)
  • 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:
Expressions for counting and substring constraints (Items 5 & 7–10)
  • Item 5 (odd number of zeros): One mandatory 0 (surrounded by arbitrary 's) followed by any number of pairs of 0'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 0 and no 11 substring): Every 1 must be immediately followed by 0, so every non-empty valid string is a sequence of 0 and 10 blocks:
  • Item 10 (even number of zeros): Zero 0's () or pairs of 0's interspersed with 's:
Answer:
  1. ; 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.

Example 2.15

Construct an ε-NFA for (ab ∪ ba)*

Construct a non-deterministic finite automaton for the regular expression .

Build elementary machines for symbols and concatenations

First construct 2-state -NFAs for () and (), then connect them in series with an -transition to form () and ().

Combine and using the union construction for

Add a branching state 0 with -transitions to 1 and 5:

Worked Out Example 2.15 — Construct an ε-NFA for (ab ∪ ba)*ε-NFA
Worked Out Example 2.15 — Construct an ε-NFA for (ab ∪ ba)* ε ε a ε b b ε a 0 1 5 2 3 4 6 7 8
Stateabε
→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
Apply the Kleene star construction for

Introduce a new initial/accepting state s with , and add feedback -transitions from the final states 4 and 8 back to 0:

Worked Out Example 2.15 — Construct an ε-NFA for (ab ∪ ba)*ε-NFA
Worked Out Example 2.15 — Construct an ε-NFA for (ab ∪ ba)* ε ε ε a ε b b ε a ε ε s 0 1 5 2 3 4 6 7 8
Stateabε
→*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
Answer:

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)

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 .

  1. 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).

  1. 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 .
Example 2.16

DFA to Regular Expression via Arden's Theorem

Construct a regular expression corresponding to the automaton given below:

Worked Out Example 2.16 — DFA to Regular Expression via Arden's TheoremDFA
Worked Out Example 2.16 — DFA to Regular Expression via Arden's Theorem b a b a b a q1 q2 q3
Stateab
→*q1q1q2
q2q3q2
q3q1q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts aa
  • ✓ accepts baa
  • ✓ accepts bbaa
  • ✓ accepts babaa
  • ✓ rejects b
  • ✓ rejects ba
  • ✓ rejects bb
  • ✓ rejects aba
  • ✓ rejects baaab
Write the state equations for

Since is both the initial state and the final state:

Eliminate and solve for using Arden's Theorem

Substitute into equation (2):

Comparing with where and (), Arden's Theorem gives:

Substitute and into the equation for

Applying Arden's Theorem with and :

Answer:

.

Example 2.17

3-State Binary DFA to Regular Expression

Construct a regular expression corresponding to the automaton given below:

Worked Out Example 2.17 — 3-State Binary DFA to Regular ExpressionDFA
Worked Out Example 2.17 — 3-State Binary DFA to Regular Expression 0, 1 0 0 1 1 q1 q2 q3
State01
→q1q1q2
*q2q2q3
q3q3q3
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 00100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 11
  • ✓ rejects 0101
Write the state equations

Here is the initial state and is the final state:

Solve for and using Arden's Theorem

From equation (1), . Substituting into equation (2):

Answer:

.


Solutions to Important Questions (Questions 24–36, Book pp. 122–129)

Example

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 .

Account for the 3 relative orderings of the mandatory

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:

Answer:

.

Example

Important Question 25 — At Least One 'a' or At Least One 'b' [2076 Ashwin]

Determine a regular expression for .

Express all non-empty strings over

A string over contains at least one a or at least one b if and only if its length is at least ():

Answer:

.

Example

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 .

Include single-character strings and length strings

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):

Answer:

(or for non-empty strings).

Example

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 .

Union the two cases ( and )

Either the string begins with a and ends with b, or it begins with b and ends with a:

Answer:

.

Example

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 .

Express

An even number of 's is , and an odd number of 's is :

Answer:

.

Example

Important Question 29 — Strings with 0101 as Substring [2072 Chaitra]

Find the regular expression for .

Sandwich 0101 between arbitrary binary strings
Answer:

.

Example

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.

Union the cases of or occurrences of a
Answer:

.

Example

Important Question 31 — Regex for Even a's Followed by Odd b's and DFA for (ab + aba)* [2081 Bhadra]

  1. Write a regular expression for .
  2. Design a DFA for the language , and check whether is accepted or not.
Regular expression for part 1 and DFA for

For part 1, . For part 2, the 5-state DFA has , start state , accepting states , and dead state :

Important Question 31 — DFA for (ab + aba)* [2081 Bhadra]DFA
Important Question 31 — DFA for (ab + aba)* [2081 Bhadra] a, b a b b a a b a b q0 q1 q4 q2 q3
Stateab
→*q0q1q4
q1q4q2
q4q4q4
*q2q3q4
*q3q1q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts ab
  • ✓ accepts aba
  • ✓ accepts abab
  • ✓ accepts abaab
  • ✓ accepts ababaab
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aa
  • ✓ rejects abb
  • ✓ rejects baba
Trace (note that )
Answer:

, and ends in and is accepted.

Example

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.

Construct the 6-state NFA

After reading the initial b from to (accepting), the machine can loop through baa () or aba (), with :

Important Question 32 — Convert L = b(baa ∪ aba)* to NFA and DFA [2079 Bhadra]NFA
Important Question 32 — Convert L = b(baa ∪ aba)* to NFA and DFA [2079 Bhadra] b b a a b a b a q0 q1 q2 q4 q3 q5
Stateba
→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
Convert to an equivalent DFA by adding dead state (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)
Important Question 32 — Convert L = b(baa ∪ aba)* to NFA and DFA [2079 Bhadra]DFA
Important Question 32 — Convert L = b(baa ∪ aba)* to NFA and DFA [2079 Bhadra] a, b a b a b a b a b a b a b q0 phi q1 q4 q2 q3 q5
Stateab
→q0phiq1
phiphiphi
*q1q4q2
q4phiq3
q2q3phi
q3q5phi
*q5q4q2
  • 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
Answer:

The DFA has states with accepting states and .

Example

Important Question 33 — DFA for R = (01 ∪ 010)* [2078 Kartik, 2073 Kartik]

Design a DFA that accepts the language defined by the regular expression .

Construct the 5-state DFA

Isomorphic to (with and ), the DFA has , start state , accepting states , and dead state :

Important Question 33 — DFA for R = (01 ∪ 010)* [2078 Kartik, 2073 Kartik]DFA
Important Question 33 — DFA for R = (01 ∪ 010)* [2078 Kartik, 2073 Kartik] 0, 1 0 1 1 0 0 1 0 1 q0 q1 q4 q2 q3
State01
→*q0q1q4
q1q4q2
q4q4q4
*q2q3q4
*q3q1q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 01
  • ✓ accepts 010
  • ✓ accepts 0101
  • ✓ accepts 01001
  • ✓ accepts 0101001
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 00
  • ✓ rejects 011
  • ✓ rejects 101
Answer:

.

Example

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 .

Construct the 5-state NFA

Let , , and :

Important Question 34 — NFA and DFA for (ab ∪ bb)*a [2075 Chaitra]NFA
Important Question 34 — NFA and DFA for (ab ∪ bb)*a [2075 Chaitra] a b b a b b b q0 q1 q4 q2 q3
Stateab
→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
Convert to DFA by adding dead state (phi)
(q0)
(q1)
(q4)
(q2)
(q3)
(phi)
Important Question 34 — NFA and DFA for (ab ∪ bb)*a [2075 Chaitra]DFA
Important Question 34 — NFA and DFA for (ab ∪ bb)*a [2075 Chaitra] a, b a b a b a b a b a b q0 q1 q4 phi q2 q3
Stateab
→q0q1q4
*q1phiq2
q4phiq2
phiphiphi
q2q3q4
*q3phiq2
  • 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
Answer:

The equivalent DFA has states with accepting states and .

Example

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.

Construct the 7-state NFA

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).
StateSymbol Symbol
Important Question 35 — NFA for (ab*a ∪ b*aa) [2073 Shrawan]NFA
Important Question 35 — NFA for (ab*a ∪ b*aa) [2073 Shrawan] b b a b b a a a a q0 q1 q4 q2 q6 q3 q5
Stateab
→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
Test on rejected string '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 .)

Answer:

Accepted strings: "abbba", "baa"; rejected strings: "abab", "ab".

Example

Important Question 36 — Obtain Regular Expression for 4-State DFA [2082 Kartik]

Obtain the regular expression for the given automaton:

Important Question 36 — Obtain Regular Expression for 4-State DFA [2082 Kartik]DFA
Important Question 36 — Obtain Regular Expression for 4-State DFA [2082 Kartik] 0, 1 0 1 1 0 0 1 A B C D
State01
→*ABC
BDA
CAD
DDD
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 0110
  • ✓ accepts 1001
  • ✓ accepts 0101
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 00
  • ✓ rejects 11
  • ✓ rejects 0011
Write the state equations

Here is both the start state and the sole final state, while is a non-accepting trap state:

Substitute and into (i) and apply Arden's Theorem

Comparing with where and , Arden's Theorem yields:

Answer:

.


Exercises

Exercises

Question 1

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:

  1. 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: .
  2. 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:
  1. 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):

  1. Kleene Star () (binds tightest)
  2. Concatenation ()
  3. 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 of 1's.
  • : Strings beginning with , terminating with , and having alternating segments.
Answer:

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.

Question 2

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:

  1. 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., ).
  2. No -transitions: The state transition graph must not contain -transitions (or -cycles).
  3. 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 ().
Answer:

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.

Question 3

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:
Answer:

Commutative: . Associative: and . Identities: and . Annihilator: . Distributive: and . Idempotent: . Closure: , , , and .

Past exam questions for Theory of Computation

← NFA, ε-NFA & Their Equivalence with DFAClosure Properties, Pumping Lemma & Decision Algorithms →