Regular Language

Overview

Finite automata are classified as either deterministic or nondeterministic. These two representations are equivalent.

If $s$ is processed by finite automaton $M$ such that $M$ finishes in an accept state, we say $M$ accepts $s$ . Otherwise $M$ rejects $s$ . If $A$ is the set of all strings that $M$ accepts, we say that $A$ is the language of machine $M$ , denoted $L (M) = A$ . We say that $M$ recognizes $A$ .

A language is called a regular language if a finite automaton recognizes it.

Automaton

Deterministic

A deterministic finite automaton (DFA) is a $5$ -tuple $⟨ Q, Σ, δ, q_{0}, F ⟩$ , where

$Q$ is a finite set called the states;
$Σ$ is a finite set called the alphabet;
$δ : Q \times Σ \to Q$ is the transition function;
$q_{0} \in Q$ is the start state; and
$F \subseteq Q$ is the set of final states.

These automaton are typically denoted using a state diagram like below. The start state is indicated by an arrow pointing at it from nowhere. An accept state is denoted with a double circle.

Nondeterministic

A nondeterministic finite automaton (NFA) is a $5$ -tuple $⟨ Q, Σ, δ, q_{0}, F ⟩$ , where

$Q$ is a finite set called the states;
$Σ$ is a finite set called the alphabet;
$δ : Q \times (Σ \cup {ϵ}) \to P (Q)$ is the transition function;
$q_{0} \in Q$ is the start state; and
$F \subseteq Q$ is the set of final states.

Like DFAs, these automaton are typically denoted using a state diagram. Unlike DFAs, not every state needs an exiting transition arrow for each symbol in the alphabet. Also, arrows can be labeled $ϵ$ for the empty string.

Equivalence

Two finite automaton are equivalent if they recognize the same language. As it turns out, every NFA can be converted to an equivalent DFA.

Epsilon-Closure

Let $N = ⟨ Q, Σ, δ, q_{0}, F ⟩$ be an NFA. Define the $ϵ$ -closure of a set of states $A \subseteq Q$ as all states reachable from any state in $A$ along zero or more $ϵ$ -transitions.

More formally, define $f : P (Q) \to P (Q)$ to be given by

f (R) = ⋃ {δ (r, ϵ) ∣ r \in R} .

Then the $ϵ$ -closure of $A \subseteq Q$ using the top-down approach is

ϵ^{*} (A) = ⋂ {X ∣ A \subseteq X \subseteq P (Q) \land f [[X]] \subseteq X} .

Using the bottom-up approach,

ϵ_{*} (A) = ⋃_{n \in N} h (n)

where $h : N \to P (Q)$ is defined in the usual way.

Power Set Construction

The power set construction describes the process by which an NFA can be converted into an equivalent DFA:

Let $N$ = $⟨ Q, Σ, δ, q_{0}, F ⟩$ be the NFA recognizing some language $A$ . Define the following:

