# Study Notes on Regular Expressions

By BYJU'S Exam Prep

Updated on: September 25th, 2023

Regular Expressions (regex) are a versatile and powerful tool for pattern matching and text manipulation. Used in a wide range of fields, from software development to data analysis, Regular Expressions provide a concise and efficient way to search, validate, and extract information from text.

This post covers the study notes of Regular Expressions, their syntax, and their practical applications.

Formulas for GATE Computer Science Engineering – Theory of Computation PDF Download

Table of content

## What are Regular Expressions?

A regular expression is a sequence of characters that defines a search pattern. It consists of a combination of literal characters and metacharacters, which represent a set of possible characters or specific rules for matching patterns.

Regular Expressions enable us to perform complex searches within text data, such as finding email addresses, validating phone numbers, or extracting specific parts of a document.

## Syntax and Metacharacters

Here are some key components and syntax used in Regular Expressions:

Literal Characters: Ordinary characters such as letters, digits, or special characters that match themselves. For example, the regex hello matches the string hello exactly.

Metacharacters: Characters that have special meanings in regex. Some commonly used metacharacters include:

• . (dot): Matches any character except a newline.
• \d: Matches any digit (0-9).
• \w: Matches any alphanumeric character or underscore.
• \s: Matches any whitespace character (spaces, tabs, newlines).
• ^: Matches the start of a line.
• \$: Matches the end of a line.
• |: Acts as an OR operator, allowing multiple alternatives.
• []: Matches any character within the brackets.
• (): Groups expressions together.

Quantifiers: It defines the number of times a character or group should be repeated.

• *: Matches 0 or more occurrences.
• +: Matches 1 or more occurrences.
• ?: Matches 0 or one occurrence.
• {n}: Matches n occurrences.
• {n, m}: Matches at least n and at most m occurrences.

Character Classes: Predefined character sets that match specific types of characters. Some common character classes include:

• \d: Digits (0-9).
• \w: Alphanumeric characters and underscores.
• \s: Whitespace characters.
• \D: Non-digits.
• \W: Non-alphanumeric characters and underscores.
• \S: Non-whitespace characters.

Anchors: Specify positions within a string.

• ^: Matches the start of a string or line.
• \$: Matches the end of a string or line.
• \b: Matches a word boundary.

Escape Sequences: Backslash () is used to escape special characters and give them their literal meaning. For example, to match a literal dot (.), you need to write .

These metacharacters, along with others, can be combined to create powerful search patterns and transformations.

## Regular Language

Regular language refers to a type of formal language that can be defined and recognized by a regular expression, a finite automaton, or a regular grammar. Regular languages are a fundamental concept in theoretical computer science and play a significant role in various areas, including compiler design, pattern matching, text processing, and formal language theory.

• The regular expression (rs) corresponds to the language LrLs.
• The regular expression (r + s) corresponds to the language Lr ∪ Ls.
• The regular expression r* corresponds to the language Lr.

## Properties of Regular Languages

• Closure Properties
• Union
• Concatenation
• Kleene Star
• Finite Automaton Recognition
• Regular Expressions
• Pumping Lemma
• Deterministic and Non-deterministic Behavior
• Regular Grammar
• Linear Time Complexity

## Arden’s Theorem

Arden’s theorem is a fundamental result in formal language theory and automata theory. It provides a method for solving systems of equations involving Regular Expressions or finite automata.

Statement of Arden’s Theorem

Let R, S, and T be Regular Expressions over an alphabet Σ. The theorem states that for any given Regular Expressions R and S, the equation Rx = S has a unique solution given by the expression Rx = S/R*, where R* is the Kleene closure (zero or more repetitions) of R.

Explanation:

Arden’s theorem provides a way to solve equations of the form Rx = S, where R and S are Regular Expressions, and x is a variable representing a regular language.

The equation Rx = S can be interpreted as finding the language x that, when concatenated with R, produces the language S. The theorem states that this equation has a unique solution, and it is given by Rx = S/R*, where R* represents zero or more repetitions of R.

The proof of Arden’s theorem relies on properties of regular languages and the properties of concatenation and closure operations. By applying the Kleene closure to both sides of the equation Rx = S, we can ensure that the left side is self-referential, allowing us to isolate x.

## How to Write Regular Expressions?

Writing Regular Expressions can be a powerful tool for pattern matching and text manipulation. Regular Expressions (regex) are a sequence of characters that define a search pattern. Here are the basic steps to write Regular Expressions:

• Define the problem: Determine what specific pattern or set of patterns you want to match or extract from a text.
• Choose a regular expression engine: Different programming languages and text editors may have slightly different regex syntax and capabilities. Make sure to choose an appropriate regex engine that matches your programming language or text editor.
• Learn the regex syntax: Familiarize yourself with the regular expression syntax. It includes a combination of ordinary characters, metacharacters, and quantifiers that define the pattern you want to match.
• Ordinary characters: These are normal characters such as letters, digits, or special characters that match themselves. For example, the letter ‘a’ in a regex will match the letter ‘a’.
• Start building the regular expression: Begin constructing the regex based on your problem definition and the desired pattern. Use the metacharacters and quantifiers to define the required pattern.
• Test and refine: Test the regular expression with sample inputs and refine it as needed. Make sure it captures the desired pattern accurately and doesn’t produce false positives or negatives.
• Escape special characters if necessary: If your regular expression includes special characters that need to be matched literally, you may need to escape them using a backslash (”). For example, if you want to match a literal dot (‘.’), you need to write ‘.’ in the regex.
• Optimize if required: Regular Expressions can sometimes be slow or inefficient, especially when dealing with large amounts of text. If performance is a concern, consider optimizing your regex by simplifying or rewriting it to improve efficiency.
• Document and share: Once you have a working regular expression, document it and share it with others who might find it useful. Include clear instructions on how to use it and any limitations or assumptions it makes.

## Regular Set

A set represented by a regular expression is known as a Regular Set. Regular sets are a fundamental concept in the study of formal languages and play a crucial role in various areas of computer science and linguistics.

Different Regular Sets and their Expressions

## Identities for Regular Expressions

• Identity Law:

E + ∅ = E

∅ + E = E

E · ε = E

ε · E = E

E · ∅ = ∅

∅ · E = ∅

These identities state that combining a regular expression with an empty language (∅) or the empty string (ε) does not change the original expression.

• Annihilation Law:

E · ∅ = ∅

∅ · E = ∅

These identities indicate that concatenating a regular expression with an empty language results in an empty language.

• Idempotent Law:

E + E = E

E · E = E

These identities state that the union or concatenation of a regular expression with itself remains unchanged.

• Absorption Law:

E + E·F = E

E·(E + F) = E

These identities imply that if a regular expression is combined with another expression and they are concatenated or unioned, if one expression is a subset of the other, it can be absorbed.

• Distributive Laws:

E · (F + G) = (E · F) + (E · G)

(F + G) · E = (F · E) + (G · E)

These identities show that the distributive property holds for the concatenation and union operations.

• De Morgan’s Laws:

(E + F)’ = E’ · F’

(E · F)’ = E’ + F’

These identities state that the complement of a union is equal to the intersection of the complements, and the complement of a concatenation is equal to the union of the complements.

• Kleene Star Law:

(E*)* = E*

ε* = ε

∅* = ε

These identities represent properties of the Kleene closure operation, stating that the closure of a closure is equal to the closure, and the closure of the empty language (∅) is the empty string (ε).