menu

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
  • VariablesA, B, C, <TERM>, <EXPR> (Angle brackets denote single variable rather than sequence of letters)
    Alphabet (of terminals)0, 1, #
    Substitution Rules<EXPR> → <TERM>
    Start VariableA (LHS of first substitution rule)
  • u derives v (u ⇒* v if u = v or if u ⇒ u1 ⇒ u2 … uk = v, k ≥ 0.