Alphabet (computer science)


Alphabet (computer science)

In computer science, an alphabet is a, usually finite, set of characters or digits. The most common alphabet is {0,1}, the binary alphabet. A finite string is a finite sequence of characters from an alphabet; for instance a binary string is a string drawn from the alphabet {0,1}. An infinite sequence of characters may be constructed from elements of an alphabet as well.

Given an alphabet Sigma, we write Sigma^* to denote the set of all finite strings over the alphabet Sigma. Here, the {}^* denotes the Kleene star operator. We write Sigma^infty (or occasionally, Sigma^N or Sigma^omega) to denote the set of all infinite sequences over the alphabet Sigma.

For example, if we use the binary alphabet {0,1}, the strings {ε, 0, 1, 00, 01, 10, 11, 000, etc.) would all be in the Kleene closure of the alphabet (where ε represents the empty string)

Alphabets are important in the use of formal languages, automata and semiautomata. In most cases, for defining instances of automata, such as deterministic finite automata (DFAs), it is required to specify an alphabet from which the input strings for the automaton are built.

See also

*Formal language
*Syntax
*Semantics


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • String (computer science) — In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet. In computer programming, a string is traditionally a sequence of… …   Wikipedia

  • Production (computer science) — A production or production rule in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences. A finite set of productions P is the main component in the specification of …   Wikipedia

  • Unification (computer science) — Unification, in computer science and logic, is an algorithmic process by which one attempts to solve the satisfiability problem. The goal of unification is to find a substitution which demonstrates that two seemingly different terms are in fact… …   Wikipedia

  • Convolution (computer science) — In computer science, specifically formal languages, convolution (sometimes referred to as zip) is a function which maps a tuple of sequences into a sequence of tuples. Example The convolution of and, fish, be is Definition Let Σ be an alphabet, # …   Wikipedia

  • Alphabet (disambiguation) — An alphabet is a complete standardized set of letters basic written symbols each of which roughly represents a phoneme of a spoken language, either as it exists now or as it may have been in the past. * Alphabets derived from the Latin ** Latin… …   Wikipedia

  • computer — computerlike, adj. /keuhm pyooh teuhr/, n. 1. Also called processor. an electronic device designed to accept data, perform prescribed mathematical and logical operations at high speed, and display the results of these operations. Cf. analog… …   Universalium

  • Computer Russification — In computing, Russification is the localization of computers and software, i.e., making the user interface of a computer and software to communicate in the Russian language and alphabet. Among the problems associated with Russification was… …   Wikipedia

  • Computer software — Software redirects here. For other uses, see Software (disambiguation). Computer software, or just software, is a collection of computer programs and related data that provide the instructions for telling a computer what to do and how to do it.… …   Wikipedia

  • Computer role-playing game — A computer role playing game (CRPGcite web title = CRPG The Online Dictionary. url=http://acronyms.thefreedictionary.com/CRPG accessdate = 2006 08 09 ] ) is a broad video game genre originally developed for personal computers and other home… …   Wikipedia

  • Computer — Ordinateur Wikipédia …   Wikipédia en Français