[Overview] [Previous] [Next]

Languages

Definitions 1

Important! An alphabet is a finite, nonempty set of symbols. We use sigma to denote this alphabet. Note: Symbols may be more than one English letter long, e.g. while is a single symbol in Pascal.

Important! A string is a finite sequence of symbols from sigma.

The length of a string s, denoted |s|, is the number of symbols in it.

Important! The empty string is the string of length zero.
It really looks like this:
but for convenience we usually write it like this: empty string

Important! sigmastar denotes the set of all sequences of strings that are composed of zero or more symbols of sigma.

Important! sigmaplus denotes the set of all sequences of strings composed of one or more symbols of sigma. That is, sigmaplus = sigmastar - {empty string}.

Important! A language is a subset of sigmastar.



Copyright 1996 by David Matuszek
Last modified Jan 31, 1996