##### 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 - {q) → R is the transition function
_{start}}

- In other words, \delta;: (Q –

- 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 = { 0
^{n}1^{n}| 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

- We can define A = L(0
- Simple Reductions
- If A
^{*}is nonregular, then so is A - If A is nonregular, then so is A
^{C} - If A is nonregular, then so is A
^{R}

- If A
- Complex Reductions (let all Rs be regular)
- For A' = (A ∪ R) ∩ (A
^{C}∪ R') - For A' = ((A
^{C}∩ R) ∪ (A^{*}∩ R')) ∘ R'' - For A' = (A ∘ R) ∩ (A
^{C}∘ R') - If A' is nonregular, then so is A

- For A' = (A ∪ R) ∩ (A

- Given B = { 0

##### 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 δ(q
_{0}, x) = δ(q_{0}, y). However, this is not distinguishable, hence contradiction

- If DFA has more states than the index, then there must be some x, y in X such that δ(q
- 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 G
_{1}= A → 0A1, A → B, B → # - Derivation of '000#111': A ⇒ 0A1 ⇒ 00a11 ⇒ 000A111 ⇒ 000B111 ⇒ 000#111

- Eg. Let grammar G
- CFG Definition
Variables A, B, C, <TERM>, <EXPR> (Angle brackets denote single variable rather than sequence of letters) Alphabet (of terminals) 0, 1, # Substitution Rules <EXPR> → <TERM> Start Variable A (LHS of first substitution rule) - u derives v (u ⇒
^{*}v if u = v or if u ⇒ u_{1}⇒ u_{2}… u_{k}= v, k ≥ 0.