Study Notes on Regular Expressions

By Mukesh Kumar|Updated : July 29th, 2021

Regular Expression

Regular expressions are a way to represent a certain set of strings in some algebraic fashion. A regular expression over the alphabet Σ is defined as follows

  • ϕ is a regular expression corresponding to the empty language ϕ.
  • ε is a regular expression corresponding to the language { ε }.
  • For each symbol, a ∈Σ a is a regular expression corresponding to the language {a}.
Table of Content

Regular Language

The languages accepted by FA are regular languages and these languages are easily described by simple expressions called regular expressions.

Any regular expression r and s over Σ (universal set) corresponding to the languages Lr and Ls respectively, each of the following is a regular expression corresponding to the language indicated.

  • (rs) corresponding to the language LrLs
  • (r + s) corresponding to the language Lr Ls
  • r* corresponding to the language Lr. Some examples of regular expression are
    1. L (01) = {0, 1}
    2. L (01 + 0) = {01, 0}
    3. L (0 (1+ 0)) = {01, 00}
    4. L (0*) = {ε, 0, 00, 000, ...}
    5. L ((0 + 10)* (ε + 1)) = all strings of 0's and 1's without two consecutive 1's.
  • If L1 and L2 are regular languages in Σ*, then L1 L2, L1 L2, L1 – L2 and L1 (complement of L1), are all regular languages.
  • Pumping lemma is a useful tool to prove that a certain language is not regular.

Regular Set

A regular set is defined as a set represented by a regular expression. For e.g., If Σ = {a, b} is an alphabet, then

Different Regular Sets and their Expressions


Identities for Regular Expressions 

The following points are the some identities for regular expressions.

  • ϕ + R = R + ϕ = R
  • ε R = R ε = R
  • R + R = R, where R is the regular expression.
  • (R*)* = R* ϕR = Rϕ = ϕ
  • ε * = ε and ϕ* = ε
  • RR* = R*R = R+
  • R*R* = R*
  • (P + Q)* = (P*Q*)* = (P* + Q*)*, where P and Q are regular expressions.
  • R (P + Q) = RP + RQ and (P + Q)R = PR + QR
  • P(QP)* = (PQ)*P 

Arden’s Theorem 

  • If P and Q are two expressions over an alphabet Σ such that P does not contain ε, then the following equation R = Q + RP.
  • The above equation has a unique solution i.e., R = QP*. Arden's theorem is used to determine the regular expression represented by a transition diagram.
  • The following points are assumed regarding transition diagrams
  • The transition system does not have any
  • It has only one initial (starting) stage.

Properties of Regular Language

Regular languages are closed under the following operations

  1. Union
  2. Concatenation
  3. Kleene closure
  4. Complementation
  5. Transpose
  6. Intersection

You can follow the detailed champion study plan for GATE CS 2021 from the following link:

Detailed GATE CSE 2021 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series! (100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering

Important Links

GATE CSE Question Papers

GATE CSE Study Plan

GATE CSE Exam Analysis

GATE Study Material for CSE

GATE CSE Exam Pattern 2022, Sectional timing, Marking Scheme

ISRO EC Question Papers

GATE CSE Syllabus 2022

ISRO EC Study Plan

ISRO EC Syllabus


Prep Smart. Score Better!

Download BYJU'S Exam Prep app for Exam Preparation here


write a comment

Follow us for latest updates