Regular Languages

Regular languages are the simplest class of languages in the Chomsky hierarchy.

They are built using simple operations on basic languages.

Basic Languages

For a given alphabet $\Sigma$, its basic languages are:

• $\set{a}$ for each symbol $a \in Σ$
• $\varnothing$ (empty language)
• $\set{\lambda}$ (language containing the null string)

Construction of Regular Languages

Regular languages are obtained from basic languages using:

• Union
• Concatenation
• Kleene star

Using only concatenation gives single-string languages. Union and * allow infinite languages.

Regular Expressions

A regular expression is a symbolic representation of a regular language. Every regular language has a regular expression.

A regular expression describes the typical form of strings in the language.

Example: $1*10$ means any number of $1$s followed by $10$.

Notation Rules

• { } are removed or replaced by ( )
• Union $\cup$ is written as $|$
• Concatenation is written by juxtaposition

Example: ${0} ∪ {1}$ → $0|1$

Recursive Definition of Regular Expressions

Let $\Sigma$ be an alphabet.

Regular expressions are defined as follows:

1. $\varnothing$ is a regular expression and denotes $\varnothing$
2. $\lambda$ is a regular expression and denotes $\set{\lambda}$
3. For each $a \in \Sigma$, $a$ is a regular expression denoting $\set{a}$
4. If $p$ and $q$ are regular expressions:
   • $(p | q)$ denotes union
   • $(pq)$ denotes concatenation
   • $(p*)$ denotes Kleene star

Only expressions formed using these rules are valid.

Operator Precedence

To reduce parentheses:

• $*$ has highest precedence
• Concatenation has next highest
• $|$ has lowest precedence

Examples:

• $a|((b*)c)$ → $a|b*c$
• $((0(1*))|0)$ → $01*|0$

Equivalence of Regular Expressions

2 regular expressions are equal iff they denote the same language.

Examples:

• $1*(1|Λ) = 1*$
• $1*1* = 1*$
• $0* | 1* ≠ (0|1)*$
• $(0*1*)* = (0|1)*$

Recognizing a Language

Language recognition means deciding whether a given string belongs to a language.

Recognition is done by reading input left to right in one pass.

The machine must remember limited information.