Regular Expressions
Introduction to Regular Expressions
In the theory of computation, regular expressions are a powerful formal tool used to describe regular languages, which are the simplest class of languages in the Chomsky Hierarchy (Type 3 languages). Regular expressions provide a concise way to define patterns in strings, making them essential for tasks like pattern matching, lexical analysis in compilers, and defining the behavior of finite automata. They are built from basic elements using operations that correspond to the properties of regular languages, such as union, concatenation, and iterative closure (Kleene star).
Motivation for Regular Expressions
Regular languages have a special property: all finite languages are regular. For example, consider the language
Moreover, the class of regular languages (
- Union: If
and are regular, then is regular. - Concatenation: If
and are regular, then (the set of strings formed by concatenating a string from with a string from ) is regular. - Kleene Star: If
is regular, then (the set of all strings formed by concatenating zero or more strings from , including the empty string ) is regular.
These operations allow us to build new regular languages from existing ones. For example, starting with finite languages (which are regular), we can apply union, concatenation, and Kleene star to generate more complex regular languages. This leads to a natural question: can we describe all regular languages using a formal tool based on these operations? The answer is yes, and that tool is the regular expression. Regular expressions are designed to capture all regular languages, providing a way to define them algebraically.
Definition of Regular Expressions
To define regular expressions formally, we need two alphabets:
: A finite alphabet of symbols (e.g., ), which are the basic building blocks of the language. : A set of operator symbols used to construct regular expressions. This set is disjoint from (i.e., ).
The set of regular expressions over
is a regular expression (representing the empty language). is a regular expression (representing the language containing only the empty string). is a regular expression for every (representing the language containing only the single symbol ). - If
is a regular expression, then is a regular expression (Kleene star, representing zero or more repetitions). - If
and are regular expressions, then is a regular expression (concatenation, representing strings formed by a string from followed by a string from ). - If
and are regular expressions, then is a regular expression (union, representing strings from either or ).
Alternative Notations
In practice, regular expressions are often written with simplified notations for readability:
- Union: Instead of
, you might see or . - Concatenation: Instead of
, you might see or simply (omitting the dot). For example, means . - These notations are equivalent and used interchangeably depending on the context.
Language Defined by a Regular Expression
Every regular expression
(the empty language, containing no strings). (the language containing only the empty string). for (the language containing only the single symbol ). (the Kleene star of the language , i.e., zero or more concatenations of strings from ). (the concatenation of languages and , i.e., all strings of the form where and ). (the union of languages and , i.e., all strings that are in , , or both).
Correspondence Between Operations
The operations in regular expressions directly correspond to the operations on regular languages:
- The
operation corresponds to union ( ). - The
operation corresponds to concatenation. - The
operation corresponds to the Kleene star ( ).
Remark on Notation
In practice, we often blur the distinction between a regular expression
Properties of Regular Expressions
Regular expressions satisfy several algebraic properties that make them easier to manipulate. Let
- Associativity of Union:
The order of grouping in unions does not matter. - Associativity of Concatenation:
The order of grouping in concatenations does not matter. - Commutativity of Union:
Union is order-independent. - Distributivity of Concatenation over Union (Left):
Concatenating with a union of and is the same as concatenating with and with , then taking the union. - Distributivity of Concatenation over Union (Right):
Similar to the left distributivity, but on the right side. - Kleene Star Expansion:
The Kleene star includes the empty string plus one or more repetitions of . - Identity for Concatenation:
Concatenating with the empty string does not change the language. - Alternative Kleene Star Form:
The Kleene star can be expressed as zero or more repetitions of or . - Zero for Concatenation:
Concatenating with the empty language yields the empty language.
Simplifications and Notational Conventions
To make regular expressions more concise, we use the following conventions based on their properties:
- Operator Precedence: The operations have a priority order (from strongest to weakest):
, , . This means: binds most tightly: In , the applies to , not , so it means . is next: In , the concatenation is evaluated first, so it means . is weakest: In , parentheses are needed to specify grouping, but associativity allows us to write it without them as .
- Omitting Parentheses: If a regular expression is enclosed in parentheses and the outermost operation matches the intended grouping, the outer parentheses can be omitted. For example,
can be written as . - Chains of Operations: Due to associativity, chains of
or do not need parentheses. For example, can be written without parentheses as , and does not need grouping. - Additional Notations:
: Shorthand for , meaning one or more repetitions of . For example, means one or more 's. - Specific Powers: We can write
to mean , representing exactly three repetitions of the pattern .
These simplifications make regular expressions easier to write and understand while preserving their meaning.
Example: Constructing and Interpreting Regular Expressions
Let’s construct a regular expression and determine the language it defines. Consider
Break Down the Expression:
: Zero or more 's, so . : Concatenation of and , so . : Zero or more 's, so . : Concatenation of and , so . : Union of and , so .
Simplify the Language:
includes strings like , , , etc. includes strings like , , , etc. - Their union includes strings that have at least one
, with 's either before or after: , , , , etc. - Notice that
(when ), and (when ), so the language can be described as all strings with at least one , and any number of 's before or after the 's.
Thus,
Regular Expressions and Type 3 Grammars
Regular expressions are closely tied to Type 3 (regular) grammars, as both describe regular languages. We can construct Type 3 grammars that correspond to the regular operations (union, concatenation, and Kleene star) applied to regular languages. This demonstrates that regular expressions can indeed describe all regular languages, as they can be translated into equivalent Type 3 grammars.
Union of Regular Languages
Given two Type 3 grammars
- Grammar for Union:
- Explanation: The new start symbol
can derive either (leading to strings in ) or (leading to strings in ). The rule is of Type 3 form ( ), and since and are Type 3, the resulting grammar remains Type 3. - Language Generated:
.
Concatenation of Regular Languages
Given two Type 3 grammars
- Identify Terminal Rules in
: Let be the rules in that produce terminal strings. - Modify Terminal Rules: Create
by replacing each terminal-producing rule with one that starts ’s derivation. - Grammar for Concatenation:
- Explanation: When
reaches a terminal string , instead of stopping, it now produces , allowing to generate a string from , resulting in . The modified rules are still of Type 3 form ( or ), so the grammar remains Type 3. - Language Generated:
.
Kleene Star of a Regular Language
Given a Type 3 grammar
- Identify Terminal Rules: Let
be the rules that produce terminal strings. - Modify Terminal Rules: Create
to allow restarting the derivation. - Grammar for Kleene Star:
- Explanation: The new start symbol
can either produce (for zero repetitions) or start a derivation with . Each time produces a terminal string , the modified rule allows restarting the derivation to produce another string, enabling zero or more repetitions. The rules are of Type 3 form, and the grammar remains Type 3. - Language Generated:
.
Computational Model
Regular languages, as defined by regular expressions or Type 3 grammars, correspond to languages accepted by finite automata (the simplest computational model in the Chomsky Hierarchy). This connection makes regular expressions a practical tool for designing and understanding finite state machines in computer science applications.
Notable Regular Expressions
- arbitrary string constructed with two symbols:
- arbitrary string constructed with three symbols, which doesn't allow certain substrings:
- arbitrary string constructed with two symbols, with even number of
's:
- arbitrary string constructed with two symbols, with odd number of
's:
Example 1
Determine the language described by the following regular expression.
Solution
Break Down the Expression:
: The string must start with a . : After the initial , there can be any combination of 's and 's (including none). : The string must end with a .
Language Generated:
Example 2
Determine the language described by the following regular expression.
Solution
Break Down the Expression:
: The outer indicates one or more repetitions of the inner expression. : Any combination of 's and 's (including none). : The string must contain at least one .
Language Generated:
Example 3
Determine the language described by the following regular expression.
Solution
Break Down the Expression:
: The string can start with any number of 's (including none). : After the 's, there can be any number of 's (including none). : The string must contain the substring . : After , there may be a number of 's divisible by 3 (including none).
Language Generated:
Example 4
Make regular expressions decribing the following languages.
Solution
Regular Expression:
Explanation: The expression captures strings that contain at least one
Example 5
Make regular expressions decribing the following languages.
Solution
Regular Expression:
Explanation: The first part
Example 6
Make regular expressions decribing the following languages.
Solution
Regular Expression:
Explanation: The expression captures strings with an odd number of
Example 7
Make regular expressions decribing the following languages.
Solution
Regular Expression:
Explanation: The expression captures strings with pairs of
Example 8
Make a type 3 grammar generating the language described by the regular expression.
Solution
Type 3 Grammar:
** Explanation**: The grammar generates strings that start with any number of
Example 9
Make a type 3 grammar generating the language described by the regular expression.
Solution
Type 3 Grammar:
