deepdream of
          a sidewalk
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 accepts w}. A language is called a regular language if some finite automaton recognizes it.


Example

Examples of alphabets:

Σ1={0,1}Σ2={a,b,c,....,z}Γ={0,1,x,y,z} (symbol: capital gamma)

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