$Q^{'} = P (Q)$
$Σ^{'} = Σ - {ϵ}$
$δ^{'} (R, a) = ⋃_{r \in R} ϵ (δ (r, a))$
$q_{0}^{'} = ϵ ({q_{0}})$
$F^{'} = {R \in Q^{'} ∣ R contains an accept state of N}$

Then $M = ⟨ Q^{'}, Σ^{'}, δ^{'}, q_{0}^{'}, F^{'} ⟩$ is a DFA equivalent to $N$ , i.e. it also recognizes $A$ .

Regular Expressions

A regular expression is a textual representation of some language. They are equivalent to finite automaton in their descriptive power. More formally, we say $R$ is a regular expression if $R$ is

$a$ for some $a$ in the alphabet $Σ$ ,
$ϵ$ ,
$\emptyset$ ,
$(R_{1} \cup R_{2})$ where $R_{1}$ and $R_{2}$ are regular expressions,
$(R_{1} \circ R_{2})$ where $R_{1}$ and $R_{2}$ are regular expressions,
$(R_{1}^{*})$ where $R_{1}$ is a regular expression.

Note individual symbols like $a \in Σ$ or $ϵ$ are interpreted as singleton sets.

GNFA

A generalized nondeterministic finite automaton (GNFA) is an NFA in which the transition arrows may have any regular expressions as labels, instead of only members of an alphabet (or $ϵ$ ).

These are useful for constructing a regular expression from a DFA. In particular, every DFA can be converted into a GNFA and every GNFA can be converted into a 2-state GNFA whose sole transition is labeled with the desired regular expression.

Extended

The following ERE (Extended Regular Expression) operators were defined to achieve consistency between programs like grep, sed, and awk. In POSIX, regexps are greedy.

. matches any single character.
- There exist application-specific exclusions. For instance, newlines and the NUL character are often ignored.
[...], the bracket expression, matches any enclosed character.
- An optional - can be included to denote a range.
- - is treated literally if its the first or last specified character.
- ] is treated literally if its the first specified character.
- ^ complements the set if its the first specified character.
^ is the leading anchor. It matches the starting position of a string.
$ is the trailing anchor. It matches the ending position of a string.
* matches the preceding element zero or more times.
+ matches the preceding element one or more times.
? matches the preceding element zero or one times.
{n}, an interval expression, matches the preceding element n times.
- {n,} matches the preceding element at least n times.
- {n,m} matches the preceding element between n and m times.
- Interval expressions cannot contain repetition counts > 255. Results are otherwise undefined.
| is the alternation operator. It allows specifying match alternatives.

Character Classes

ERE also introduced notation for describing a class of characters specific to a given locale/character set:

Class	Similar To	Meaning
`[:alnum:]`	`[A-Za-z0-9]`	Alphanumeric characters
`[:alpha:]`	`[A-Za-z]`	Alphabetic characters
`[:blank:]`	`[ \t]`	`' '` and `TAB` characters
`[:cntrl:]`		Control characters
`[:digit:]`	`[0-9]`	Numeric characters
`[:graph:]`	`[^ [:cntrl:]]`	Printable and visible characters
`[:lower:]`	`[a-z]`	Lowercase alphabetic characters
`[:print:]`	`[ [:graph:]]`	Printable characters
`[:punct:]`		All graphic characters except letters and digits
`[:space:]`	`[ \t\n\r\f\v]`	Whitespace characters
`[:upper:]`	`[A-Z]`	Uppercase alphabetic characters
`[:xdigit:]`	`[0-9A-Fa-f]`	Hexadecimal digits

Backtracking

Many popular implementations of regular expression libraries use backtracking instead of finite automaton. This implementation strategy is notorious for being exponentially slow.

The only situation in which backtracking is the best known option is in the case of backreferences, i.e. a substring that matches a previously matched portion of the "regular expression" (quoted since backreferences are not actual regular expressions in the theoretical sense).

Thompson's Algorithm

Thompson's algorithm converts regular expressions into an NFA containing a number of states equal to at most the length of the expression. The total NFA is built up from partial NFAs for each subexpression, with a different construction for each operator. Each partial NFA has dangling arrows pointing to nothing. The result is concatenated together at the end.

Once built, the NFA is simulated in a multiple-state fashion. Every possible branch of navigation is executed simultaneously.

Closure Operations

Let $A$ and $B$ be regular languages over alphabet $Σ$ . Such languages are closed over the regular operations which include:

Union: $A \cup B = {x ∣ x \in A \lor x \in B}$
Intersection: $A \cap B = {x ∣ x \in A \land x \in B}$
Complement: $\overset{―}{A} = {x ∣ x \in Σ^{*} - A}$
Reversal: $A^{R} = {x^{R} ∣ x \in A}$
Concatenation: $A \circ B = {x y ∣ x \in A \land y \in B}$
Kleene star: $A^{*} = {x_{1} x_{2} \dots x_{k} ∣ k \geq 0 \land x_{i} \in A}$

Product Construction

Let $D_{1} = ⟨ Q_{1}, Σ, δ_{1}, q_{1}, F_{1} ⟩$ and $D_{2} = ⟨ Q_{2}, Σ, δ_{2}, q_{2}, F_{2} ⟩$ be DFAs. Then the product construction of $D_{1}$ and $D_{2}$ is DFA $D = D_{1} \times D_{2} = ⟨ Q, Σ, δ, q_{0}, F ⟩$ where

$Q = Q_{1} \times Q_{2}$ ,
$δ (⟨ r_{1}, r_{2} ⟩, a) = ⟨ δ_{1} (r_{1}, a), δ_{2} (r_{2}, a) ⟩$
$q_{0} = ⟨ q_{1}, q_{2} ⟩$

The definition of $F$ depends on the semantics desired.

Pumping Lemma

Let $L$ be a regular language. Then there exists a pumping constant $p$ where, if $s$ is any string in $L$ of length at least $p$ , then $s$ can be written as $s = x y z$ such that

$x y^{i} z \in L$ for any integer $i \geq 0$ ,
$| y | > 0$ , and
$| x y | \leq p$ .