2 - Regular Expressions and Languages

---

Regular languages represent the simplest class within the hierarchy of formal languages, defined in multiple ways including algebraically, through generating grammars, and by employing recognizer machines. This foundational category of languages is critical for various areas in computer science, particularly in automata theory, formal language theory, and compiler design.

At the heart of regular languages lies the concept of regular expressions, which are strings composed of symbols from a terminal alphabet, denoted as . Regular expressions utilize a set of meta-symbols: concatenation (), union (), and the Kleene star (), along with special symbols like the empty set () and parentheses for grouping.

Definition

The formal definition of a regular expression can be delineated through five fundamental cases:

1. : This expression denotes the empty language, which contains no strings.
2. : Here, is a symbol from the alphabet , signifying a language that consists solely of the single character .
3. : This denotes the union of the languages represented by expressions and , allowing the formation of languages that include strings from either expression.
4. : This expression represents the concatenation of languages, where strings from are followed by strings from .
5. : The Kleene star indicates the closure operation, meaning the language may contain zero or more occurrences of strings defined by .

The precedence of the operators in a regular expression is as follows: the star operator has the highest precedence, followed by concatenation, and finally the union operator. Additionally, the empty string can be included in regular expressions, as it holds that .

The interpretation of a regular expression gives rise to a language over the alphabet .

Regular Expression	Language
(or )
(or )

A language is classified as regular ( ) if it can be represented by a regular expression.

Example 1: The language is the unary language of the multiples of three.

We can define the regular expression as follows:

that is, the concatenation of the string “111” zero or more times. This expression generates strings such as , which correspond to the multiples of three in unary notation. From the regular expression , we can derive the associated language:

Another regular expression that generates the same language is:

Example 2: Let , where denotes a decimal digit . Define the regexp that generates the language of integers, possibly signed.

This language represents the in three different ways: , , . If we want to avoid this, we can use the following regexp: .

Example 3: Define a language over the binary alphabet such that the number of letters in every string is odd and such that every string contains at least one letter .

The regexp is , where is the set of strings with an odd number of ‘s () and is the set of strings with an even number of ‘s ().

The study of regular languages can be categorized into distinct families.

• The family of regular languages, denoted as , comprises all languages that can be expressed via regular expressions.
• In contrast, the family of finite languages, termed , encompasses all languages containing a finite number of strings.

It is noteworthy that every finite language is inherently regular, as it can be constructed through the union of a finite number of strings, where each string is a concatenation of a finite number of symbols from the alphabet.

Despite , it also includes an infinite number of languages characterized by infinite cardinality—those that contain infinitely many strings.

Subexpression of a Regular Expression

To analyze a regular expression (regexp) systematically, we can isolate its subexpressions, especially when the expression is fully parenthesized¹. This step helps in understanding the structure and behavior of the expression, making it easier to study its properties or manipulate it for various operations such as pattern matching or language generation.

Example

Let’s take the example of a regular expression

We follow the steps below to better understand the subexpressions:

1. Fully Parenthesized Form: The expression is already fully parenthesized.

2. Numbering the Symbols: Each alphabetic symbol (i.e., individual elements from the alphabet) in the regular expression is assigned a unique number. We represent this new marked regular expression as:

3. Isolating Subexpressions: Now, let’s break down the regular expression into its subexpressions and highlight them.

• Subexpression 1: , a single symbol from the alphabet.
• Subexpression 2: , the concatenation of two symbols from the alphabet.
• Subexpression 3: , which represents a union of two subexpressions: and .
• Subexpression 4: , which represents the Kleene star applied to the union of two subexpressions.
• Subexpression 5: , the positive closure (one or more repetitions) of the symbol .
• Subexpression 6: , another union between the symbol and the concatenation of .
• Subexpression 7: , a union between the positive closure of and the union of .

In regular expressions, the operators like union () and iteration (Kleene star ) allow multiple ways of defining the same or different languages. By choosing one alternative over another, we can generate a new expression that describes a smaller subset of the original language.

Union and Iteration Operator Choices

Consider a regular expression , where each is a subexpression. Choosing one subexpression from this union gives a new regular expression that describes a smaller language.

For example, if , you can derive or , each describing a subset of the original language.

