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

image004

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 Gradeup Green Card check the following link:

Click Here to Avail GATE CSE Green Card! (100+ Mock Tests)

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

Click here to avail Super 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

Thanks

Prep Smart. Score Better!

Download Gradeup app for Exam Preparation here

Posted by:

Mukesh KumarMukesh KumarMember since Feb 2020
Share this article   |

Comments

write a comment
Syed Arbaz

Syed ArbazOct 8, 2019

Hello..
I want to know,
From where should i learn calculs in order to solve every kind of question that may come in cse  gate2020
Ramya Yogesh

Ramya YogeshOct 22, 2019

Made easy handbook is preferable
Harsha Vardhan
No notes on pumping lemma ?

Follow us for latest updates