Closures

Automata

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\)

Renumber for \(\sqcup\)

\(M_1\)

\(M_2\)

Combine

Add \(q_0\)

• Essentially just the two machines running in parallel.

Use \(\varepsilon\) edges.

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

Update \(q_0\)

Update \(F\)

Update \(\delta\)

• 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

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

Update \(\delta\)

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

• Home