Languages can be generated by regular expressions $R$.

There are 3 atomic regular expressions:

• $a \in \sum$
  • $L(R) = \{a\}$
• $\epsilon$
  • empty word
  • $L(R) = \{\epsilon\}$
• $\emptyset$
  • empty set
  • $L(R) = \emptyset$

We can build more complex expressions using:

• $+/\cup$
  • Sum/Union (Mean the same thing)
  • $L(R) = L(R_1) \cup L(R_2)$
• $.$
  • Concatenation
  • $L(R) = L(R_1) . L(R_2)$
• $*$
  • Kleene star - use any number (including 0) of the sequence of letters this is applied to repeatedly
  • $L(R) = L(R_1)^*$
• $()^n$
  • A variation on the kleene star - use the sequence of letters this is applied to $n$ times.

<aside> 👿 The $*$ operator has the highest precedence, followed by $.$ and then $+$

</aside>

Examples

1. $\sum = \{a,b\}$ and $R = (a+b)^*$. What is $L(R)$, the language generated by $R$?
   • $L(R) = \{a,b\}^= \sum^$
2. $R = (a+b)^*(a+bb)$
   1. $L(R) = \sum^* . \{a,bb\}$
   2. That is, all words which end in $a$ or $bb$

Describing DFA/NFA with Regex

Take this DFA:

Let us take the complement