Review

Saturday

Prof. Calvin

CSCI 5100

Aims of Education

Amber Huffman, a Principal Engineer at Google, has spent her career defining standards for the hardware industry. Now with the rapid growth of AI the demand and uses for Open Source Hardware have never been higher. Learn what Open Source Hardware is and why it is important to all of us.

Finite Automata

A 5-tuple \(M = (Q, \Sigma, \delta, q_0, F)\):

  • \(Q\) A finite, non-empty set of states.
  • \(\Sigma\): A finite, non-empty set of input symbols called the alphabet.
  • \(\delta\): The transition function, a mapping
    • \(\delta : Q \times \varepsilon \rightarrow Q\)
  • \(q_0\): The initial state, where \(q_0\) ∈ Q.
  • \(F\): A set of accepting states (or final states), where \(F \subset Q\).

Theorem 1: Union Closure

\[ \forall L(M_1), L(M_2): \exists M_3 : L(M_3) = L(M_1) \cup L(M_2) \]

Proof

\[ \begin{aligned} L(&Q_1, \Sigma, \delta_1, q_1, F_1) \cup L(Q_2, \Sigma, \delta_2, q_2, F_2) = \\ L(&Q_1 \times Q_2, \Sigma, \\ &\delta((q,q')a),\rightarrow (\delta_1(q,a), \delta_2(q',a)), \\ &(q_1, q_2), \\ &\{ (F_1 \times Q_2) \cup (Q_1 \times F_2) \})\blacksquare \end{aligned} \]

Theorem 2: NFA → DFA

\[ \forall M_{NFA}: \exists M_{DFA} : L(M_{NFA})) = L(M_{DFA})) \]

Proof

\[ \begin{aligned} M_{NFA}(&Q, \Sigma, \delta, q_1, F_1) = \\ M_{DFA}(&\mathcal{P} (Q), \Sigma, \delta, \{q_1\}, \\ & \{ R \in \mathcal{P} (Q) | R \cap F \neq \varnothing \})\blacksquare \end{aligned} \]

Theorem 3: Concat Closure

\[ \forall L(M_1), L(M_2): \exists M_3 : L(M_3) = L(M_1)L(M_2) \]

Proof

\[ \begin{aligned} L(&Q_1, \Sigma, \delta_1, q_1, F_1)L(Q_2, \Sigma, \delta_2, q_2, F_2) = \\ L(&Q_1 \sqcup Q_2, \\ &\Sigma, \\ &\delta_1 \sqcup \delta_2 \cup \{ (f, \varnothing) \rightarrow \{q_2\} | f \in F_1 \} \\ &q_1, \\ &F_2)\blacksquare \end{aligned} \]

Theorem 4: Star Closure

\[ \forall L(M_1): \exists M_3 : L(M_2) = L(M_1)* \]

Proof

\[ \begin{aligned} L(&Q_1, \Sigma, \delta_1, q_1, F_1)* = \\ L(&Q_1 \cup \{q_0\}, \\ &\Sigma, \\ &\delta_1 \cup \{ (f, \varnothing) \rightarrow \{q_1\} | f \in F_1 \cup \{q_0\} \} \\ &q_0, \\ &f \in F_1 \cup \{q_0\})\blacksquare \end{aligned} \]

GNFAs

  • It is simple enough to argue for GNFAs
    • Every operation can be an NFA
    • Any NFA node can be replaced with an NFA
      • Essentially the closure options.
    • Therefore, a GNFA is equivalently expressive to NFA
  • The complete proof is left as an exercise to the interested student.

Atomicity Lemma

\[ \begin{aligned} \exists M_1, M_2, M_3 :\\ L(M_1) &= a \in \Sigma \\ L(M_2) &= \Sigma^0 \\ L(M_2) &= \varnothing \end{aligned} \]

Proof

\[ \begin{aligned} M_1 &= (\{q_0,q_1\}, &\Sigma, &\{ (q_0, a) \rightarrow \{q_1\} \}, &q_0, &\{q_1\}) \\ M_2 &= (\{q_0\}, &\Sigma, &\{ (q_0, a) \rightarrow \{q_1\} \}, &q_0, &\{q_1\}) \\ M_3 &= (\{q_0\}, &\Sigma, &\varnothing, &q_0, &\{q_1\}) \\ \end{aligned} \]

Theorem 5:

\[ \forall R : \exists M : R = L(M) \]

Proof

  • Atomic \(R\) follows from Atomicity Lemma
  • Composite \(R\) follows from Closure properties (Theorems 1-4)

Base Lemma

\[ \forall |G| = 2 := (\{q_0,q_1\},\Sigma,\delta,q_0,\{q_1\}) : \exists R : R = L(G) \]

Proof

  • By definition, \(G = (\{q_0,q_1\},\Sigma,\delta,q_0,\{q_1\})\)

  • By definition, \(\delta = \{ (q_0, R') \rightarrow q_1 \}\)

  • Let \(R = R'\)

  • \(\blacksquare\)

Inductive Lemma

\[ \forall |G| = (k > 2) : \exists |G| = (k - 1) : L(G) = L(G') \]

Proof

  • By definition, \(G = (Q,\Sigma,\delta,q_0,\{q_n\})\)

  • Select arbitrary \(q_i \in Q \setminus \{q_0, q_n\}\)

  • Take \(G' = (Q \setminus \{q_i\},\Sigma,\delta_{-i},q_0,\{q_n\})\)

Theorem 6

\[ \forall M : \exists R : R = L(M) \]

Proof

  • \(\forall |G| = 2 := (\{q_0,q_1\},\Sigma,\delta,q_0,\{q_1\}) : \exists R : R = L(G)\)
  • \(\forall |G| = (k > 2) : \exists |G| = (k - 1) : L(G) = L(G')\)
  • By induction, \(\forall M : \exists R : R = L(M)\)

Pumping Lemma

  • \(s \in A \land |s| > p\) requires
    • \(xy^nz \in A\)
    • \(|y| > 0\)
    • \(|xy| \leq p\)

Proof

finite_automata d0 q0 q 0 d0->q0 qi s i q0->qi x qi->qi y qn q n qi->qn z

CFGs

  • Rule: Statements of form Variable → (string of symbols and terminals)
  • Variable: Those symbols on the left-hand side (LHS) of a → in a rule
  • Terminals: Those symbols which appear in only on the right-hand side (RHS)
  • Starting variable: The topmost symbol.

Ambiguity

\[ \begin{align*} G_2& \\ &\left. \begin{aligned} &E \rightarrow E+T \quad | \quad T\\ &T \rightarrow T\times F \quad | \quad F \\ &F \rightarrow ( E ) \quad | \quad a \end{aligned} \right. \end{align*} \]

\[ \begin{align*} G_3& \\ &\left. \begin{aligned} &E \rightarrow E+E \quad | \quad E \times E \quad | \quad ( E ) \quad | \quad a\\ \end{aligned} \right. \end{align*} \]

  • These represent the same language (\(L(G_2) = L(G_3)\))!
  • But \(G_3\) is ambigious!

Stretch Break