Formal language

Definition

• An alphabet is a finite set $\Sigma$.
• Elements of an alphabet $\Sigma$ are called characters.
• A string over $\Sigma$ is a finite sequence of characters from $\Sigma$.
• A (formal) language$L$ over $\Sigma$ is a set of strings

Notations:

• The empty string containing no characters is denoted $\varepsilon$.
• The set of all strings over $\Sigma$ is denoted $\Sigma^*$.
• So a language over $\Sigma$ is a subset $L \subseteq \Sigma^*$.

Example

• $\Sigma = \{a, b\}$.
• $\Sigma^* \ni \varepsilon, a, abb, aabaaabbabaaabaaaabbb$

Example

• $\Sigma = \{a, b, c\}$.
• $L$ is the language of palindromes over $\Sigma$.
• $L = \{\varepsilon, a, b, c, aa, bb, cc, aaa, aba, aca, bab, \dots\}$.

Example
Programming codes, mathematical expressions, logic formulas.

Formal language vs Natural language

Key question:
How to efficiently describe a language?
(not by listing all its strings).

Regular language

• Union$L_1 \cup L_2$.
• Concatenation$L_1L_2 = \{xy \in \Sigma^* \mid x \in L_1, y \in L_2\}$.
• Power$L^0 = \{\varepsilon\}$. $L^{n+1} = LL^n$.
• Kleene closure$L^* = \bigcup_{i=0}^\infty L^i = \{x \in \Sigma^* \mid \exists n, x \in L^n\}$.

Definition: The collection of regular languages can be defined recursively as follows:

• The empty language $\emptyset$ and $\{c\}$ for $c \in \Sigma$ are regular languages.
• If $L$ is a regular language, so are $L^*$ and $L^0 = \{\varepsilon\}$.
• If $L_1$ and $L_2$ are regular languages, so are $L_1 \cup L_2$ and $L_1L_2$.

Deterministic finite automaton

A mathematical model of computation. Can be used to determine whether a string is within a language.

Definition: A deterministic finite automaton (plural automata) consists of a set $Q$ of states and a transition function $\tau: Q \times \Sigma \to Q$. A unique state $q_0 \in Q$ is designated as the initial state, and some states $F \subseteq Q$ are designated as the final states.

An automaton runs on an input string $s = c_1 \dots c_n$ and answers YES or NO.

• Initially, the automaton is in the initial state $r_0 = q_0$.
• After $k$ steps, the state of the automaton is denoted $r_k$.
• At the $k$-th step, the automaton reads the $k$-th character $c_k$ of $s$, then transitions from the state $r_{k-1}$ to $r_k = \tau(r_{k-1}, c_k)$.
• After $n$ steps, the string is accepted if $r_n \in F$ is a final state, and rejected otherwise.

Definition: The language of an automaton is the set of strings accepted by this automaton.

Theorem: A language is regular iff it is the language of a deterministic finite automaton.

Example

• The string 010110 is accepted.
• The string 101000 is rejected.
• The string 11011100 is?

Example

Nondeterministic finite automaton

In an NFA,

• For a state-character pair in $Q \times \Sigma$, there might be zero or several possible transitions (non-deterministic).
• There is an $\varepsilon$-transition that can be followed for any number of times without consuming any character in the input string.
• The input string is accepted iff there exists a sequence of transitions that leads to a final state.

Example

Theorem (NFA=DFA) A language can be accepted by a DFA iff it can be accepted by an NFA.

Proof (omitted) by powerset construction.

Example

Theorem: A language is regular iff it is the language of a NFA.

Formal grammar

Definition: A formal grammar consists of

• A set $\Sigma$ of terminal symbols.
• A set $N$ of nonterminal symbols disjoint from $\Sigma$.
• A set $P$ of production rules of the form
  $(\Sigma \cup N)^* N (\Sigma \cup N)^* \to (\Sigma \cup N)^*$
• A distinguished start symbol$S \in N$.

Example:

• $S \to aSb$, $S \to ba$.
• $S \to a$, $S \to SS$, $aSa \to b$.

Regular grammar

Definition: A (right-)regular grammar is a formal grammar such that each production rule is of the following forms

• $A \to \varepsilon$.
• $A \to a$.
• $A \to aB$.
  where $A, B \in N$ and $a \in \Sigma$.

Theorem: A language is regular iff it can be generated by a (right-)regular grammar.

If we replace the last production rule by $A \to Ba$, we obtain a left-regular grammar, equivalent to the right-regular grammar.

However, if both $A \to Ba$ and $A \to aB$ are included in the production rules, the language is not regular.

Regular expression

A convenient and popular way to describe a regular language. Let $R$ be a regular expression, we use $\mathcal{L}(R)$ to denote the language it describes.

Regular expressions (regex) start with the atomic regular expressions.

• the empty language $\emptyset$, $\mathcal{L}(\emptyset) = \emptyset$.
• the empty string $\varepsilon$, $\mathcal{L}(\varepsilon) = \{\varepsilon\}$.
• for $a \in \Sigma$, $\mathcal{L}(a) = \{a\}$.

Then we combine regular expressions in the following ways (in the order of increasing precedence!).

• Or (union of languages).
  $\mathcal{L}(R_1|R_2) = \mathcal{L}(R_1) \cup \mathcal{L}(R_2)$.
• Concatenation.
  $\mathcal{L}(R_1R_2) = \mathcal{L}(R_1)\mathcal{L}(R_2)$.
• Kleene closure.
  $\mathcal{L}(R^*) = \mathcal{L}(R)^*$.

Example

• (0|1)*00(0|1)*, $\Sigma^*$00$\Sigma^*$.
• $\Sigma\Sigma\Sigma\Sigma$, $\Sigma^4$.
• 1*(0|$\varepsilon$)1*, 1*0?1*.
• [A][A]*(.[A][A]*)*@[A][A]*.[A][A]*(.[A][A]*)*, [A]+(.[A]+)*[A]+(.[A]+)+.

By definition

Theorem: A language is regular iff it is the language of a regular expression.

The set of regular expressions is itself a language, but not a regular language.

POSIX regex standard

This is the syntax used by many practical tools such as grep. It is a convenient shorthand for writing regular languages.

• . matches any single character.
• [abc] matches one character chosen from the set {a,b,c}.
• [A-Z] matches one uppercase letter in the range A to Z.
• R+ means one or more copies of R.
• R? means zero or one copy of R.
• R* means zero or more copies of R.
• (R) groups a subexpression.
• R|S means either R or S.

Example
[A-Za-z]+@[A-Za-z]+\.[A-Za-z]+ matches an email pattern.

Context-free grammar

Definition: A context-free grammar is a formal grammar such that the lhs of each production rule is a single non-terminal symbol. A language is context-free iff it can be generated by a context-free grammar.

Example

• $S \to aSa$, $S \to bSb$, $S \to \varepsilon$.
• $S \to SS$, $S \to (S)$, $S \to ()$.