The iteration operator has multiple forms: the Kleene star (), positive closure (), and finite repetition (). These variations give rise to different ways of interpreting the same subexpression. For instance, if you have , you can derive a new expression by choosing the positive closure , which requires at least one occurrence of . Similarly, a finite repetition like requires exactly 2 occurrences of .

Deriving a New Regexp

Given a regular expression , we can derive a new expression by replacing one of its subexpressions (denoted as ) with a different choice for the union or iteration operator.

For example, consider the regular expression . We can replace the subexpression with just , leading to the new expression , which defines a smaller language.

Thus, by manipulating the structure of a regular expression through alternative choices for unions and iterations, we can refine it to create different expressions that describe smaller or more specific languages. This flexibility is one of the key advantages of using regular expressions in formal language theory.

In formal language theory, the concept of derivation is used to describe how one regular expression (regexp) can be transformed into another by systematically replacing parts of the expression. The derivation relation between two regular expressions is defined by the idea that

Definition

A regular expression derives from another regular expression if the two can be factored into parts such that and , where:

• and are fixed parts of the regular expressions.
• is a subexpression of .
• is a subexpression of and is a choice of .

This means that is formed from by replacing the subexpression with an alternative choice , while the rest of the structure ( and ) remains unchanged.

Derivation steps can be applied sequentially. That is, we can derive a regular expression from by applying a series of derivations, where each step replaces a subexpression with a new choice. The notation for multiple-step derivations is as follows:

• denotes that derives in steps, with .
• means that derives in steps.
• indicates that derives in steps, which includes both zero or more steps of derivation.

Examples of Derivation

Let’s look at concrete examples of derivations to better understand this process:

1. One-Step Derivation:

Here, we derive from the initial expression by choosing from the union.

2. Two-Step Derivation:

In this case, we first choose from the union, and then , as allows zero occurrences of . Thus, in two steps, we derive the empty string .

4. Derivation of a Non-Empty String:

In this example, we first choose from the union, and then derive three occurrences of from the positive closure.

These derivations show that the language generated by a regular expression consists of all strings that can be derived from the expression in zero or more steps, where is the alphabet.

Language Generated by a Regular Expression

The language defined by a regular expression , denoted as , is the set of all strings that can be derived from by performing zero or more derivation steps:

In other words, the language consists of all possible strings that can be generated by starting from the regular expression and applying derivations to transform it into a sequence of alphabetic symbols (a string) without any meta symbols (such as union, iteration, or concatenation).

Definition

Two regular expressions are said to be equivalent if they define the same language.

That is, even if the regular expressions themselves look different, they are equivalent if they generate the same set of strings.

For instance, the regular expressions and are equivalent, as they both generate the same language, which is the set of all strings made up of any number of 's and 's in any order.

The language defined by a derived regular expression is always a subset of the language defined by the original expression from which it is derived. This is because derivation involves making choices that narrow down the possible strings that the expression can generate. Additionally, there may be multiple derivation paths that lead to the same string, but these are considered equivalent in terms of the language generated.

Ambiguity in Regular Expressions

In formal language theory, ambiguity in regular expressions occurs when a string can be derived in two or more substantially different ways from the same regular expression. This phenomenon goes beyond merely rearranging the order of derivations; it involves fundamentally different sequences of derivations that lead to the same resulting string.

Example of Ambiguity

Consider the regular expression . This expression allows the string “aa” to be derived through two different derivation paths:

1. First derivation:

In this derivation, the first is replaced with , followed by the second , yielding the string “aa.”

2. Second derivation:

Here, the first is replaced with (the empty string), and the subsequent part generates the string “aa.”

In both cases, the resulting string is the same (“aa”), but the derivations differ significantly, illustrating the ambiguity of the regular expression.

Definition

A regular expression is considered ambiguous if its corresponding marked regular expression generates two distinct marked strings and such that, when the indices (or markers) are removed, the resulting unmarked strings are identical.

In other words, ambiguity arises when the structure of the derivation paths differs, but the final derived string remains the same.

Example

Let’s look at the marked version of the regular expression . This regular expression operates over a marked alphabet , where each symbol is uniquely labeled to track different derivation paths.

For example, we can derive the string “aa” in two ways:

• (choosing from the first union and from the middle part)
• (choosing from the middle and from the second union)

