+CS 154 Notes: January 30, 2012

+==============================

+P:reliminary definitions:

+- An __alphabet__ is a finite set of symbols. An alphabet is *not* a symbol.

+- Capital letters are used for languages. (L, M, N...)

+- Capital greek are used for alphabets. (Σ, Μ, Ν...)

+- Lower case leters near the beginning of the english alphabet are symbols from

+- Lowercase letters near the end of the the english alphabet are used for

+- λ will denote the empty string.

+-If x and y are strings, then concatenation xk or x∙y of x and y is:

+We'll write the string whose only symbol is a as a. With this notation x__a__ =

+x is a __prefix__ o fy iff there exists __z__ with y = x__z__. In the previous

+case, x is a prefix of y.

+If x is an empty string, then xy = y.

+If x and y are strings, then |xy| = |x| + |y|.

+***Warning***: We'll soon define a notion of language concatenation for which

+the analog of the second theorem does not hold true.

+- The language LM is equal to {xy | x ε L and y ε M}.

+- An alternate notation for LM is L∙M.

+The string x^n is obtained from x by concatenationg n copies of x. Formally it

+If L is a language then,

+- L* is the union of L^n over all n >= 0

+- L+ is the union of L^n over all n >= 1 (Thus excluding the empty string)

+- If Σ is an alphabet then:

+ - Σ* is the set of all strings over Σ.

+ - Σ+ is the set of all nonempty strings over Σ.

+- The second definition follows frm the first if Σ is considered as a set of

+If x is an empty string, then xy = y.

+Proof: by induction on |y|

+Basis: If |y| = 0, then y is empty. And then by definition of concatenation,

+xy = x, which is empty by assumption.

+Inductive Step: If |y| > 0, then y = z∙a for some z and a, Here

+ xy = (xz).a (by definition of concatenation)

+Proof: by induction on |y|

+Basis: If |y| = 0 then y is empty so we need to show that |xy| = |x| But in this

+Induction step: If |y| > 0 then y = z.a for some z and a, so by definition of

+concatenation, xy = (xz).a

+> "Induction proofs are fair game for the exam but they will be simple."

+If x and y are strings, the first symbol of xy is the first symbol

+of x if x is nonempty, the first symbol of y if x is empty but y is not, and

+undefined if both x and y are empty.

+Proof: If x is empty, then xy = y, so hte last two cases follow immediately from

+If x is not empty we may proceed by induction on |y|.

+Induction step: If |y| > 0, then y = z.a for some z and a, so

+ the first symbol of xy = the first symbol of (xz).a (by defintion of concatenation)

+ = the first symbol of xz (by definition of first symbol)

+ = the first symbol of x (by induction)

+Proof: by induction on |w|

+Basis: If |w| = 0 then w is empty, so that both (xy)w and x(yw) equal xy.

+Inductive Step: If |w| > 0 then w is empty then w = z.a for some z and a, so

+ = ((xy)z).a (by definition of concatenation)

+ = ((xy)z).a (by definition of concatenation)