Chapter 3: Regular Expression and Regular Languages

This set of flashcards covers vocabulary and foundational concepts of Regular Expressions and Regular Languages, including operations, grammar types, and the Pumping Lemma.

Regular Languages

A language for which there exists a finite automata; all languages are either regular or non-regular, but never both.

Non-regular languages

Languages that are not accepted by a finite automata, often because they require string comparisons, such as L = \text{{}a^nb^n,n ≥ 0\text{}}.

Concatenation of Strings

Given strings $s = a_1 … a_n$ and $t = b_1 … b_m$, their concatenation is defined as $st = a_1 … a_nb_1 … b_m$.

Concatenation of Languages ($L_1L_2$)

The set of strings formed by taking any string from $L_1$ and any string from $L_2$, defined as L_1L_2 = \text{{}st: s ∈ L_1, t ∈ L_2\text{}}.

Union of Languages ($L_1 ∪ L_2$)

The set of all strings that are contained in either language $L_1$ or language $L_2$.

Star (Kleene closure) of $L$

The set of all strings made up of zero or more chunks from $L$, denoted as $L^* = L^0 ∪ L^1 ∪ L^2 ∪ …$; it is always infinite and always contains the empty string $ε$.

Regular operations

The operations comprising union ($∪$), concatenation ($⋅$), and the star operation ($*$).

Regular Expression (RE)

An algebraic way to describe languages that exactly represents the class of regular languages.

Basis 1 (RE Basis)

If $a$ is any symbol, then $a$ is a regular expression and $L(a) = \text{{}a\text{}}$.

Basis 2 (RE Basis)

$ε$ is a regular expression, and its language is $L(ε) = \text{{}ε\text{}}$.

Basis 3 (RE Basis)

$∅$ is a regular expression, and its language is $L(∅) = ∅$.

RE Precedence of Operators

The order of precedence is highest for the star operation ($*$), followed by concatenation, and then union ($+$, the lowest priority).

Closure properties of Regular languages

The class of regular languages is closed under union, concatenation, star operation, intersection, and complement.

Arden’s Theorem

A theorem used to find the unique solution to the equation $R = P + RQ$ as $R = PQ^*$, provided that $Q$ does not include the empty string $ε$.

Formal Definition of Grammar ($G$)

Defined by a four-tuple $(V, T, P, S)$ where $V$ is variables, $T$ is terminals, $P$ is production rules, and $S$ is the start symbol.

Right-Linear Grammars (RLG)

A grammar where all productions follow the form $A → xB$ or $A → x$, where $x$ is a string of terminals and $A, B$ are variables.

Left-Linear Grammars (LLG)

A grammar where all productions follow the form $A → Bx$ or $A → x$, where $x$ is a string of terminals and $A, B$ are variables.

Regular Grammar

Any grammar that is either right-linear or left-linear.

Chomsky Hierarchy Type 0

Unrestricted grammar.

Chomsky Hierarchy Type 1

Context-sensitive grammar.

Chomsky Hierarchy Type 2

Context-free grammar.

Chomsky Hierarchy Type 3

Regular Grammar.

Pumping Lemma for Regular Languages

A theorem used to prove a language is not regular, stating that for any regular language $L$, there is a pumping length $P$ such that any string $S ∈ L$ with $|S| ≥ P$ can be split into $S = xyz$ where $|y| > 0$, $|xy| ≤ P$, and $xy^iz ∈ L$ for all $i ≥ 0$.