Definition

R is a regular expression if R is:

1. a for some a in the alphabet \Sigma,
2. \epsilon
3. \phi
4. (R_1 \cup R_2), where R_1 and R_2 are regular expressions
5. (R_1 \circ R_2), where R_1 and R_2 are regular expressions, or
6. (R_1^*), where R_1 is a regular expression.

Layperson: 1—3 describe the simplest base conditions, 4—6 say that we can do a bunch of regular operations to make more complex REs.

• 1—3 can be thought of as the base cases in a recursive function.

How Everything Relates:

• A regular language is a language that can be represented by a DFA/NFA.
• A regular expression is a pattern that describes a regular language.

Regular Expression Shorthands:

• (a \cup b) can be rewritten as \Sigma
• RR^* can be rewritten as R^+
• The concatenation of k R’s can be rewritten as R^k
• Programming languages have tons of shorthand for REs.

Some Identities to Remember:

R \cup \phi = R

• Adding an empty language to R won’t change it. R \circ \epsilon = R
• Joining an empty string to R won’t change it.

Examples

Note: Alphabet is {0,1}

Conversion and properties of RL and RE:

1. (\Sigma\Sigma)^* = { w | w is a string of even length}
2. (\Sigma\Sigma\Sigma)^* = { w | w is a string of length divisible by 3}
3. 001 = { w | w is the string 001 }
4. 001 \cup 10 = { w | w is the string 001 or 10 }
5. \Sigma^* 001 \Sigma^* = { w | w contains the substring 001 }
6. 0^*10^* = { w | w contains a single one }
7. See Example 1.53 in the book for more examples…

Create the RE for the following regular languages:

Q: { w | w contains at least two 1s }

A;

• The smallest string is 11
• The substring of 11 can be written as \Sigma^* 11 \Sigma^*
• 0s don’t move the needle, but they can be in-between, so \Sigma^* 1 0^* 1 \Sigma^*

Thus, the RE is \Sigma^* 1 0^* 1 \Sigma^*

Q: { w | w contains at an even amount of 1s }

A;

• The smallest string is 11
• 0s don’t move the needle, so we can account for them like so: 0^* 1 0^* 1 0^*
• This pattern repeat and still be even, so (0^* 1 0^* 1 0^*)^+

Thus, the RE is (0^* 1 0^* 1 0^*)^+

Q: { w | w doesn’t contain the substring 10 }

A:

Observations:

• Remember, NOT isn’t a regular operation, so we need to write an RE from scratch for this.

0^* 1^*

Q: { w | w contains 3 ones }

A:

Observation:

• 111 is the shortest string
• Essence: The number of 0s and their position doesn’t matter.
• 0^* 1 0^* 1 0^* 1 0^*

Q: What the value?

\begin{align*} a \cup b &= \\ a \circ b &= \\~\\ a \cup \epsilon &= \\ a \circ \epsilon &= \\~\\ \phi \cup \epsilon &= \\ \phi \circ \epsilon &= \\~\\ a^* &= \\ b \circ a^* b &= \\ \end{align*}

A: \begin{align*} a \cup b &= \{ a,b \} \\ a \circ b &= \{ \texttt{ab} \} \\~\\ \end{align*} \begin{align*} a \cup \epsilon &= \{ a, \epsilon \} \\ a \circ \epsilon &= \{ a \} \\~\\ \phi \cup \epsilon &= \epsilon \\ \phi \circ \epsilon &= \{ \} \\ a^* &= \{ \epsilon, a^1, a^2, a^3, ... \} \\ b \circ a^* b &= \\ \end{align*}

Takeaways:

• Epsilon matters in union, but not in concatenation
  • alt: Epsilon matters when branching, but not on straightforward paths.
• Anything concatenated with \phi is \phi

Q: Write the NFA and GNFA for R_1 \circ (R_2)^* \circ R_3

A: