PlanetMath: alphabet

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (211)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (36)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

alphabet

(Definition)

An alphabet $\Sigma$ is a nonempty finite set such that every string formed by elements of $\Sigma$ can be decomposed uniquely into elements of $\Sigma$ .

For example, $\{b,lo,g,bl,og\}$ is not a valid alphabet because the string can be broken up in two ways: b lo g and bl og. $\{\mathbb{C}a,\ddot{n}a,{\rm d},a\}$ is a valid alphabet, because there is only one way to fully break up any given string formed from it.

If $\Sigma$ is our alphabet and $n \in \mathbb{Z}^+$ , we define the following as the powers of $\Sigma$ :

$\Sigma^0 = {\lambda }$ , where $\lambda$ stands for the empty string.
$\Sigma^n = \{xy\vert x \in \Sigma, y \in \Sigma^{n-1}\}$ ( is the juxtaposition of and )

So, $\Sigma^n$ is the set of all strings formed from $\Sigma$ of length .

"alphabet" is owned by mathcam. [ full author list (2) | owner history (2) ]

(view preamble)

See Also: Kleene star, substring, language, Huffman coding, word

Other names:

powers of an alphabet

Log in to rate this entry.
(view current ratings)

Cross-references: length, juxtaposition, empty string, powers, string, finite set
There are 60 references to this entry.

This is version 3 of alphabet, born on 2002-02-02, modified 2004-09-13.
Object id is 1681, canonical name is Alphabet.
Accessed 9155 times total.

Classification:

AMS MSC:

03C07 (Mathematical logic and foundations :: Model theory :: Basic properties of first-order languages and structures)

Pending Errata and Addenda

None.[ View all 3 ]

Discussion

forum policy

No messages.

Interact