Commits

Steven! Ragnarök committed 407cc46

Partial notes from today's class.

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

Comments (0)

Files changed (1)

+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)
+
+