Regular Expressions | Compiler Design - Computer Science Engineering (CSE) PDF Download

Regular Expression

  • The language accepted by finite automata can be easily described by simple expressions called Regular Expressions. It is the most effective way to represent any language.
  • The languages accepted by some regular expressions are referred to as Regular languages.
  • A regular expression can also be described as a sequence of patterns that defines a string.
  • Regular expressions are used to match character combinations in strings. String searching algorithm used this pattern to find the operations on a string.

For instance

  • In a regular expression, x* means zero or more occurrence of x. It can generate {e, x, xx, xxx, xxxx, .....}
  • In a regular expression, x+ means one or more occurrences of x. It can generate {x, xx, xxx, xxxx, .....}

Operations on Regular Language

The various operations on regular language are:

  • Union: If L and M are two regular languages then their union L U M is also a union.
    L U M = {s | s is in L or s is in M}  
  • Intersection: If L and M are two regular languages then their intersection is also an intersection.
    L ⋂ M = {st | s is in L and t is in M}  
  • Kleene closure: If L is a regular language then its Kleene closure L1* will also be a regular language.
    L* = Zero or more occurrences of language L.  

Example 1:

Write the regular expression for the language accepting all combinations of a's, over the set ∑ = {a}
Solution: All combinations of a's means a may be zero, single, double and so on. If a is appearing zero times, that means a null string. That is we expect the set of {ε, a, aa, aaa, ....}. So we give a regular expression for this as:
R = a*  

Example 2:


Write the regular expression for the language accepting all combinations of a's except the null string, over the set ∑ = {a}
Solution: The regular expression has to be built for the language
L = {a, aa, aaa, ....}  
This set indicates that there is no null string. So we can denote regular expression as:
R = a+

Example 3: 

Write the regular expression for the language accepting all the strings containing any number of a's and b's.
Solution: The regular expression will be:
r.e. = (a + b)*  
This will give the set as L = {ε, a, aa, b, bb, ab, ba, aba, bab, .....}, any combination of a and b.
The (a + b)* shows any combination with a and b even a null string.

Examples of Regular Expression

Example 1: Write the regular expression for the language accepting all the string which are starting with 1 and ending with 0, over ∑ = {0, 1}.
Solution: In a regular expression, the first symbol should be 1, and the last symbol should be 0. The r.e. is as follows:
R = 1 (0+1)* 0  

Example 2: Write the regular expression for the language starting and ending with a and having any combination of b's in between.
Solution: 
The regular expression will be:
R = a b* b  

Example 3: Write the regular expression for the language starting with a but not having consecutive b's.
Solution: 
The regular expression has to be built for the language:
L = {a, aba, aab, aba, aaa, abab, .....}  
The regular expression for the above language is:
R = {a + ab}* 

Example 4: Write the regular expression for the language accepting all the string in which any number of a's is followed by any number of b's is followed by any number of c's.
Solution: 
As we know, any number of a's means a* any number of b's means b*, any number of c's means c*. Since as given in problem statement, b's appear after a's and c's appear after b's. So the regular expression could be:
R = a* b* c*  

Example 5: Write the regular expression for the language over ∑ = {0} having even length of the string.
Solution: The regular expression has to be built for the language:
L = {ε, 000000000000, ......}  
The regular expression for the above language is:
R = (00)* 

Example 6: Write the regular expression for the language having a string which should have atleast one 0 and alteast one 1.
Solution: The regular expression will be:
R = [(0 + 1)* 0 (0 + 1)* 1 (0 + 1)*] + [(0 + 1)* 1 (0 + 1)* 0 (0 +1)*]  

Example 7: Describe the language denoted by following regular expression
r.e. = (b* (aaa)* b*)*  
Solution: The language can be predicted from the regular expression by finding the meaning of it. We will first split the regular expression as:
r.e. = (any combination of b's) (aaa)* (any combination of b's)
L = {The language consists of the string in which a's appear triples, there is no restriction on the number of b's}

Example 8: Write the regular expression for the language L over ∑ = {0, 1} such that all the string do not contain the substring 01.
Solution: The Language is as follows:
L = {ε, 01001110100, .....}  
The regular expression for the above language is as follows:
R = (10*)  

The document Regular Expressions | Compiler Design - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Compiler Design.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
26 videos|55 docs|30 tests

Up next

FAQs on Regular Expressions - Compiler Design - Computer Science Engineering (CSE)

1. What are regular expressions used for in computer science engineering?
Ans. Regular expressions are used in computer science engineering for pattern matching, searching, and text processing tasks. They provide a concise and flexible way to specify patterns in strings.
2. How do regular expressions help in operations on regular languages?
Ans. Regular expressions help in operations on regular languages by providing a formalism to define and manipulate regular languages. They can be used to describe sets of strings that can be recognized by finite automata.
3. Can you provide an example of a regular expression used in computer science engineering?
Ans. An example of a regular expression is "^[a-zA-Z0-9]+@[a-zA-Z0-9]+\.[a-zA-Z]{2,3}$", which is commonly used to validate email addresses.
4. What are some common tasks that regular expressions can be used for in CSE?
Ans. Regular expressions can be used for tasks such as input validation, text parsing, data extraction, and search and replace operations in computer science engineering.
5. How important are regular expressions in the field of computer science engineering?
Ans. Regular expressions are fundamental in computer science engineering as they provide a powerful tool for working with text and patterns. They are widely used in various applications and play a crucial role in data processing and manipulation.
26 videos|55 docs|30 tests
Download as PDF

Up next

Explore Courses for Computer Science Engineering (CSE) exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Download the FREE EduRev App
Track your progress, build streaks, highlight & save important lessons and more!
Related Searches

MCQs

,

Summary

,

ppt

,

Regular Expressions | Compiler Design - Computer Science Engineering (CSE)

,

shortcuts and tricks

,

Regular Expressions | Compiler Design - Computer Science Engineering (CSE)

,

pdf

,

Viva Questions

,

Exam

,

Previous Year Questions with Solutions

,

Objective type Questions

,

Sample Paper

,

practice quizzes

,

study material

,

Semester Notes

,

Free

,

Regular Expressions | Compiler Design - Computer Science Engineering (CSE)

,

Important questions

,

video lectures

,

Extra Questions

,

mock tests for examination

,

past year papers

;