Previous chapter: The Büchi Acceptance Condition
This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner
Introduction
Kleene’s theorem states that the set of languages over finite words that can be defined by regular expressions is exactly the set of languages that can be recognized by automata over finite words.
Based on this, we define $\omega$-regular expressions, and finally prove the corresponding theorem for $\omega$-regular languages: Büchi’s characterization theorem.
Regular Expression
Regular expression consist of constants that denote languages of finite words, and
consist of operator symbols that denote operations over these languages.
The collection of regular languages over an alphabet $\Sigma$ is $\mathcal{L}(E)$, where $E$ is a regular expression.
Regular expression can be defined as $E := \varepsilon\mid\varnothing\mid a\in\Sigma\mid E+F\mid E\cdot F\mid E^* $, where:
- empty language: $\varepsilon$,
- empty string language: $\varnothing$,
- singleton language: (single letter from alphabet) $a\in\Sigma$,
- union of regular languages: $E+F$,
- concatenation of regular languages: $E\cdot F$, and
- language with kleene star: $E^*$.
$\textbf{Definition 3.1. } \textit{Regular expressions } \text{are defined as follows:}$
$\begin{array}{l}\hspace{1cm} \cdot \ \text{The constants }\varepsilon\text{ and }\varnothing\text{ are regular expressions.}\newline
\hspace{1cm} \ \ \mathcal{L}(\varepsilon) = \lbrace\varepsilon\rbrace ,\mathcal{L}(\varnothing)=\varnothing.\newline
\hspace{1cm} \cdot \ \text{If }a\in\Sigma\text{ is a symbol, then }a\text{ is a regular expressions.}\newline
\hspace{1cm} \ \ \mathcal{L}(a) = \lbrace a\rbrace .\newline
\hspace{1cm} \cdot \ \text{If }E\text{ and }F\text{ are regular expressions, then }E+F\text{ is a regular expression:}\newline
\hspace{1cm} \ \ \mathcal{L}(E+F) = \mathcal{L}(E)\cup\mathcal{L}(F) .\newline
\hspace{1cm} \cdot \ \text{If }E\text{ and }F\text{ are regular expressions, then }E\cdot F\text{ is a regular expression:}\newline
\hspace{1cm} \ \ \mathcal{L}(E\cdot F) = \lbrace uv\mid u\in\mathcal{L}(E),v\in\mathcal{L}(F)\rbrace.\newline
\hspace{1cm} \cdot \ \text{If }E\text{ is a regular expression, then }E^*\text{ is a regular expression.}\newline
\hspace{1cm} \ \ \mathcal{L}(E^{\ast}) = \lbrace u_1u_2\dots u_n\mid n\in\mathbb{N},u_i\in\mathcal{L}(E)\text{ for all }0\leq i\leq n\rbrace.\end{array}$
Kleene’s Theorem
A language over finite words is regular if it is definable by a regular expression, or
if it is recognized by automata over finite words.
$\textbf{Definition 3.2. } \text{An }\textit{automaton on finite words } \mathcal{A}\text{ is a tuple } (\Sigma,Q,I,T,F), \text{ where }\Sigma\text{ is an input} \newline \text{alphabet, }Q\text{ is a nonempty finite set of states, }I\in Q\text{ is a set of initial states, }\Delta\subseteq Q\times\Sigma\times Q\text{ is}\newline\text{a set of transitions, and }F\subseteq Q\text{ are a set of finite states.}$
Mathematical Definition
An automaton $\mathcal{A}$ accepts a finite word $w \in\Sigma^*$ if there is a finite sequence of states $q(0)q(1) . . . q(|w|)$ such that $q(0)\in I$ and $(q(i),w(i), q(i + 1))\in\Delta$ for all $i < |w|$ and with $q(|w|)\in F$
Explained in Human language
In a nutshell, a finite word $w$ is accepted by an automaton $\mathcal{A} = (\Sigma,Q,I,T,F)$ if:
| Notation | Explaination |
|---|---|
| $\Sigma$ | $w$ is a finite word in $\Sigma$ |
| $Q$ | There exists a finite sequence of states $q(0)q(1) . . . q(|w|)$ |
| $I$ | In such sequence, $q(0)$ is one of the initial state $I$ |
| $T$ | In such sequence, there is transition from $q(i)$ to $q(i+1)$ for each letter $w(i)$, where $i<|w|$ |
| $F$ | In such sequence, $q(|w|)$ is one of the final state $F$, and it will be the last state of the run since there is no more letters |
From accepted word to accepted language
The set of all words accepted by $\mathcal{A}$ is called the language of $\mathcal{A}$, denoted by $\mathcal{L}(\mathcal{A})$.
$\textbf{Theorem 3.1. } \text{(Kleene’s Theorem)}\newline\textit{A language is regular iff it is recognized by some finite word automaton.}$
Next post: $\omega$-regular language
Further Reading: Regular expression,Regular language Kleene star
Please cite the source for reprints, feel free to verify the sources cited in the article, and point out any errors or lack of clarity of expression. You can comment in the comments section below or email to GreenMeeple@yahoo.com