5. Regular Expressions

Jan 20/25, 2022

Regular expressions

describe regular languages
primitive expressions: $\emptyset, ϵ, α$
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 (ϵ) = {ϵ}$
- $L (α) = {α}$

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 (ϵ), L (α)$ 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