Study Notes on Regular Expressions

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 L_r and L_s respectively, each of the following is a regular expression corresponding to the language indicated.

• (rs) corresponding to the language L_rL_s
• (r + s) corresponding to the language L_r ∪ L_s
• r^* corresponding to the language L_r. 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 L₁ and L₂ are regular languages in Σ^*, then L₁ ∪ L₂, L₁ ∩ L₂, L₁ – L₂ and L₁ (complement of L₁), 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

Thanks

Prep Smart. Score Better!