Chapter 0
Mathematical Notions and
Terminology
Alphabets and Strings
Topics
 Alphabets
 Strings
 Languages
Alphabets and Symbols
 Alphabet: any (nonempty) finite set
 Usually assume elements are some kind of characters
 Members of an alphabet are called symbols
 Symbols are usually letters and digits
 Example alphabets: {a}, {a, x}, {0}, {0, 1}
 Usually don't use quotes for characters (ie 'a')
 Usually use different font or context to recognize symbols
 Represent an alphabet with the Greek letters (eg Σ and
Γ which are capital Sigma and capital Gamma)
 Example: Σ = {0, 1}
 Example: let x be an element of Σ
Strings Over an Alphabet
 String: finite sequence of symbols over (ie from) an alphabet
 Symbols are usually written adjacent without commas
 Examples over Σ = {a,b,c,d}: aaa, bac
 Examples over Σ = {0,1}: 000, 01011
 acb is a shorthand for (a, c, b)
 Typically represent strings with letters like u, v, w, x, y, z
 Examples: u = acb, x = 10110
 Frequently the alphabet that strings are formed over is unspecifed and assumed

Example: 0 or more a's followed by a single b
Strings Operations
 We can define operation on strings
 The most common operations are
 Concatenation: Join two or more strings and/or symbols
 Example: x = cab, y = aba , xy = ??
 We freely concatenate any combination of strings and symbols
 Example: xay =
 Superscript: x^{k}
 Reverse  Notation: w^{R}
 Length of string w:
 number of symbols in w
 written w
 cab = 3
The Empty String
 The string with no symbols
 If x is the empty string, then x = 0
 Conundrum: How do we write the empty string?
 Answer: A special symbol: ε
 Symbol λ also used
 Question: Can ε be a symbol in the alphabet we are using to form strings?
 How is ε represented in Ada and Java?
 Plays role of 0 or 1 in a number system
 wε = ?? = ??
 This is called ...
Lexicographic Ordering
 Need a standard order in which to list strings
 Lexicographic ordering: shorter precede longer (eg
{ε, 0, 1, 00, 01, 10, 11, 000, ...})
 Assume symbols have an ordering
Languages
 Language: A set of strings (over an alphabet)
 Examples:
 Over alphabet {a, b, c}:
 L1 = {aaa, aba}
 L2 = {a, aa, aaa}
 Over alphabet {0, 1}:
 L1 = {0}
 L2 = {0, 1, 010}
 Frequently the alphabet that strings are formed over is unspecifed and assumed
Empty Strings and Languages
 Are these two languages different? {00, 11} and {ε, 00, 11}
 Is this a language: {ε}
 Is this a language: {}
 Eventually we will see language specifications that turn out to define empty languages,
although that might not be obvious at first
 Notice the connection between the string (ie sequence of symbols) with no symbols and the language (ie set of strings)
with no elements
 Is this a valid alphabet: Σ = {}
 If it is, what are the strings over Σ?
 If it is, what are the languages over Σ?
 Is it valid? See page 13.
Infinite Languages
 Languages can be finite or infinite
 Infinite languages contain an infinite number of strings
 Example infinite languages:
 All binary strings that start with 0
 What's the shortest string in the language?
 L = {ww^{R}}  for any string w}
 What's wrong with this definition?
 What's the shortest string in the language?
 What language is this: Even length palindromes
 How do we specify odd length palindromes
Infinite Alphabets, Strings, and Languages
 Can an alphabet be infinite?
 Can a string be of infinite length?
 Look at infinite languages above: infinite number of finite strings
 In an infinite language, there is no limit to the length of a string, but the length of each string is finite.
 Remember these definitions!!!
Tools for working with languages on Languages
 We construct 3 tools for working with languages:
 Automata:
 Regular Expressions: Generate (describe) languages
 Grammars: Generate languages
Some Questions when Working with Languages
 Each tool can be used to ask 2 questions:
 What strings are in the language?
 Is a given string in the language?
ITEC 420 Course Page,
Last modified on