Reference no: EM131467496

Question: Lets define the set Σ = { a, b, c, ..., z } of all English letters (the reason for the notation Σ here will become clearer later on when we discuss formal languages). A string of symbols from Σ is a finite sequence of letters. For example, "math" and "about" are both strings. We;ll denote the empty string of no letters using the symbol ε (the Greek letter epsilon). We can then let Σ* be the set of all strings made from letters in Σ. Formally, we'll say that Σ* = { w | w is a string of letters in Σ } The normal way that we sort English words is called the lexicographical ordering on strings. In this ordering, we proceed across the characters of two words w1 and w2 from the left to the right.

If we find that the current character of one word precedes the current character of the other, then we decide that the first word precedes the second word. For example, "apple" comes before "azure." Otherwise, if we exhaust all characters of one word before the other, we declare that this word comes first. For example, "ha" precedes "happy." Is the lexicographical ordering on strings a well-ordering? If so, prove it. If not, find a set of strings that contains no least element.