Once the indices are removed, both derivations result in the same unmarked string “aa.” This difference in marked derivations that lead to the same unmarked result is a clear indicator of ambiguity.

Ambiguity often arises in expressions with nested Kleene stars. For instance, consider the expression , which is ambiguous because the string “aa” can be derived in at least two different ways:

1. First derivation:

   Here, the inner produces two ‘s, and the outer accepts them as part of the derivation.

2. Second derivation:

   In this case, the inner generates the string “aa” as a whole, and the outer simply accepts it.

Both derivations lead to the same string “aa,” but the process is different, making the expression ambiguous.

While regular expressions are generally designed to describe well-defined languages, ambiguity can complicate the process of understanding and processing such expressions. Ambiguous regular expressions, though rare in most practical applications, can lead to multiple valid interpretations of the same input string, depending on the derivation path.

• In regular language theory, ambiguity is not a major issue, as regular languages are deterministic. However, understanding the possibility of ambiguous expressions is essential for recognizing cases where different derivation paths lead to the same outcome.
• In parsing and syntax analysis, ambiguity can cause confusion, especially in grammars that describe more complex structures. Resolving or avoiding ambiguity ensures that a given string has a unique parse tree, which is critical for applications like compilers and interpreters.

Other Operators in Regular Expressions

In addition to the basic operators of union, concatenation, and Kleene star that form the foundation of regular expressions, there are other derived operators that expand the expressive power of regular expressions. These include operators such as power, cross, and, in extended regular expressions, set-theoretic operations like intersection, complement, and difference.

1. Union: The union operator combines languages so that any string from either language is accepted.
2. Concatenation: The concatenation operator combines strings from two languages by placing them next to each other.
3. Kleene Star (): The Kleene star allows for any number of repetitions (including zero) of a given string or language. It generates the closure of a language under concatenation.

Power and Cross Operators

Definitions

• Power Operator: The power operator, denoted as , represents the repetition of a string or language exactly times (also is allowed in this case).
• Cross Operator: The cross operator is similar to the Kleene star but excludes the empty string. It requires at least one occurrence of the string or language. It is often denoted by .

Example: Floating-Point Numbers

To illustrate these operators, consider the regular expression that describes floating-point fractional numbers, including the possibility of signs and exponents.

Given the alphabet , where represents a decimal digit , we can construct the regular expression:

where:

• represents the optional sign.
• represents the fractional or integer constant.
• represents the optional exponent, possibly signed and preceded by the character .

This expression can generate floating-point numbers such as:

In regular expressions, repetition can be controlled using bounds. A string can repeat from to times, or it can be optional.

• Bounded Repetition: represents the repetition of between and times.
• Optionality: allows to appear optionally, meaning it can either be present or absent in the string.

Extended Regular Expressions

Regular expressions can be extended with set-theoretic operations such as intersection, complement, and difference. These operations enable more complex conditions to be expressed, such as requiring a string to meet multiple criteria simultaneously.

Example: Intersection

Intersection allows for specifying that a string must satisfy multiple conditions at the same time. For instance, suppose we want to describe strings over the alphabet that:

1. Contain the substring .
2. Have an even length.

We can express this using intersection:

This intersection ensures that the string contains the substring and has an even number of characters. For example, the string “abbb” satisfies both conditions.

Example: Complement and Intersection

To illustrate how complement works in combination with intersection, consider the regular expression . This expression generates strings that:

1. Do not start with .
2. Do not end with .
3. Do not contain the substrings or .

We can express the complement of this regular expression as:

Using De Morgan’s laws, this complement can be rewritten as the intersection of the complements of each condition:

Example: Transforming Extended Regular Expressions

Given an extended regular expression over the alphabet , we can transform it into an equivalent regular expression that only uses basic operators such as union (), concatenation (), and Kleene star ().

For example, consider:

This transformation shows how an extended regular expression can be simplified while preserving the language it generates.

Closure of the REG Family with Respect to Operations

In formal language theory, the family refers to the set of regular languages. These are the languages that can be expressed using regular expressions or recognized by finite automata. One of the essential properties of this family is its closure under certain operations.

Let be an operator applied to one or more languages, producing a result that is also a language.

Definition

