Previous chapter: The Logic-Automata Connection
This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner
2.1 Preliminaries
| Basic math notations | Example |
|---|---|
| Natural numbers | $\mathbb{N} = \lbrace 0,1,2,3\dots\rbrace$ |
| Positive Natural numbers | $\mathbb{N}^+ = \lbrace 1,2,3\dots\rbrace$ |
| Numbers from $n$ to $m$ | $[n,m] = \lbrace n,n+1,\dots,m\rbrace$ For $n,m\in \mathbb{N}$ with $n\leq m$ |
| Numbers from $0$ to $m$ | $[m] = \lbrace 0,1,\dots,m\rbrace$ |
$$$$
| Alphabet and Letter | Example |
|---|---|
| Alphabet | a nonempty, finite set of symbols, usually denoted by $\Sigma$ |
| Letter | elements of an alphabets, denoted by $\sigma$ |
$$$$
| Finite and Infinite Word | Example |
|---|---|
| Finite Words | concatenation $w=w(0)w(1)\dots w(n-1)$ of finitely many letters of $\Sigma$ |
| Infinite Words | $\alpha$ (will be explained in chapter 2.3 |
| $n$-th letter of word $w$ | $w(n)$ for each $n\in [|w| - 1]$ |
| Length of words $w$ | $|w|$ |
| set of all finite words | \Sigma^*$ |
| Infinite Words | $\alpha$ (will be explained in chapter 2.3 |
| set of all non-empty finite words | $\Sigma^+ = \Sigma^* \backslash \lbrace \epsilon \rbrace$ |
| set of all infinite words | $\Sigma^\omega$ |
$$$$
| Language | Example |
|---|---|
| language over finite words ($\omega$-language) | each subset of $\Sigma^*$ |
| language over infinite words ($\omega$-language) | each subset of $\Sigma^\omega$ |
Next chapter: Automata over Infinite Words
Further Reading: Büchi automaton, Omega language
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