##### Lecture 6 • 2017/09/21
• Reflexive, symmetric, transitive
• S~ represents an equivalence class, where S is the set & ~ represent equal
• δ(s, a) – state you went to after reading alphabet a at state s
• δ*(s, w) – state you went to after reading all letters in word w, starting at state s
##### Lecture 6 • 2017/09/26
• Every NFA can be done with a DFA
• E(R) = { q | q can be reached from R by traveling along 0 or more ε arrows }
• R is a regular expression if
• a for some a in alphabet Σ
• ε
• Union, concatenation, and star of regular expressions are regular expressions
##### Lecture 7 • 2017/09/28
• Lemma – if a language is regular, then it is described by a regular expression
• Generalized NFA
• Start state has transition arrows to every other state, but no arrows coming in from any other state
• Single accept state, with arrows coming in from every other state and no arrows from any other state. The accept state cannot be the start state
• For all other states, one arrow goes from every state to every other state
• In other words, \delta;: (Q –
) x (Q - {qstart}
) → R is the transition function
• GNFA → regex
• Basis – if GNFA has 2 states, the states are a start & accept state with a single transition to the accept state
• TODO
##### Lecture 8 • 2017/10/03
• Reduction
• Given B = { 0n1n | n ≥ 0 }
• Given C = { w | w contains an equal number of 0s & 1s }
• If C is regular, then so is B
• If B is nonregular, then so is C
• Proof
• We can define A = L(0*1*), which is obviously regular; if C was regular than so would C ∩ A = B
• Simple Reductions
• If A* is nonregular, then so is A
• If A is nonregular, then so is AC
• If A is nonregular, then so is AR
• Complex Reductions (let all Rs be regular)
• For A' = (A ∪ R) ∩ (AC ∪ R')
• For A' = ((AC ∩ R) ∪ (A* ∩ R')) ∘ R''
• For A' = (A ∘ R) ∩ (AC ∘ R')
• If A' is nonregular, then so is A
##### Lecture 9 • 2017/10/05
• Myhill-Nerode Theorem
• A set of strings (X) is pairwise distinguishable by language L is every two elements in X are distinguishable by L (∀x, x' in X, x ≢L x')
• Define an index of L to be the size of a maximum set X that is pairwise disinguishable by L. L is regular iff the index is finite.
• The smallest index is also the number of states of the smallest DFA recognizing L
• If DFA has more states than the index, then there must be some x, y in X such that δ(q0, x) = δ(q0, y). However, this is not distinguishable, hence contradiction
• Minimal DFAs can be discovered using the Myhill-Nerode Theorem by first discovering the pairwise distinguishable set, then by creating a DFA whose states matches the distinguished set values.
##### Lecture 10 • 2017/10/10
• Context-Free Grammar
• Derivation – conversion of word from start variable (typically first symbol in grammar)
• Eg. Let grammar G1 = A → 0A1, A → B, B → #
• Derivation of '000#111': A ⇒ 0A1 ⇒ 00a11 ⇒ 000A111 ⇒ 000B111 ⇒ 000#111
• CFG Definition
•  Variables A, B, C, , (Angle brackets denote single variable rather than sequence of letters) Alphabet (of terminals) 0, 1, # Substitution Rules Start Variable A (LHS of first substitution rule)
• u derives v (u ⇒* v if u = v or if u ⇒ u1 ⇒ u2 … uk = v, k ≥ 0.