Steven! Ragnarök avatar Steven! Ragnarök committed 7f94870

Update notes and fix typo in date.

Comments (0)

Files changed (2)

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)
-
-
+CS 154 Notes: January 30, 2012
+==============================
+
+Preliminary definitions:
+
+- An __alphabet__ is a finite set of symbols. An alphabet is *not* a symbol.
+- A __string__ over an alphabet is Σ is a finite sequence of symbols from Σ.
+- A __language__ over the alphabet Σ is a set of strings over Σ.
+	- Also, alphabets and strings must be finite but languages needn't
+		be
+
+***NOTE*** Thus, programming languages are sets of programs.
+
+
+
+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 english alphabet are used for
+	strings. (z, y, x...)
+
+- λ will denote the empty string.
+
+We'll write the string whose only symbol is a as a.
+With this notation x**a** = x.**a**.
+
+
+Why is This Interesting?
+------------------------
+
+Many questions in programming reduce to questions of membership in languages.
+
+Questions like:
+
+- Is `x2!y` a legal identifier in language PQR?
+- Is `null` a legal statement in language QRS?
+- Is 10101010101 a prime number?
+- Is `Buffalo buffalo.` a legal English sentence.
+
+
+Strings, an enhanced and expanded definition
+--------------------------------------------
+
+A string over alphabet Σ is one of of the following:
+- empty.
+- has the form x.a where x is a string over Σ and a is an element of Σ.
+
+Intuition shows that x.a results from adding the symbol a to the end of the
+string x. The empty string is written as λ.
+
+
+String Concatenation and Length
+-------------------------------
+
+If x and y are strings then the concatenation xy (or x∙y) of x and y is
+
+- x if y is empty
+- (xz).a if y = z.a
+
+*Recursion is your friend!*
+
+x is a __prefix__ of y iff there exists __z__ with y = x**z**. In the previous
+case, x is a prefix of y.
+
+If x is a string then the length of the string |x| is
+
+- 0 if x is empty
+- 1 + |y| if x = y.a
+
+*Recursion is your friend!*
+
+So the length of the character string abc is:
+
+		1 + length(ab)
+		= 1 + (1 + length(a))
+		= 1 + (1 + (1 + length(λ)))
+		= 1 + (1 + (1 + 0))
+		= 3
+
+Stringy Theorems
+----------------
+
+1. If x is an empty string, then xy = y.
+
+2. 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.
+
+3. **Preliminary**: The first symbol of a nonempty string xa is
+	- a if x = λ
+	- the first symbol of x otherwise.
+**Theorem**: 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 nonempty.
+	- undefined if both x and y are empty.
+**Corollary** If x is a string over an alphabet Σ and b is a symbol of Σ, then
+the first symbol of bx is b. Also, |bx| = 1 + |x|.
+
+
+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 concatenating n copies of x. Formally it
+equals
+
+- λ if n = 0.
+- x^(n-1)x if n > 0
+
+The Language L^n contains all concatenations of n members of L. Formally it
+equals
+
+- {λ} if n = 0
+- L^(n-1)∙L 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 from the first if Σ is considered as a set of
+strings of length 1.
+
+Sometimes the \* operator is called the Kleene closure operator.
+
+λ is a member of L\* for all L. (L\*)\* = L\*, so L\* is closed under the
+closure operator.
+
+Properties of Concatenation
+---------------------------
+
+- Theorem: (xy)w = x(yw)
+- Theorem x^m x^n = x^(m+n)
+- Corollary: x^n = x x^(n-1)
+	- So the defintion of x^n could also have been stated this way.
+	- Also, L^m L^n = L^(m+n), so L^n = L L^(n-1)
+
+***Warning***: |LM| needn't euqal |L||M|, as L might be {a, ab} and M might be
+{bc,c c}.
+
+
+String Reversal
+---------------
+
+The reverse w^R of a string w is
+
+- λ if w = λ
+- az^R if w = za
+
+		(abc)^R = c(ab)^R
+		= c(b(a^R))
+		= c(b(a(λ^R))) = cba
+
+*Recursion is your friend!*
+
+
+### 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)
+
+
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.