# Commits

committed 407cc46

Partial notes from today's class.

Will require going over slides to flesh out as well as formatting fixes.

• Participants
• Parent commits 0448720

# File 01-30-2011.md

`+CS 154 Notes: January 30, 2012`
`+==============================`
`+`
`+P:reliminary definitions:`
`+`
`+- An __alphabet__ is a finite set of symbols. An alphabet is *not* a symbol.`
`+- An `
`+`
`+`
`+Notational conventions`
`+----------------------`
`+`
`+- 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`
`+alphabets. (a, b, c..)`
`+`
`+- Lowercase letters near the end of the the english alphabet are used for`
`+	strings. (z, y, x...)`
`+`
`+- λ will denote the empty string.`
`+`
`+-If x and y are strings, then concatenation xk or x∙y of x and y is:`
`+	- x if y is empty.`
`+	- (xz).a if y  = z.a`
`+`
`+We'll write the string whose only symbol is a as a. With this notation x__a__ =`
`+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.`
`+`
`+`
`+Language Concatenation`
`+----------------------`
`+`
`+- The language LM is equal to {xy | x ε L and y ε M}.`
`+- An alternate notation for LM is L∙M.`
`+`
`+`
`+Repetition`
`+----------`
`+`
`+The string x^n is obtained from x by concatenationg n copies of x. Formally it`
`+equals `
`+`
`+- λ if n = 0.`
`+- x^(n-1)x if n > 0`
`+`
`+`
`+Closure`
`+-------`
`+`
`+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`
`+strings of length 1.`
`+`
`+### Theorem 1:`
`+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)`
`+		= z.a (by induction)`
`+		= y (by assumption)`
`+`
`+### Theorem 2:`
`+|xy| = |x| + |y|`
`+`
`+Proof: by induction on |y|`
`+`
`+Basis: If |y| = 0 then y is empty so we need to show that |xy| = |x| But in this`
`+case xy = x.`
`+`
`+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."`
`+`
`+### Theorem 3:`
`+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`
`+the definition.`
`+`
`+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)`
`+`
`+### Theorem 4:`
`+(xy)w = x(yw)`
`+`
`+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)w = (xy) (z.a)`
`+		= ((xy)z).a (by definition of concatenation)`
`+		= ((xy)z).a (by definition of concatenation)`
`+`
`+`