Show Question
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}

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

Source

Introduction to the Theory of Computation, Sipser