5. Regular Expressions

Jan 20/25, 2022

Regular expressions

• describe regular languages

• primitive expressions: \(\emptyset, \epsilon, \alpha\)

• given regular expressions \(r_1\) and \(r_2\), can compose to create other regular expressions
  e.g.     \(r_1 + r_2\)     \(r_1 \cdot r_2\)     \(r_1^*\)

• \(L(r)\) language of regular expression \(r\), for primitive expressions:

  • \(L(\emptyset) = \emptyset\)
  • \(L(\epsilon) = \{\epsilon\}\)
  • \(L(\alpha) = \{\alpha\}\)

Regular expressions and regular languages

• For any regular expression \(r\) the language \(L(r)\) is regular

• Proof steps: show that languages generated by REs \(\Leftrightarrow\) Regular languages

  • languages generated by REs \(\subseteq\) Regular languages
    => proof by induction on the size \(r\)

    • base case primitive expressions: \(L(\emptyset), L(\epsilon), L(\alpha)\) are regular languages

    • inductive step: suppose regular expressions \(r_1\) and \(r_2\) and \(L(r_1)\) and \(L(r_2)\) are regular languages => prove that \(L(r_1 + r_2)\)   \(L(r_1 \cdot r_2)\)   \(L(r_1^*)\)   \(L((r_1))\)   are regular

    • by inductive hypothesis we know \(L(r_1)\) and \(L(r_2)\) are regular, we also know union, concat, star of regular languages are closed, therefore these are regular:

    • \(L(r_1 + r_2) = L(r_1) \cup L(r_2)\)

    • \(L(r_1 \cdot r_2) = L(r_1)L(r_2)\)

    • \(L(r_1^*) = L((r_1))^*\)

    • \(L((r_1)) = L(r_1)\)   is trivially regular by induction hypothesis

    • using the regular closure of operations we can construct recursively the NFA \(M\) that accepts \(L(M) = L(r)\)

  • languages generated by REs \(\supseteq\) Regular languages
    => show that for any regular language L there is a regular expressions \(r\) with \(L(r) = L\)   =>   convert NFA that accepts \(L\) to a regular expression

    • since \(L\) is regular there is a NFA \(M\) that accepts it; take it with a single accept state

    • from \(M\) construct the equivalent generalized transition graph in which transition labels are regular expressions e.g. transition label \(a, b\) becomes \(a + b\)

    • reduce the states recursively

    2-state general case:

    

    • repeat until two states are left to obtain the resulting regular expression

---

Standard representations of regular languages: DFAs, NFAs, regular expressions

---