Closures

31 Jan 01:30 PM

Prof. Calvin

CSCI 5100

Sketch

  • Closures
    • Union
    • Concatenation
    • Star

Union

Review

  • We previously proved closure under union (for regular languages).
  • We did so using only deterministic finite automata (DFAs).
  • The proof was somewhat demanding and non-trivial.
  • We re-prove using NFAs
    • Separately, we prove the result for NFAs.

Recall: Theorem 1

\[ \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} \]

New Technique

  • We can equivalently argue:
  • Take both \(M_1\) and \(M_2\)
  • Non-deterministically read into both simultaneously
  • We begin with the first edge from the first state.

New \(Q\)

  • Take \(Q\) to be all states in \(Q_1\) and in \(Q_2\)
    • We can renumber them, if needed.
    • We add novel start state \(q_0\)
      • Initial state with no return edges
    • \(q_1\) and \(q_2\) persist, without start edge.
  • \(Q_3 = Q_1 \sqcup Q_2 \cup \{q_0\}\)
    • \(\sqcup\) is disjoint union - members indexed by initial set to avoid duplication.

New \(\delta\)

  • Same as \(Q\) - take \(\delta_1\) and \(\delta_2\)
    • Add \(q_0\) with outgoing edges \(q_1 \sqcup q_2\)
    • No other changes.

\(q_0, F\)

  • We use the new initial state.
  • The set of accepting states is also a disjoint union.

Graphically

\(M_1\)

\(M_2\)

finite_automata q0 q1 q 1 q0->q1 q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0}

finite_automata q0 q1 q 1 q0->q1 q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

Renumber for \(\sqcup\)

\(M_1\)

\(M_2\)

finite_automata r0 r1 r 1 r0->r1 r1->r1 {0} r2 r 2 r1->r2 {1} r2->r1 {0}

finite_automata q0 q1 q 1 q0->q1 q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

Combine

finite_automata r0 r1 r 1 r0->r1 r1->r1 {0} r2 r 2 r1->r2 {1} r2->r1 {0} q0 q1 q 1 q0->q1 q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

Add \(q_0\)

finite_automata r0 q0 q 0 r0->q0 r1 r 1 r1->r1 {0} r2 r 2 r1->r2 {1} r2->r1 {0} q0->r1 {0} q0->r2 {1} q1 q 1 q0->q1 {0} q2 q 2 q0->q2 {1} q1->q1 {0} q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

  • Essentially just the two machines running in parallel.

Use \(\varepsilon\) edges.

finite_automata r0 q0 q 0 r0->q0 r1 r 1 r1->r1 {0} r2 r 2 r1->r2 {1} r2->r1 {0} q0->r1 σ q1 q 1 q0->q1 σ q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

Recall: Theorem 2

\[ \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 1

\[ \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 \sqcup Q_2 \cup \{q_0\}, \\ &\Sigma, \\ &\delta_1 \sqcup \delta_2 \cup ((q_0, \varepsilon) \rightarrow \{q_1, q_2\} \\ &q_0, \\ & F_1 \sqcup F_2)\blacksquare \end{aligned} \]

Concatenation

Goal

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

New \(Q\)

  • As with union, so with concatenation.
  • \(Q_3 = Q_1 \sqcup Q_2\)

New \(\delta\)

  • As with union, so with concatenation.
  • \(\delta_3 = \delta_1 \sqcup \delta_2\)
  • Additionally need to get from \(M_1\) to \(M_2\)
    • Add \(\varepsilon\) (empty string) paths
    • From \(q_n \in F_1\)
    • To \(q_2\) \(\delta_3 = \delta_1 \sqcup \delta_2 \cup \{ (f, \varepsilon) \rightarrow \{q_2\} | f \in F_1 \}\)

\(q_0, F\)

  • We use only \(M_1\) initial state \(q_1\)
  • We use only \(M_2\) accepting states \(F_2\)

Combine Graphically

finite_automata r0 r1 r 1 r0->r1 r1->r1 {0} r2 r 2 r1->r2 {1} r2->r1 {0} q0 q1 q 1 q0->q1 q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

Update \(q_0\)

finite_automata r0 r1 r 1 r0->r1 r1->r1 {0} r2 r 2 r1->r2 {1} r2->r1 {0} q1 q 1 q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

Update \(F\)

finite_automata r0 r1 r 1 r0->r1 r1->r1 {0} r2 r 2 r1->r2 {1} r2->r1 {0} q1 q 1 q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

Update \(\delta\)

finite_automata r0 r1 r 1 r0->r1 r1->r1 {0} r2 r 2 r1->r2 {1} q1 q 1 r1->q1 σ r2->r1 {0} r2->q1 σ q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

  • Recall \(\exists\) an equivalent DFA by Theorem 2

Theorem 3

\[ \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, \varepsilon) \rightarrow \{q_2\} | f \in F_1 \} \\ &q_1, \\ &F_2)\blacksquare \end{aligned} \]

Star

Goal

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

  • We note that the empty string \(\varepsilon \in A* \forall A\)

New \(Q\)

  • \(Q_2 = Q_1 \cup \{q_0\}\)
  • We add novel \(q_0\) to support the empty string.

New \(\delta\)

  • Need to get from \(F\) to \(q_1\)
    • Add \(\varepsilon\) paths
    • From \(q_n \in F_1\)
    • To \(q_1\)
    • And \(q_0\) to \(q_1\)
  • \(\delta_2 = \delta_1 \cup \{ (f, \varepsilon) \rightarrow \{q_2\}| f \in F_1 \cup \{q_0\} \}\)

\(q_0, F\)

  • We add novel start state \(q_0\)
  • We include \(q_0\) in \(F\)
  • This includes the empty string.

Combine Graphically

finite_automata q0 q1 q 1 q0->q1 q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

Update \(q_0\) and \(F\)

finite_automata d0 q0 q 0 d0->q0 q1 q 1 q0->q1 σ q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q3 {0,1}

Update \(\delta\)

finite_automata d0 q0 q 0 d0->q0 q1 q 1 q0->q1 σ q1->q1 {0} q2 q 2 q1->q2 {1} q2->q1 {0} q3 q 3 q2->q3 {1} q3->q1 σ q3->q3 {0,1}

Theorem 4

\[ \forall L(M_1): \exists M_2 : 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, \varepsilon) \rightarrow \{q_1\} | f \in F_1 \cup \{q_0\} \} \\ &q_0, \\ &F_1 \cup \{q_0\})\blacksquare \end{aligned} \]

Stretch Break