A family of languages is said to be closed under if, when the operator is applied to one or more languages within the family, the resulting language remains within the same family.

The family of regular languages is closed under several important operators:

1. Concatenation: The language formed by concatenating all possible strings of two languages and is still regular.

2. Union: The union of two regular languages is regular. This is the set of all strings that are either in or in .

3. Kleene Star (): Applying the Kleene star to a regular language produces a regular language consisting of any number (including zero) of concatenations of strings from .

Since regular languages are closed under union, concatenation, and star, they are also closed under derived operators such as:

• Cross (): The cross operation is similar to Kleene star, but requires at least one occurrence of the language’s strings.
• Repetition: Repeating a language between and times is still a regular language.
• Optionality: Adding optionality to a language, meaning it can either be present or absent, remains within the family of regular languages.

Given two regular languages and , the following combinations also yield regular languages:

• (union)
• (concatenation)
• (Kleene star)
• (cross operator)

Property

The family is not just closed under these operators—it is the smallest family that satisfies the following conditions:

1. Contains all finite languages: Any finite set of strings is a regular language.
2. Closed under concatenation, union, and star: Applying these operations to any regular language will still result in a regular language.

This property makes regular languages foundational in language theory, as they form the simplest class of languages that are closed under these operations.

In addition to concatenation, union, and star, regular languages are closed under the following:

• Intersection: The intersection of two regular languages is regular.

• Complement: If is a regular language, then its complement (all strings not in ) is also regular.

• Difference: The difference between two regular languages (strings in but not in ) is regular.

• Mirroring: The mirror of a regular language, where the strings are reversed, is still regular.

These closure properties are important in automata theory and provide powerful tools for reasoning about regular languages.

The family (context-free languages) is larger than but shares some closure properties. For example, is also closed under concatenation, union, and star. However, is a strict subset of :

This means that while every regular language is context-free, not every context-free language is regular.

Linguistic Abstraction

Linguistic abstraction refers to the process of simplifying the phrases of a language by replacing complex symbols with simpler abstract representations. This allows the construction of models that focus on the structure of the language rather than the specific symbols used.

For example, in compiler design, abstract representations (such as regular expressions) are used to describe the syntax of programming languages, while the actual lexical elements (such as keywords or identifiers) are chosen later during the compilation process.

Effective and Abstract Lists

A list is a sequence of elements whose number is not predetermined. Lists can be represented using regular expressions:

• Kleene Star (): Represents a list where the number of elements may be zero or more.

• Kleene Plus (): Represents a list where there is at least one element.

In these expressions, represents an element of the list. The element can be a terminal symbol or a more complex object, such as another list.

When creating lists, it is common to use separators (e.g., commas) between elements and sometimes start and end markers (e.g., parentheses or brackets) to indicate the boundaries of the list.

Definition

The general form of a list with a separator and markers can be described by the regular expression:

where:

• is the start-marker.
• represents an element.
• is the separator.
• is the end-marker.

Alternatively, a similar form with brackets can be:

Examples

1. Begin-End Block:

This can represent a sequence of instructions in a programming block, where each instruction is separated by a semicolon.

2. Procedure Parameter List:

Here, the parameters of a procedure are listed within parentheses, separated by commas.

3. Array Indexing:

This represents an array declaration where multiple indices are provided within square brackets.

Substitution (Replacement)

Substitution is an operation that replaces symbols from one language with elements or phrases from another language. This allows the transformation of strings from a source language over an alphabet into a target language over an alphabet .

Let:

• be the source language.
• be the target language for substitution.
• be a string from the source language.

If , the symbol in is substituted with any string from . This creates a new language over the alphabet , which can be written as:

This substitution allows for the recursive construction of languages by replacing specific symbols with more complex patterns or lists.

Nested Lists

Nested lists are lists that contain other lists as elements. This introduces multiple levels of hierarchy within the list structure, where elements at one level can themselves be lists.

For instance, a nested list can be represented as:

where, the list contains atomic elements , , and a sublist . Nested lists are useful in programming and data structures, where each element can recursively contain other lists or objects.

Footnotes

1. an expression is fully parenthesized means that every operator has its operands enclosed in parentheses, ensuring that the order of operations is explicitly defined. For example, the expression is fully parenthesized, while is not, as it lacks parentheses around the union operation. ↩