Skip to content

4. Regular Languages

Jan 20, 2022

Properties of Regular Languages

  • For regular languages \(L_1\) and \(L_2\), the following operations the result is also regular, i.e. closed under:

    • Union \(L_1 \cup L_2\)
    • Concatenation \(L_1 L_2\)
    • Star \(L_1^*\)
    • Reversal: \(L_1^R\)
    • Complement \(\overline{L_1}\)
    • Intersection \(L_1 \cap L_2\)

Operation closures

union: \(w \in L_1 \cup L_2\) \(\Leftrightarrow\) \(w \in L_1\) or \(w \in L_2\)

concatenation: \(w \in L_1L_2\) \(\Leftrightarrow\) \(w = w_1w_2: w_1 \in L_1\) and \(w_2 \in L_2\)

star: \(w \in L^*\) \(\Leftrightarrow\) \(w = w_1w_2...w_k : w_i \in L\) or \(w = \epsilon\)

reverse: reverse all transitions, make the initial sate accept state and the accept state the initial state

complement: take the DFA that accepts L, make the accept states regular and vice versa => note: NFA cannot be used for complement

intersection: \(L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}\) (by De Morgan's law)

\(L_1, L_2\) (regular) => \(\overline{L_1}, \overline{L_2}\) (regular) => \(\overline{L_1} \cup \overline{L_2}\) (regular) => \(\overline{\overline{L_1} \cup \overline{L_2}}\) (regular)

=> \(L_1 \cap L_2\) is regular

Alternative procedure for intersection

Define an NFA that simulates in parallel \(M_1\) and \(M_2\)

  1. build intersection
  2. for each new state and for each symbol add transition to either an existing state or create a new state and point to it
  3. repeat step 2 until no new states are added
  4. designate accept states

Intersection DFA \(M\) simulates in parallel \(M_1\) and \(M_2\) and accepts a string \(w\) if and only if \(M_1\) accepts \(w\) and \(M_2\) accepts \(w\).