3 - Closure

ucla | CS 181 | 2024-04-05 14:20

---

Table of Contents

• Basic Notions
• Regular Operations
  • Fundamental Ops
  • Functional Ops
  • Corollaries

Basic Notions

• Regular Language - a language for which there exists a DFA/NFA that recognizes it
• Regular languages remain regular under regular operations, the definition is bidirectional.

  Regular Operations

  Fundamental Ops

• Complement $L={\bar{L}}_1$
  • $F_1\to {\bar{F}}_1$ for DFAs
  • We need to inspect state transitions for NFAs to ensure the complement is regular.
• Union $L=L_1\cup L_2$
  • Combine using $\epsilon$ transitions
  • Combine $M_1$ and $M_2$ s.t. their union model $M^{\prime }$ is defined by the cartesian products of $M_1$ and $M_2$ definitions
    • $Q^{\prime }=Q_1\times Q_2$
    • ${\delta }^{\prime }((q,r),a)=({\delta }_1(q,a),{\delta }_2(r,a))$

    • $F’=\bigg{(q,r)\space

      \space q\in F_1\lor r\in F_2\bigg}=(F_1\times Q_2)\cup(Q_1\times F_2)$

• Intersection $L=L_1\cap L_2$
  • DeMorgan’s => $\bar{L}={\bar{L}}_1\cup {\bar{L}}_2$
  • We showed complement is regular, and the union is regular; thus, the intersection is regular bc the complement is regular
    • $Q^{\prime }=Q_1\times Q_2$
    • ${\delta }^{\prime }((q,r),a)=({\delta }_1(q,a),{\delta }_2(r,a))$

    • $F’=\bigg{(q,r)\space

      \space q\in F_1\land r\in F_2\bigg}=F_1\times F_2$

• Concatenation $L=l_1;l_2|l{1}_{\in }{L}_1,l_2\in L_2$

  Functional Ops

• Add $L={x\sigma y\space

  \space \sigma\in\Sigma,xy\in L}$

  • sps DFA $D$ accepts $xy$
  • make 2 copies: $D_1,D_2$, and for some state $q$ that transitions on $\sigma$
  • Now, make the state $q$ in $D_1$ have a transition on $\sigma$ to the same state $q$ in $D_2$
  • but adjust $D_1$ so that all states are rejecting and do NOT include a start transition in $D_2$

• Skip $L={xy\space

  \space x\sigma y\in L,\sigma\in\Sigma}$

  • Similar to add, sps $D_1,D_2$ are the same DFA but 2 copies that both accept $xy$
  • $D_1$ has the start transition but is all rejecting and $D_2$ has no start transition
  • now, from some state $q\in D_1$ draw $\epsilon -$transitions for each symbol in the alphabet to the same state $q\in D_2$ but unique copies for each symbol
  • i.e., $q\in D_1$ will have 2 $\epsilon -$transitions for the binary alphabet to 2 copies of $q\in D_2$
    

    Corollaries

    If $L_1,L_2,\dots ,L_n$ are regular, then the language described by any regular operations on any number of them is also regular e.g. $L=L_1\cup L_2\cup L_3\cup \dots \cup L_n$ e.g.$L=L_1\cap L_2\cap \dots \cap L_n$

Every finite language is regular Pf:

• sps. $L$ is finite then, $\bigcup _{w\in L}w$ is regular by the corollary above WLOG