# 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}.

## 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

Thanks

Prep Smart. Score Better!

write a comment

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 YogeshOct 22, 2019