Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Jul 9, 2024
Medium

Regular Expression IN TOC

Author Anant Dhakad
0 upvote
Table of contents
Learn to use AI Tools & ChatGPT to excel as Microsoft SDE
11 Jul, 2024 @ 01:30 PM
Speaker
Pranav Malik
SDE 2 @
Theory of Computation

Regular Expressions are simple expressions that can describe the language that finite automata accept. It is the most efficient method of representing any language. Regular languages are the languages that some regular expressions accept. A regular expression can also be defined as a pattern sequence that defines a string.

To match character combinations in strings, regular expressions are used. The string searching algorithm used this pattern to find operations on a string.

An expression is regular if and only if the following conditions are met:

  • ɸ is a regular expression that stands for regular language ɸ.
  • ɛ is a regular expression that stands for regular language {ɛ}.
  • If a ∈ Σ  (Σ represents the input alphabet), then a is a regular expression in language {a}.
  • If a and b are regular expressions, then a + b is a regular expression with the language as {a,b}.
  • If a and b are regular expressions, then ab (a and b concatenation) is also regular.
  • If a is a regular expression, then a* (0 or more times a) is also regular.


Note that two regular expressions are equivalent if the languages generated by them are the same. For example,(a+b*)* and (a+b)* yield the same language. Every string produced by (a+b*)* is also produced by (a+b)*, and vice versa.

Examples of Regular Expression in TOC

Here * means 0 or more occurrences, and + means one or more occurrences.

  • If regular language is  { }, then the regular expression is ϕ.
  • If regular language is  {ϵ}, then the regular expression is ϵϵ.
  • If regular language is  {r}, then the regular expression is r.
  • If regular languages are LR and LS, then the regular expression is R and S.
  • If regular language is LR U LS, the regular expression is R+S.
  • If regular language is LR.LS, then the regular expression is R.S
  • If regular language is LR*, then the regular expression is R*
  • If regular language is L+R, then the regular expression is R+

Properties of Regular Expressions using Operators

(a) Union operator satisfies commutative property and associative property.

        a+b=b+a (commutative)

        a+(b+c)=(a+b) +c (associative)

(b) The concatenation operator satisfies associative property but not commutative property

        ab ≠ b.a (not commutative)

        a(b.c) =(a.b).c (associative)

(c) Both left and right distributive properties of concatenation over union hold.

        x (y+z) = (x.y) + (x.z) (Left distribution of. over +)

        (x+y).z =(x.z) + (y.z) (Right distribution of. over +)

(d) Both left and right distributive properties of union over concatenation does not holds.

        a+(b.c) ≠ (a+b).(a+c)

        (ab)+c ≠ (a+c).(b+c)

(e) Union operetor satisfies idempotent property but the concatenation operator does not holds.

        a+az = a (idempotent)

        a.a ≠ a (not idempotent)

(f) Identity property:

        R+∅ = ∅ +R =R  (∅ is identity element with respect to union operation)

        ε . R = R.ε = R (ε is identity element with respect to concatenation)

(g) Annihilator property: RoX = X

        R+Σ* = Σ* (Σ* is annihilator with respect to union operator)

        R. ∅ = ∅  ( ∅ is annihilator with respect to concatenation operator)

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Applications of Regular Expression in TOC

Regular Expressions are helpful in a wide range of text processing tasks and string processing in general, where the data does not have to be textual. 

For example:

  • Data validation
  • Data scraping (particularly web scraping)
  • Data wrangling
  • Simple parsing
  • The creation of syntax highlighting systems and a variety of other tasks are typical applications.


While Regular Expressions could be helpful in Internet search engines, processing them across the entire database could consume many computer resources depending on the complexity and design of the regular expressions.

Also see, Turing Machine in TOC.

Frequently Asked Questions

Which are 3 uses of regular expression?

Regular expressions are highly useful for various tasks such as searching and extracting specific patterns in text, validating input formats like email addresses and phone numbers, and replacing or modifying text based on patterns. ​​

What are the different types of regular expressions?

Regular expressions generally come in two types: POSIX (basic and extended) and Perl-compatible (PCRE). PCREs are widely used in modern programming languages for their enhanced features and flexibility.

What is meant by regular expression?

A regular expression can also be defined as a pattern sequence that defines a string. It is most commonly used in pattern matching with strings or string matching. 

Write a regular expression for a set of vowels?

The regular expression for a set of vowels is ( a ∪ e ∪ i ∪ o ∪ u )

What are Regular Language and Regular Grammar?

Grammar is considered regular if it has rules of the form A -> a or A -> aB or A -> ɛ where ɛ  is a special symbol known as NULL and a language is considered regular if it can be expressed using regular expressions.

Conclusion

Regular Expressions are simple expressions that can describe the language that finite Automata accept. It is the most efficient method of representing any language. Regular languages are the languages that some regular expressions accept. A regular expression can also be defined as a pattern sequence that defines a string. We have learned about Regular Expressions in this blog and have seen various examples.

Also, check out these amazing blogs on the Theory of Computation to strengthen your knowledge of the concepts:


Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, etc. along with some Contests and Interview Experiences only on Code360