\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
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