Chapter II Languages

Definition
An alphabet å is any finite set. (The elements of å are usually 
called letters or symbols.)
A string or word over å is a finite sequence of symbols of å.
A language over å is any set of words over å. 
The empty string or null string L is the string with no letters 
in it.

Example English
	å = {English words}
	L = {valid English sentences}

NOTE: According to this definition, what we ordinarily call a sentence is called a word.

	English	Formal language

	dictionary	alphabet
	word		symbol
	sentence	word

Example Pascal
	å = {	A, B, . . . , Z, a, b, . . . , z, 
		if, then, else, . . . 
		abs, sqr, . . . , }
	L = { Pascal programs

Example 	Powers of x 
	å = {x}
	L = {L, x, xx, . . . } = {xn: n >= 0} 
	That is, xn is x concatenated with itself n times.  Define xn+m.

Example Binary numbers
	å = {0, 1}
	L = {binary numbers} That is, L consists of all nonempty finite strings of 
				0's and 1's where the first number is not 0.

Definition 
The length of a word w is the number of symbols in w. 

Example: length

Definition 	
The reverse of a word w = w1 w2 w3 . . . wn  is the word
wn . . . w3 w2 w1.

Lemma reverse (w1w2) = reverse(w2) reverse (w1).


Problem 7 Page 23
(i) 	If x Î PALINDROME then so is xn for any n.
(ii) 	If xn Î PALINDROME for some n > 0 then so is x.
(iii) 	PALINDROME over the alphaber å = {a, b} has 
as many words of length 4 as it does of length 3.

Proof 

(i) Let x Î PALINDROME.  Then 
reverse(xn) = reverse (x) . . . reverse (x) = x . . . x = xn
so that xn Î PALINDROME.

(ii) Let w = xn.  If n = 1, then the result is trivial.  Suppose n > 1.  
Then xn = reverse (xn) = (reverse  (x))n.  Write this as 
x x . . . x = reverse (x) reverse (x) . . . reverse (x). But x and 
reverse (x) have the same length, so that x = reverse (x).

(iii) List all the words. The palindromes of length 3 are 
aaa aba bab bbb.
The palindromes of length 4 are
aaaa abba baab bbbb.  


Definition 
The closure of an alphabet å is the set of all strings over å. The 
closure is denoted å*. This is called the Kleene star. 

Example The closure of the alphabet å = {x} is the set of all 
powers of x.

Definition The closure of a language S is the set of all strings over S. 

Example 	Let S = {ab, ba}. Then S* = {w Î å* | length (w) = 2, 
				  at most 2 occurrences of a or b occur together, and w begins and ends with one occurrence of a or b}.

Example 	Let S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9).  Then S* = {strings of digits}.
		Note that some strings in S* begin with 0, so that S* does not consist of the decimal numbers. 
		Note also that S*contains the empty string.

Example 	Let S = {1, 2, 3, 4, 5, 6, 7, 8, 9} U {all two digit decimal numbers.} 
		Then S*= {L} U {all positive integers except for 100, 200, etc.} 

Example 	Let S = {L}.  Then S* = {L}.

Example 	Let S = &.  Then S* = {L}.

Theorem S** = S*.
Proof  Let x Î S**.  Then x = w1w2 . . .  for some w1, w2 Î S*, 
	so that x is a string of elements of S.  Thus, x Î S*.  
	Suppose that x Î S*.  Then x is itself a concatenation of strings, namely itself.  
	Hence x Î S**.