2. Alphabets, words, languages

Words

Alphabet

An alphabet is a finite set $S$ of symbols. Examples of alphabets include: $\{a,b,c,...,z\}$, $\{0,1\}$ and $\{\#,\text{!},\text{=}\}$.

Link to original

Word (finite automata)

A word or string (over an alphabet $S$) is a finite sequence of symbols from $S$ written without commas. For example, $tortoise,abc$ or $11101110101011,1110$.

Link to original

Empty word

The empty word, denoted by $ϵ$, is a word over any alphabet. We assume that $ϵ$ is not a symbol of any of our alphabets.

Link to original

Length (word)

The length of a word $w$ is $|w|=\text{ the number of symbols in }w$. For example, $|azwza|=5$ or $|ϵ|=0$.

Link to original

Concatenation

The concatenation of words $x$ and $y$ is the word $x$ followed by the word $y$, written $xy$. We can use the syntax $\text{foo}@\text{bar}=\text{foobar}$.

Formally, $A@B\stackrel{def}{=}\{s_1@s_2|s_1\in A\wedge s_2\in B\}$.

Link to original

Repetition

The repetition of words can be denoted by the power, $w^n=\stackrel{n}{\overbrace{ww...w}}$. For example, $(ab{)}^0=ϵ$, $(01{)}^3=010101$ or $a^4=aaaa$.

Link to original

For every word $x$, $xϵ=ϵx=x$.

Prefix

If $w=xyz$, then $xy$ is a prefix of $w$.

Link to original

Suffix

If $w=xyz$, then $yz$ is a suffix of $w$.

Link to original

Languages

Language

A language (over an alphabet $S$) is a set of words over $S$.

For example, given $S=\{a,b,c,...,z\}$.

• $L_1=\text{ all English words}$
• $L_2=\text{ all Latin words}$
• $L_3=\{ghgkrf,oputj,erwwq\}$

Given $S=\{0,1\}$:

• $L_4=\{001,101010,111,1001\}$
• $L_5=\{0^n{1}^m|n\text{ is even},m\text{ is odd}\}$

Link to original