Introduction to the Theory of Computation | Regular Languages

Definition: If $A$ is the set of all strings that machine $M$ accepts, we say that $A$ is the language of machine $M$ . We say that $M$ recognizes/accept $A$ .

Definition: Let $A$ and $B$ be languages.
- we define union as $A \cup B = {x ∣ x \in A$ or $x \in B}$
- we define concatenation as $A \circ B = {x y ∣ x \in A$ and $y \in B}$
- we define star as $A^{*} = {x_{1} x_{2} \dots x_{k} ∣ k \geq 0$ and each $x_{i} \in A}$ \

Deterministic Finite Automaton

Definite: A deterministic finite automaton 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 Σ ⟶ Q$ is the transition function.
$q_{0} \in Q$ is the starting state.
$F \subseteq Q$ is the set of accept/final states.

Definition: Let $M = (Q, Σ, δ, q_{0}, F)$ be a deterministic finite automaton and let $w = w_{1} w_{2} \dots w_{n}$ be a string were each $w_{i}$ is a member of the alphaet $Σ$ . Then $M$ aceepts $w$ if a sequence of states $r_{0}, r_{1}, \dots, r_{n}$ in $Q$ exists with three conditions

$r_{0} = q_{0}$
$δ (r_{i}, w_{i + 1}) = r_{i + 1}$
$r_{n} \in F$

Nondeterministic Finite Automaton

Definite: A nondeterministic finite automaton 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 Σ_{ε} ⟶ P (Q)$ is the transition function. (Here $P (Q)$ is called the power set of $Q$ .
$q_{0} \in Q$ is the starting state.
$F \subseteq Q$ is the set of accept/final states.

Definition: Let $M = (Q, Σ, δ, q_{0}, F)$ be a nondeterministic finite automaton and let $w = w_{1} w_{2} \dots w_{n}$ be a string were each $w_{i}$ is a member of the alphaet $Σ$ . Then $M$ aceepts $w$ if a sequence of states $r_{0}, r_{1}, \dots, r_{n}$ in $Q$ exists with three conditions

$r_{0} = q_{0}$
$r_{i + 1} \in δ (r_{i}, w_{i + 1})$
$r_{n} \in F$

Equivalence of Nondeterministic Finite Automaton and Deterministic Finite Automaton

Definition: The subset construction starts from an NFA $N = (Q_{N}, Σ, δ_{N}, q_{0}, F_{n})$ . Its goal is the DFA $D = (Q_{D}, Σ, δ_{D}, {q_{0}}, F_{D})$ such that $L (D) = L (N)$

$Q_{D}$ is the set of subsets of $Q_{N}$
$F_{D}$ is the set of states that include at lease on accepting state of $N$ .
For each set $S \subseteq Q_{D}$ and for each input symbol $a$ in $Σ$ , $δ_{D} (S, a) = ⋃_{p in S} δ_{N} (p, a)$

Proof: If is the DFA $D = (Q_{D}, Σ, δ_{D}, {q_{0}}, F_{D})$ constructed from NFA $N = (Q_{N}, Σ, δ_{N}, q_{0}, F_{n})$ , by the subset construction, then $L (D) = L (N)$

// TODO

Regular Expressions

Definition: Say that $R$ is a regular expression if $R$ is

$a$ for some $a$ in the alphabet $Σ$
$ε$
$ϕ$
$(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}$ 1 is a regular expression

A definition of this type is called an inductive definition.

Equivalence with Finite Automaton

Regular Expressions => Finite Automaton

Say that we have a regular expression $R$ describing some language $A$ . We show how to convert $R$ into an NFA recognizing $A$ .

We consider the six cases in the formal definition of regular expressions.

The base cases are:

$a$ : one starting state and one accepting state, with one transition from thpe start to the accepting state corresponding to $a$
$ε$ : one starting state that's also accepting
$ϕ$ : no accepting state

The inductive cases are: (We assume $M_{1}$ and $M_{2}$ respectively recognizes $L (R_{1})$ and $L (R_{2})$

$(R_{1} \cup R_{2})$ : a new 'super starting state' with $ϵ$ transitions to both starting states of $M_{1}$ and $M_{2}$
$(R_{1} \circ R_{2})$ : add $ϵ$ transitions from every accepting states of $M_{1}$ to the starting state of $M_{2}$
$(R_{1}^{*})$ : add $ϵ$ transitions from every accepting states to the starting state and from the starting state to accepting states

Finite Automaton => Regular Expressions

Definition: A generalized nondeterministic finite automaton is a 5-tuple, $(Q, Σ, δ, q_{start}, q_{accept})$ , where

(nfa wherein the transition arrows may have any regular expressions as labels, instead of only members of the alphabet or

ϵ

$Q$ is the finite set of states
$Σ$ is the input alphabet
$δ : (Q - {q_{accept}}) \times (Q - {q_{start}}) ⟶ R$ is the transition function
$q_{start}$ is the starting state
$q_{accept}$ is the accepting state

从 DFA 到 Reg：给每个状态编号， $R_{ijk}$ 表示中间状态最高到 $k$ 的路径的正则表示。得到转移方程 $R_{ijk} = R_{ij (k - 1)} + R_{ik (k - 1)} (R_{kk (k - 1)}) * R_{kj (k - 1)}$

从 DFA 到 Reg：通过消除每条初始状态到某个接受状态路径上的状态来构造正则表达式（有多个接受状态的话就有多条路径，最后将每条路径对应的正则表达式合起来每消除一个状态 $p_{s}$ 就为其每个前驱 $q_{i}$ 及每个后继 $q_{j}$ 添加一条 $r_{i \to s} r_{s \to s}^{*} r_{s \to j}$

消到最后剩一个开始状态和接受状态，看67页

The Pumping Lemma For Regular Languages

Pumping Lemma states that If $A$ is a regular language, then there is a number $p$ (called the pumping length) where if $s$ is any string in $A$ of length at least $p$ , then $s$ may be divided into three pieces, $s = x yz$ , satisfying the following conditions:

$∣ y ∣ > 0$
$∣ x y ∣ \leq p$
$\forall i \geq 0, x y^{i} z \in A$

Proof: Let $M = (Q, Σ, δ, q_{0}, F)$ be a DFA recognizing $A$ and $p$ be the number of states of $M$ . Let $s = s_{1} s_{2} \dots s_{n}$ be a string in $A$ of length $n$ , where $n \geq p$ .

$M$ accepts $s$ , then there is a sequence of states $r_{0}, r_{1}, \dots, r_{n}$ in $Q$ . This sequence has length $n + 1$ , which is at least $p + 1$ .
Among the first $p + 1$ elements in the sequence, two must be the same state, by the pigeonhole principle. We call the first of these positioned at $i$ and the second $j$ .

Then we can spit $s$ into $s = x yz$ where,

$x$ takes $M$ from $r_{0}$ to $r_{i}$
$y$ takes $M$ from $r_{i}$ to $r_{j}$ ( $r_{i}$ and $r_{j}$ are the same state
$z$ takes $M$ from $r_{j}$ to $r_{n}$ which is an accepting state.

which satisfies the 3 conditions:

$∣ y ∣ > 0$ is by definition
$j$ is among the first $p + 1$ , then $∣ x y ∣ \leq p$ .
$y$ will not change the state as a result, then M must accept $x y^{i} z$ for all $i \geq 0$

Regular Languages

Definition: $A$ language is called a regular language if some finite automaton recognizes it.

Theorem: THe class of regular language is closed under the union operation

Theorem: THe class of regular language is closed under the concatenation operation

Theorem: THe class of regular language is closed under the star operation