Math and science::Theory of Computation

# Alphabets and languages

An alphabet is defined to be any nonempty finite set. The members of an alphabet are the symbols of the alphabet.

A string over an alphabet is a finite sequence of symbols from that alphabet.

A language is a set of strings. A language is prefix-free if no member is a proper prefix of another.

A string is a proper prefix of another if it is a prefix but not equal to the other.

We say that a finite machine \( M \) recognizes language \( A \) if \( A = \{w | M \text{ accepts } w \} \). A language is called a regular language if some finite automaton recognizes it.

### Example

Examples of alphabets:

\[\begin{aligned} \\

\Sigma_1 &= \{0, 1\} \\

\Sigma_2 &= \{a, b, c, ...., z\} \\

\Gamma &= \{0, 1, x, y, z\} \text{ (symbol: capital gamma)} \\

\end{aligned} \]

\Sigma_1 &= \{0, 1\} \\

\Sigma_2 &= \{a, b, c, ...., z\} \\

\Gamma &= \{0, 1, x, y, z\} \text{ (symbol: capital gamma)} \\

\end{aligned} \]

Capital Greek characters are used to denote alphabets and lowercase Latin characters are used to denote symbols.